7.4.1简单选择排序

选择排序的基本思想是：每趟（例如第i趟）在后面 n-i+1(i=1,2,...,n-1)个待排序元素中选取关键字最小的元素，

作为有序子序列的第i个元素，直到第n-1趟直到第n-1趟做完，待排序元素只剩下1个，就不用再选了。

选择排序的基本思想：假设排序表为L[1...n]，第i趟排序即从L[i..n]中选择关键字最小的元素与L[i]交换，每一趟排序可以确定一个元素的最终位置，这样经过n-1趟排序就可以使整个排序表有序。

简单选择排序的伪代码：

void SelectSort（Elemtype A[],int n）{
    //对表A进行简单选择排序，A[]从0开始存放元素
    for(i=0;i<n-1;i++){//一共进行n-1趟
        min=i;//记录最小元素位置
        for(j=i+1;j<n;j++){//在A[i...n-1]中选择最小的元素
            if(A[j]<A[min]){
                 min=j;
            }
        }
        if(min!=i){
            swap(A[i],A[min]);//与第i个元素交换
        }
    }
}

简单选择排序算法的性能分析： 空间效率：仅使用常数个辅助单元，故而空间效率为O(1)。 时间效率：简单选择排序过程中，元素移动的操作次数很少，不会超过n-1次，最好情况是移动0次，此时对应的表已经有序。 但元素间比较的次数与序列的初始状态无关，始终是n(n-1)/2次，所以时间复杂度是O(n^2)。 稳定性：在第i趟找到最小元素后，和第i个元素交换，可能会导致第i个元素和其含有相同关键字元素的相对位置发生变化。 例如，表L={2，2,1}，经过一趟排序后，L={1,2,2},最终排序序列也是L={1,2,2},显然，2与2的相对次序已经发生了变化。因此，简单选择排序是一个不稳定的排序过程。