选择排序算法步骤分析

简单选择排序，Simple Selection Sort，用一句简述选择法排序即，每次选择一个最小的元素放在最前面。选择排序的基本思想是，在每一趟排序中，从n-i+1个元素中选择一个最小的元素与i位置上的元素交换，也就是说每次从无序子序列中选择一个最小的元素，并把该元素放在无序子序列的第一个位置上。这样，每趟选择排序需要比较n-i次，只需要交换1次。

第一趟选择排序：

将第1个元素与后面n-1个元素都进行比较 ，选择出一个最小的元素，并把该元素与0位置的元素进行交换，总共需要n-1次比较，1次交换。

经过一趟选择排序后，整个数组的最小元素被放在了0号位置，无序数组的长度只剩下n-1个元素。

第二趟选择排序：

从第二个元素开始的子序列，即（1， 2， 3， 4）的元素，将该无序子序列的第一个元素与后面的每一个元素比较，选择出最小的元素，并和该无序子序列的第一个位置元素进行交换。第二趟选择排序总共进行了n-2次比较，未发生交换（最好的情况是不交换，最差的情况是交换一次）。

经过第二趟选择排序，整个数组最小的两个元素已经按照顺序排在了最前面，有序子序列长度为2，无序子序列长度为n-2。

第n-1趟排序：

第n-1趟排序，要进行n-(n-1)次比较，最多进行一次交换。

选择排序的稳定性分析

假如说有一个序列{5， 6，7， 5， 2， 8 }，第一趟选择排序的时候会把开头的5拿出来和2交换，这样原本在前面的5跑到了另一个5的后面，所以，简单选择排序是不稳定的。

可以看到，原本红色的5在黑色的5前面，经过一趟排序后，红色的5跑去了黑色5的后面。所以，选择排序是不稳定的。

选择排序的代码实现

1. /*交换 i j 位置的元素*/
2. void swap(int array[], int i, int j)
3. {
4.  int temp = array[i];
5.  array[i] = array[j];
6.  array[j] = temp;
7. }
8. 
9. /*选择排序*/
10. void select_sort(int array[], int num)
11. {
12.   int i = 0, j = 0, MinRecord = 0; /*MinRecord用于记录最小元素的位置*/
13.   for (i = 0; i < num - 1; i++)
14.   {
15.     MinRecord = i;
16.     for (j = i + 1; j < num; j++)
17.     {
18.       if (array[j] < array[MinRecord])
19.       {
20.         MinRecord = j; /*更新最小元素下标*/
21.       }
22.     }
23.     swap(array, i, MinRecord);
24.   }
25. }

选择排序的时间复杂度

选择排序总共需要n-1趟排序，第i趟选择排序要进行n-i次比较，至多1次交换。所以最坏的情况下，n-1趟排序总共需要 次比较和n-1次交换（最坏每趟交换一次），时间复杂度为 。

选择排序算法是一种，不稳定的，时间复杂度为 的，简单内排序算法。

（内排序：在内存中完成排序；外排序：排序过程需要内外存交互。）