【排序算法】（6）选择排序

选择排序

---

2019-11-10  11:43:17  by冲冲

1、概念

选择排序(Selection sort)是一种简单直观的排序算法。

基本思想是，首先在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置；接着，再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

2、基本思想

以数列{20,40,30,10,60,50}为例，演示它的选择排序过程：

① 第1趟：i=0。找出a[1...5]中的最小值a[3]=10，然后将a[0]和a[3]互换。 数列变化：20,40,30,10,60,50 -- > 10,40,30,20,60,50

② 第2趟：i=1。找出a[2...5]中的最小值a[3]=20，然后将a[1]和a[3]互换。 数列变化：10,40,30,20,60,50 -- > 10,20,30,40,60,50

③ 第3趟：i=2。找出a[3...5]中的最小值，由于该最小值大于a[2]，该趟不做任何处理。 

④ 第4趟：i=3。找出a[4...5]中的最小值，由于该最小值大于a[3]，该趟不做任何处理。 

⑤ 第5趟：i=4。交换a[4]和a[5]的数据。 数列变化：10,20,30,40,60,50 -- > 10,20,30,40,50,60

3、完整代码

 1 public class SelectSort {
 2     /**
 3      * 参数说明：
 4      * a -- 待排序的数组
 5      * n -- 数组的长度
 6      */
 7     public static void selectSort(int[] a, int n) {
 8         int i;        // 有序区的末尾位置
 9         int j;        // 无序区的起始位置
10         int min;    // 无序区中最小元素位置
11         for(i=0; i<n; i++) {
12             min=i;
13             // 找出"a[i+1] ... a[n]"之间的最小元素，并赋值给min。
14             for(j=i+1; j<n; j++) {
15                 if(a[j] < a[min])
16                     min=j;
17             }
18             // 若min!=i，则交换 a[i] 和 a[min]。
19             // 交换之后，保证了a[0] ... a[i] 之间的元素是有序的。
20             if(min != i) {
21                 int tmp = a[i];
22                 a[i] = a[min];
23                 a[min] = tmp;
24             }
25         }
26     }
27
28     public static void main(String[] args) {
29         int i;
30         int[] a = {20,40,30,10,60,50};
31
32         System.out.printf("before sort:");
33         for (i=0; i<a.length; i++){
34             System.out.printf("%d ", a[i]);
35         }
36         System.out.printf("\n");
37
38         selectSort(a, a.length);
39
40         System.out.printf("after  sort:");
41         for (i=0; i<a.length; i++){
42             System.out.printf("%d ", a[i]);
43         }
44         System.out.printf("\n");
45     }
46 }

1 before sort:  20 40 30 10 60 50
2 after  sort:  10 20 30 40 50 60