【概述】
直接选择排序又称简单选择排序，是一种不稳定的排序方法，其是选择排序中最简单一种，其基本思想是：第 i 趟排序再待排序序列 a[i]~a[n] 中选取关键码最小的记录，并和第 i 个记录交换作为有序序列的第 i 个记录。
其实现利用双重循环，外层 i 控制当前序列最小值存放的数组元素位置，内层循环 j 控制从 i+1 到 n 序列中选择最小的元素所在位置 k
【排序过程】
1.排序过程
具体的排序过程为：
- 将整个记录序列划分为有序区和无序区，初始时有序区为空，无序区含有待排序的所有记录
- 在无序区选择关键码最小的记录，将其与无序区中的第一个元，使得有序区扩展一个记录，同时无序区减少了一个记录
- 不断重复步骤 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]); } }
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/232085.html原文链接：https://javaforall.net
