一. 算法描述
選擇排序：比如在一個長度為N的無序數組中，在第一趟遍歷N個數據，找出其中最小的數值與第一個元素交換，第二趟遍歷剩下的N-1個數據，找出其中最小的數值與第二個元素交換......第N-1趟遍歷剩下的2個數據，找出其中最小的數值與第N-1個元素交換，至此選擇排序完成。
以下面5個無序的數據為例：
56 12 80 91 20（文中僅細化了第一趟的選擇過程）
第1趟：12 56 80 91 20
第2趟：12 20 80 91 56
第3趟：12 20 56 91 80
第4趟：12 20 56 80 91
二. 算法分析
平均時間復雜度：O(n2)
空間復雜度：O(1) (用于交換和記錄索引)
穩定性：不穩定 （比如序列【5， 5， 3】第一趟就將第一個[5]與[3]交換，導致第一個5挪動到第二個5后面）
三. 算法實現
|
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
public class SelectionSort { public static void main(String[] args) { int len = 15; int[] ary = new int[len]; Random random = new Random(); for (int j = 0; j < len; j++) { ary[j] = random.nextInt(1000); } System.out.println("-------排序前------"); // ary=new int[]{10,9,8,7,6,5,4,3,2,1}; //測試交換次數 // ary=new int[]{1,2,3,4,5,6,7,8,10,9}; //測試交換次數 for (int j = 0; j < ary.length; j++) { System.out.print(ary[j] + " "); } selectDesc(ary); selectAsc(ary); } /* * 選擇排序：降序 */ static void selectDesc(int[] ary) { int compareCount = 0;//比較次數 int changeCount = 0;//交換次數 int len = ary.length; int maxValueIndex = -1; //記錄一輪比較下來的最小值索引 for (int i = 0; i < len - 1; i++) { maxValueIndex = i; //從0開始 for (int j = i + 1; j < len; j++) { if (ary[maxValueIndex] < ary[j]) { maxValueIndex = j; //記錄較大的索引 compareCount++; } } // System.out.println("minValueIndex==" + maxValueIndex); if (maxValueIndex != i) {//如果跟左邊的記錄索引不同，則交換 ary[i] = ary[maxValueIndex] + (ary[maxValueIndex] = ary[i]) * 0;//一步交換 changeCount++; } } System.out.println("\n-------降序排序后------比較次數：" + compareCount + "，交換次數" + changeCount); for (int j = 0; j < ary.length; j++) { System.out.print(ary[j] + " "); } } /* * 選擇排序：升序 */ static void selectAsc(int[] ary) { int compareCount = 0, changeCount = 0; int len = ary.length; int minIndex = -1; for (int i = 0; i < len - 1; i++) { minIndex = i; for (int j = i + 1; j < len; j++) { if (ary[minIndex] > ary[j]) { minIndex = j; //記錄較小的索引 compareCount++; } } if (minIndex != i) {//如果跟左邊的記錄索引不同，則交換 ary[i] = ary[minIndex] + (ary[minIndex] = ary[i]) * 0; changeCount++; } } System.out.println("\n-------升序排序后------比較次數：" + compareCount + "，交換次數" + changeCount); for (int j = 0; j < ary.length; j++) { System.out.print(ary[j] + " "); } } } |
打印
|
1
2
3
4
5
6
|
-------排序前------ 125 350 648 789 319 699 855 755 552 489 187 916 596 731 852 -------降序排序后------比較次數：26，交換次數13 916 855 852 789 755 731 699 648 596 552 489 350 319 187 125 -------升序排序后------比較次數：56，交換次數7 125 187 319 350 489 552 596 648 699 731 755 789 852 855 916 |
