本文實例講述了java數據結構與算法之簡單選擇排序。分享給大家供大家參考，具體如下：
在前面的文章中已經講述了交換類的排序算法，這節中開始說說選擇類的排序算法了，首先來看一下選擇排序的算法思想；
選擇排序的基本算法思想：
每一趟在 n-i+1 (i=1,2,3,……,n-1)個記錄中選取關鍵字最小的記錄作為有序序列中第i個記錄。
簡單選擇排序：
設所排序序列的記錄個數為n。i取1,2,…,n-1,從所有n-i+1個記錄（Ri,Ri+1,…,Rn）中找出排序碼最小的記錄，與第i個記錄交換。執行n-1趟 后就完成了記錄序列的排序。
算法實現代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
package exp_sort;public class SimpleSelectSort { static int i; static int temp; public static void selectSort(int array[]) { for (i = 0; i < array.length; i++) { int k = i; //記錄當前位置 for (int j = i + 1; j < array.length; j++) { if (array[j] < array[k]) { //找出最小的數，并用k指向最小數的位置 k = j; } } //交換最小數array[k]與第i位上的數 if (k != i) { temp = array[i]; array[i] = array[k]; array[k] = temp; } } } public static void main(String[] args) { // TODO Auto-generated method stub int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 }; selectSort(array); for (int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println("\n"); }} |
算法分析：
在此排序過程中，需要移動記錄的次數比較少。最好情況下，即待排序記錄初始狀態就已經是正序排列了，則不需要移動記錄；最壞情況下，即待排序記錄初始狀態是按照逆序排列的，則需要移動次數最多是：3(n-1)。排序過程中需要進行的比較次數與初始狀態下待排序的記錄序列的排列情況無關。當i=1時，需要進行n-1次比較；當i=n時，共需要進行的比較次數是：n(n-1)/2，即比較操作的時間復雜度是：O(n^2)，進行移動操作的時間復雜度為O(n)；該排序是不穩定排序。
希望本文所述對大家java程序設計有所幫助。
