选择排序

选择排序（Selection sort）是一种不稳定的排序方法，每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。其主要应用于计算机和数学领域。它的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

为什么说选择排序是一种不稳定的排序方法呢？举个例子，序列58529，我们知道第一遍选择第1个元素5会和2交换，变成了28559 ，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。

选择排序的基本方法是：

通过n-i次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1<=i<=n）个记录进行交换。当i=n时，所有记录有序排列。

排序实例：

初始关键字 [49 38 65 97 76 13 27 49]

第一趟排序后 13 [38 65 97 76 49 27 49]

第二趟排序后 13 27 [65 97 76 49 38 49]

第三趟排序后 13 27 38 [97 76 49 65 49]

第四趟排序后 13 27 38 49 [76 97 65 49 ]

第五趟排序后 13 27 38 49 49 [97 65 76]

第六趟排序后 13 27 38 49 49 65 [97 76]

第七趟排序后 13 27 38 49 49 65 76 [97]

最后排序结果 13 27 38 49 49 65 76 97

void select_sort(int *a, int n)

{

          register int i, j, min, t;

         for( i =0; i < n -1; i ++)

         {

                    min = i; //查找最小值

                    for( j = i +1; j < n; j ++)

                        if( a[min] > a[j])

                                min = j; //交换

                  if(min != i)

                  {

                          t = a[min]; a[min] = a[i]; a[i] = t;

                  }

        }

}