内排序算法之 —— 选择排序

选择排序的基本方法是：每步从待排序的元素中选出关键字最小的元素，顺序放在已排序的元素序列的最后，直到全部排完为止。本次介绍简单选择排序和堆排序。

简单选择排序

简单选择排序的过程是：假设元素存放在 R[0..n−1] 之中，其中 R[0..i−1] 是有序区， R[i..n−1] 是无序区，且有序区的所有关键字均小于无序区的所有关键字。需将 R[i] 添加到 R[0..i−1] 之中，使 R[0..i] 成为有序的。这里每一趟从排序无序区 R[i..n−1] 中选择一个最小关键字的元素 R[k] ,将其与 R[i] 进行交换，显然 R[0..i] 变成新的有序区了。

C++代码示例：

void easySelectSort(vector<int> R,int n) { int k,temp; for (int i = 0; i < n - 1; i ++) { k = i; for (int j = i + 1; j < n; j ++) { // 从无序区选最小元素 if (R[j] < R[k]) { k = j; // 用 k 指出每趟在无序区的最小元素 } if (i != k) { temp = R[i]; // 将R[k]与R[i]交换 R[i] = R[k]; R[k] = temp; } } } }

简单选择排序算法的性能如下表所示：

时间复杂度空间复杂度稳定性复杂性平均情况: O(n2) O(1)不稳定简单最坏情况: O(n2) \\\最好情况: O(n2) \\\

从上表可以看出，当初始数据序列正序时，也需要进行相应的比较，不会减少比较的次数，所以简单选择排序算法的效率与初始数据的顺序性无关。

简单选择排序算法中产生的有序区一定是全局有序的，也就是说，有序区中的所有元素的关键字一定大于或小于无序区中所有元素的关键字，这样每一趟排序都会讲一个元素放置到最终的位置上（即归位一个元素）。

堆排序

关于堆排序详细算法过程，这里不再做详细的总结，笔者给出一个传送门：堆排序算法详解。个人认为这篇文章讲得非常清楚得当，难以超越。

这里给出堆排序的性能表格：

时间复杂度空间复杂度稳定性复杂性平均情况: O(nlog2n) O(1)不稳定较复杂最坏情况: O(nlog2n) \\\最好情况: O(nlog2n) \\\

堆排序算法中产生的有序区一定是全局有序的，也就是说，有序区中的所有元素的关键字一定大于或小于无序区中所有元素的关键字，这样每一趟排序都会将一个元素放置到最终的位置上（即归位一个元素）。