(66)王道数据结构-简单选择排序

基本概念

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

代码逻辑

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

性能分析

时间复杂度

简单选择排序过程中，元素移动的操作次数很少，不会超过3(n- 1)次，最好的情况是移动0次，此时对应的表已经有序；但元素间比较的次数与序列的初始状态无关，始终是n(n-1)/2次，所以时间复杂度始终是O(n^2)

空间复杂度

仅使用常数个辅助单元，故空间效率为O(1)

稳定性

在第i趟找到最小元素后，和第i个元素交换，可能会导致第i个元素与其含有相同关键字元素的相对位置发生改变。例如，表L={2, 2,1 }，经过一趟排序后L= {1, 2, 2}， 最终排序序列也是L= {1, 2, 2}，显然，2与2的相对次序已发生变化。因此，简单选择排序是一种不稳定的排序方法