理论基础 —— 排序 —— 直接选择排序

【概述】

直接选择排序又称简单选择排序，是一种不稳定的排序方法，其是选择排序中最简单一种，其基本思想是：第 i 趟排序再待排序序列 a[i]~a[n] 中选取关键码最小的记录，并和第 i 个记录交换作为有序序列的第 i 个记录。

其实现利用双重循环，外层 i 控制当前序列最小值存放的数组元素位置，内层循环 j 控制从 i+1 到 n 序列中选择最小的元素所在位置 k

【排序过程】

1.排序过程

具体的排序过程为：

1. 将整个记录序列划分为有序区和无序区，初始时有序区为空，无序区含有待排序的所有记录
2. 在无序区选择关键码最小的记录，将其与无序区中的第一个元，使得有序区扩展一个记录，同时无序区减少了一个记录
3. 不断重复步骤 2，直到无序区只剩下一个记录为止

2.实例

 初始关键字：『 8，5，2，6，9，3，1，4，0，7 』

 第一趟排序后：0，『5，2，6，9，3，1，4，8，7』

 第二趟排序后：0，1，『2，6，9，3，5，4，8，7』

 第三趟排序后：0，1，2，『6，9，3，5，4，8，7』

 第四趟排序后：0，1，2，3，『9，6，5，4，8，7』

 第五趟排序后：0，1，2，3，4，『6，5，9，8，7』

 第六趟排序后：0，1，2，3，4，5，『6，9，8，7』

 第七趟排序后：0，1，2，3，4，5，6，『9，8，7』

 第八趟排序后：0，1，2，3，4，5，6，7，『8，9』

 第九趟排序后：0，1，2，3，4，5，6，7，8，『9』

 结果：          『 0，1，2，3，4，5，6，7，8，9 』

     排序过程                    宏观过程

【时空复杂度分析】

容易看出，待排序序列为正序，移动次数最小，为 0 次；待排序序列为逆序时，移动次数最多，为 3(n-1) 次。

但无论记录的初始排列如何，关键码的比较次数相同，第 i 趟排序需进行 n-i 次关键码的比较，而简单选择排序需要进行 n-1 趟排序，因此，总的比较次数为 O(n^2)

故而，无论是最优、最差时间复杂度，还是平均时间复杂度，均为 O(n^2)

对于空间复杂度来说，简单选择排序仅需一个存储空间用于记录交换的暂存单元，即空间复杂度为 O(1)

【源程序】

void selectSort(int a[],int n){
    for(int i=1;i<=n-1;i++){//进行n-1趟选择
        int index=i;
        for(int j=i+1;j<=n;j++)//从无序区选取最小的记录
            if(a[index]>a[j])
                index=j;
        if(index!=i)
            swap(a[i],a[index]);
    }
}