直接选择排序算法思想
无序数组a[0…n-1]，第一次从a[0]~a[n-1]中选取最小值，与a[0]交换，第二次从a[1]~a[n-1]中选取最小值，与a[1]交换，….，第i次从a[i-1]~a[n-1]中选取最小值，与a[i-1]交换，…..，第n-1次从a[n-2]~a[n-1]中选取最小值，与a[n-2]交换，总共通过n-1次，得到一个按关键字从小到大排列的有序序列·
#
直接选择排序算法过程如下:
给定n=7，数组a中的7个元素为[8,3,2,1,7,4,6]
- 初始状态 [ 8 3 2 1 7 4 6]
- 第1次，数组a[0..6]中最小的数为a[3]=1，交换a[3]<->a[0]，交换结果[ 1 3 2 8 7 4 6]
- 第2次，数组a[1..6]中最小的数为a[2]=2，交换a[2]<->a[1]，交换结果[ 1 2 3 8 7 4 6]
- 第3次，数组a[2..6]中最小的数为a[2]=3，交换a[2]<->a[2]，交换结果[ 1 2 3 8 7 4 6]
- 第4次，数组a[3..6]中最小的数为a[5]=4，交换a[5]<->a[3]，交换结果[ 1 2 3 4 6 8 7]
- 第5次，数组a[4..6]中最小的数为a[4]=6，交换a[4]<->a[4]，交换结果[ 1 2 3 4 6 8 7]
- 第6次，数组a[5..6]中最小的数为a[6]=7，交换a[6]<->a[5]，交换结果[ 1 2 3 4 6 7 8]
排序完成。
在直接选择排序中，共需要进行n-1次选择和交换，每次选择需要进行 n-i 次比较 (1<=i<=n-1),而每次交换最多需要3次移动，因此，总的比较次数C=(n*n - n)/2，时间复杂度O(n^2)。直接选择排序为原地排序，空间复杂度O(1)。直接选择排序不是稳定的排序算法。
算法实现
直接选择排序算法伪代码
//直接排序SELECTION_SORT(A){ for i=1 to n-1 min=i for j=i+1 to n if A[min] > A[j] min = j swap A[min] <-> A[i]}
Test
用直接选择排序算法对数组arr[10] = {8, 5, 10, 12, 7, 6, 15, 9, 11, 3}从小到大排序。
@Test public void sort3() { Integer arr[] = { 8, 5, 10, 12, 7, 6, 15, 9, 11, 3 }; for (int i = 0; i < arr.length; i++) { int temp = arr[i]; int min = arr[i]; int key = i; for (int j = i; j < arr.length; j++) { key = arr[j] < min ? j : key; min = arr[j] < min ? arr[j] : min; } if (key != i) { arr[i] = arr[key]; arr[key] = temp; } } // 输出数组元素 for (Integer it : arr) { System.out.print(it + " "); } }
输出
3 5 6 7 8 9 10 11 12 15
ゝ一纸荒年。
野性酷女
不念不忘少年蓝@
港控/mmm°
还没有评论，来说两句吧...