排序算法之选择排序
罗朝辉（http://www.cppblog.com/kesalin）
转载请注明出处
排序是数据处理中经常使用的一种重要运算，在计算机及其应用系统中，花费在排序上的时间在系统运行时间中占有很大比重，其重要性无需多言。下文将介绍常用的如下排序方法，对它们进行简单的分析和比较，并提供 C 语言实现。
所谓排序，就是要将一堆记录，使之按关键字递增(或递减)次序排列起来。根据排序所采用的策略，可以分为如下五种：
1、插入排序（直接插入排序、希尔排序）
2、交换排序（冒泡排序、快速排序）
3、选择排序（直接选择排序、堆排序）
4、归并排序；
5、桶排序（桶排序，基数排序）；
---------------------------------------------------------------------------------
前面讲了插入，交换排序，下面接着来讲选择排序。
选择排序(Selection Sort)的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。
常用的选择排序方法有直接选择排序和堆排序。
直接选择排序
基本思想：将待排序记录分成有序区和无序区，初始状态下有序区位空，无序区为整个待排序记录。每一趟选择排序就是在无序区中选择最小（或最大）的记录，插入到有序区的最后。如此循环直到无序区为空，完成排序。
代码实现
// 直接选择排序
//
void select_sort(int* array, int length)
{
assert(array && length >= 0);
int i, j, k, temp;
for (i = 1; i < length; ++i) {
k = i;
for (j = i + 1; j < length; ++j) {
if (array[j] < array[k]) {
k = j;
}
}
if (k != i) {
temp = array[i];
array[i] = array[k];
array[k] = temp;
}
}
}
|
时间复杂度分析：
无论待排序记录的初始状态如何，在第 i 趟排序中选出最小关键字的记录，需做 n - i 次比较，因此，总的比较次数为： n * (n - 1) / 2 = 0(n ^ 2)，当待排序记录的初始状态为正序时，移动次数为 0；当初始状态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值 3 * (n-1)。所以，直接选择排序的平均时间复杂度为 0(n ^ 2)。
空间复杂度：
很明显，0(1)。
补充：
直接选择排序是一个就地排序，且是非稳定排序。
堆排序
堆的定义：满足如下约束的 n 个关键字序列 Kl，K2，…，Kn 称为堆，1 ≤ i ≤ n/2，
(1) ki ≤ K2i 且 ki ≤ K2i+1 （小根堆） 或
(2) Ki ≥ K2i 且 ki ≥ K2i+1 （大根堆）
从定义来看，堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在的话)结点的关键字。堆排序就是充分利用堆这种堆顶记录要么是最大的要么是最小的有序性质，每次在堆中选择最大或最小关键字完成排序。堆排序也是选择排序的一种，它比直接选择排序平均效率要高，因为直接选择排序，每次比较之后并没有对比较结果进行保存，导致可能存在重复的比较，而堆则利用其堆性质将比较结果保存在堆中了（非叶子节点的左边孩子一定不大于或不小于比右边的孩子）。
堆排序的关键就在于将待排序记录的建立成堆，建好堆之后，将无序区的堆顶记录（总是无序区的最大或最小）和无序区最后一个记录交换，交换之后，无序区的最后一个记录变成有序区的第一个记录，而无序区新的的堆顶记录不一定满足堆性质了，因而需要将无序区调整而堆。如此循环，直到无序区为空，结束排序。
所以堆排序的主要步骤就分三步：
1，建立初始堆；
2，将无序的堆顶记录与最后一个记录交换，缩小无序区；
3，将交换之后的无序区调整为堆，重复步骤 2。
代码实现：
// 筛选法调整堆，除 [low] 之外，[low] 的两个孩子均已是大根堆
void adjust_heap(int* heap, int low, int high)
{
assert(heap);
#if 1 // 循环实现
int i = low;
int j = 2 * i;
int temp = heap[i];
while (j <= high) {
// 若有两个孩子，j 为孩子中大的那个的下标
if (j < high && heap[j] < heap[j + 1]) {
j = j + 1;
}
// 已是堆
if (temp >= heap[j]) {
break;
}
// 继续筛选
else {
heap[i] = heap[j];
i = j;
j = 2 * i;
}
}
heap[i] = temp;
#else // 递归实现
int i = low;
int j = 2 * i;
int temp = heap[i];
if (j >= high) {
return;
}
// 若有两个孩子，j 为孩子中大的那个的下标
if (j < high && heap[j + 1] > heap[j]) {
j = j + 1;
}
// 已经为堆，无需调整
if (heap[low] >= heap[j]) {
return;
}
heap[i] = heap[j];
heap[j] = temp;
// 调整之后，[j, high] 可能不满足堆了，需继续调整
adjust_heap(heap, j, high);
#endif
}
// 只有一个结点的树是堆，而在完全二叉树中，所有序号 i > n/2 的结点都是叶子，
// 因此以这些结点为根的子树均已是堆。这样，我们只需依次将以序号为
// n/2, n/2 - 1, …, 0 的结点作为根的子树都调整为堆即可。
void build_heap(int* heap, int length)
{
assert(heap && length >= 0);
int i;
for(i = length / 2; i >= 0; --i) {
adjust_heap(heap, i, length - 1);
}
}
// 堆排序
//
void heap_sort(int* array, int length)
{
assert(array && length >= 0);
if (length <= 1) {
return;
}
int i, temp;
// 将 [0, length - 1] 建成初始堆
build_heap(array, length);
// 对当前无序区 [0, i - 1] 进行堆排序，共做 length - 1 趟。
for(i = length - 1; i > 0; --i) {
// 将堆顶和堆中最后一个记录交换
temp = array[0];
array[0] = array[i];
array[i]= temp;
// 将 [0, i - 1] 重新调整为堆，仅有 [0] 可能违反堆性质
adjust_heap(array, 0, i - 1);
}
}
|
时间复杂度分析：
堆排序的时间开销主要由建立初始堆和反复调整堆这两部分的时间开销构成，你可以想象成二叉树的情形。堆排序的平均时间复杂度为O(nlgn)。
空间复杂度分析：
很明显，为 0(1)。
补充：
堆排序是不稳定的就地排序。
=======================================================================================
测试：
在前文《排序算法之插入排序》测试代码的基础上添加两行代码即可：
SortFucntionInfo sort_function_list[] = {
{"直接选择排序", select_sort},
{"堆排序", heap_sort},
{"", NULL}
};
运行结果：
=== 直接选择排序 ===
original: 65 32 49 10 8 72 27 42 18 58 91
sorted: 65 8 10 18 27 32 42 49 58 72 91
original: 10 9 8 7 6 5 4 3 2 1 0
sorted: 10 0 1 2 3 4 5 6 7 8 9
=== 堆排序 ===
original: 65 32 49 10 8 72 27 42 18 58 91
sorted: 8 10 18 27 32 42 49 58 65 72 91
original: 10 9 8 7 6 5 4 3 2 1 0
sorted: 0 1 2 3 4 5 6 7 8 9 10