4 希尔排序
希尔排序是D.L.Shell于1959年提出的一种排序算法，希尔排序是第一批突破平方阶时间复杂度的算法之一。
4.1 希尔排序的代码实现
在希尔排序中，需要设置一个增量，然后使其逐渐较小到1，从而顺利完成排序任务。具体实现的代码如下。
#include <stdio.h> #define MAXSIZE 10000 #define TRUE 1 #define FALSE 0 typedef struct { int r[MAXSIZE + 1]; int length; }sqList; void swap(sqList* L, int i, int j) { int temp = L->r[i]; L->r[i] = L->r[j]; L->r[j] = temp; } void ShellSort(sqList *L) { int i, j, k = 0; int increment = L->length; do { increment = increment / 3 + 1; for (i = increment + 1; i <= L->length; i++) { if (L->r[i] < L->r[i - increment]) { L->r[0] = L->r[i]; for (j = i - increment; j > 0 && L->r[0] < L->r[j]; j -= increment) L->r[j + increment] = L->r[j]; L->r[j + increment] = L->r[0]; } } } while (increment > 1); } int main() { sqList test = {{0,9,1,5,8,3,7,4,6,2}, 9}; ShellSort(&test); for (int i = 0; i <= test.length; i++) printf("%d\t", test.r[i]); return 0; }
从代码中可以看出，希尔排序与插入排序有相似之处，又或者说，希尔排序是一种特殊的插入排序，与插入排序相比，希尔排序是每间隔几个数进行比较大小的，然后每循环一次，间隔减一，直到为0，完成排序。如下图所示：
4.2 希尔排序算法总结
同插入排序类似，希尔排序仍然需要一个辅助空间，但其时间复杂度要小一些。有的说法是n1.3，有的说法是n1.5。但肯定优于前三种排序算法。
5 堆排序
堆排序是利用推进行排序的一种算法。
堆排序的基本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走，然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值。如此反复执行，便能得到一个有序序列了。
5.1 堆简介
堆（数据结构）是具有下列性质的完全二叉树；每个结点的值都大于或者等于其左右孩子结点的值，成为大顶堆；或者每个结点的值都小于或者等于其左右孩子结点的值，称为小顶堆。
从这里也可以看出，推是一种特殊的二叉树。此次排序用的堆是大顶堆。
5.2 堆排序的代码实现
推排序的代码实现如下所示。
#include <stdio.h> #define MAXSIZE 10000 #define TRUE 1 #define FALSE 0 typedef struct { int r[MAXSIZE + 1]; int length; }sqList; void swap(sqList* L, int i, int j) { int temp = L->r[i]; L->r[i] = L->r[j]; L->r[j] = temp; } //本函数调整L->r[s]的关键字，使L->r[s..m]成为一个大顶堆 void HeapAdjust(sqList *L, int s,int m) { int temp, j; temp = L->r[s]; for (j = 2 * s; j <= m; j *= 2) //沿关键字较大的孩子结点向下筛选 { if (j < m && L->r[j] < L->r[j + 1]) //左孩子的值应小于右孩子 ++j; //j的位置变为右孩子，也就是较大值的位置 if (temp >= L->r[j]) //当前结点的值应该大于等于孩子结点的值 break; L->r[s] = L->r[j]; s = j; } L->r[s] = temp; } void HeapSort(sqList *L) { int i; //构建大顶堆 for (i = L->length / 2; i > 0; i--) HeapAdjust(L, i, L->length); //排序 for (i = L->length; i > 1; i--) { //将堆顶记录和当前未经排序子序列最后一次记录交换 swap(L, 1, i); //将其重新调整为大顶堆 HeapAdjust(L, 1 ,i - 1); } } int main() { sqList test = { {0,50,10,90,30,70,40,80,60,20}, 9 }; HeapSort(&test); for (int i = 0; i <= test.length; i++) printf("%d\t", test.r[i]); return 0; }
堆排序的算法有点难理解，大致过程是这样的。
- 构建大顶堆；
- 将大顶堆上的根节点（最大值）取出，然后调整大顶堆，这样就可以取出次大值，直到将所有值取出。
下面我们借助图来理解整个堆排序的详细过程。
5.2.1 堆的构建过程
如上图所示，绿色为非叶子结点，也就是调用HeapAdjust的时候，传的第二个参数所指的位置。先调整编号4为根节点的子树。调整过程大概如下：
if (j < m && L->r[j] < L->r[j + 1]) //左孩子的值应小于右孩子 ++j; //j的位置变为右孩子，也就是较大值的位置
以上语句就是检查左子树是否小于右子树的，若小于则指向右孩子结点。显然此时不满足，继续往下运行（也就是说，j指向了较大值所在的孩子结点）；
if (temp >= L->r[j]) //当前结点的值应该大于等于孩子结点的值 break;
若根节点大于孩子结点，则满足要求，运行结束。此时显然不满足。继续往下运行；
L->r[s] = L->r[j]; s = j;
将较大的值赋予根节点（局部）；继续往下运行；j = 16，不满足条件，跳出循环。继续往下运行；
L->r[s] = temp; //插入新值
也就是L->r[8] = 3；此次调用执行结束。
第二次和第三次调用于此类似，如下所示：
因为3号节点本身就符合要求，因此第二次调用不做改变。
第四次调用稍微麻烦一些：
因为这里做了两次循环，且对节点进行了重新赋值。至此，大顶堆构建结束。
5.2.2 堆排序过程
如果将核心思想看懂了，堆的排序过程就变得容易了（图片仅用来说明第一次HeapAdjust函数调用的运行过程，剩下的可自己推理）。如下图所示：
首先，整个大顶堆的根节点肯定是最大值，所以将其放在最后，并对其他部分进行调整（排序），再将值逐个取出，即可完成排序过程。
5.3 堆排序算法总结
总体来说，堆排序的时间复杂度为O(nlongn)。这在性能上显然要远远好过冒泡，选择，插入排序算法了。而且空间复杂度也比较低。
另外，构建堆比较麻烦，因此，它并不合适待排序序列个数比较少的情况。
6 归并排序
前面讲了归并排序，不过堆的构建分身比较麻烦，有没有排序快并且不用这么麻烦的算法呢？归并排序就是一个。
归并排序，就是利用归并的思想实现的排序方法。基本原理是，假设初始记录含有n个记录，则可以看作n个有序的子序列，每个子序列的长度为1，然后两两归并，得到长度为2或者1的子序列；两两归并，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法成为2路归并排序。
有2路归并，自然就有多路归并，本文仅介绍2路归并排序算法。
6.1 归并排序的代码实现
归并排序的实现代码如下。
#include <stdio.h> #define MAXSIZE 10000 #define TRUE 1 #define FALSE 0 typedef struct { int r[MAXSIZE + 1]; int length; }sqList; void Merge(int SR[], int TR[], int i, int m, int n) { int j, k, l; //将SR中的记录由小到大地并入TR for (j = m + 1, k = i; i <= m && j <= n; k++) { //哪个值小就归并哪个值，直至归并完成 if (SR[i] < SR[j]) TR[k] = SR[i++]; else TR[k] = SR[j++]; } //将剩余的SR[i,m]区间的数值复制到TR if (i <= m) { for (l = 0; l <= m - i; l++) TR[k + l] = SR[i + l]; } //将剩余的SR[j,n]区间的数值复制到TR if (j <= n) { for (l = 0; l <= n - j; l++) TR[k + l] = SR[j + l]; } } void Msort(int SR[], int TR1[], int s, int t) { int m; int TR2[MAXSIZE + 1]; if (s == t) TR1[s] = SR[s]; else { m = (s + t) / 2; //将SR[s,t]区间平分为[s,m]和[m+1,t] Msort(SR, TR2, s, m); //递归地将SR[s,m]归并为有序的TR2[s,m] Msort(SR, TR2, m + 1, t); //递归地将SR[m+1，t]归并为有序的TR2[m+1,t] Merge(TR2, TR1, s, m, t); //将TR2[s,m]和TR2[m+1,t]归并到TR1[s,t] } } void MergeSort(sqList* L) { Msort(L->r, L->r, 0, L->length - 1); } int main() { sqList test = { {50,10,90,30,70,40,80,60,20}, 9 }; MergeSort(&test); for (int i = 0; i < test.length; i++) printf("%d\t", test.r[i]); return 0; }
归并排序的基本过程如下图所示：
从上图可以发现，归并排序分成两个过程，分别是拆分和合并，在合并的过程中逐步将数据进行排序。
归并排序程序的主体部分如下：
void Msort(int SR[], int TR1[], int s, int t) { int m; int TR2[MAXSIZE + 1]; if (s == t) TR1[s] = SR[s]; else { m = (s + t) / 2; //将SR[s,t]区间平分为[s,m]和[m+1,t] Msort(SR, TR2, s, m); //递归地将SR[s,m]归并为有序的TR2[s,m] Msort(SR, TR2, m + 1, t); //递归地将SR[m+1，t]归并为有序的TR2[m+1,t] Merge(TR2, TR1, s, m, t); //将TR2[s,m]和TR2[m+1,t]归并到TR1[s,t] } }
从代码中可以发现，该程序采用了递归，每次都可以将区间分成两半，而Merge函数并未参与到“递”的过程，在此拆分过程中，递归的结束条件是s==t，也就是该区间无法再次拆分的时候，“递”过程结束。
而在“归”的过程中，就有了Merge函数的参与，而“归”是“递”的逆过程，所以此时究竟应该合并哪几个数，在“递”的过程中就已经决定了，只需逆向执行并排序即可。
Merge函数也很好理解，将TR2[s,m]和TR2[m+1,t]归并到TR1[s,t]，哪个值小就先放哪个，并将访问位置后移，如果有一个区间的值提前归并完成，则结束循环，然后将剩下的值复制过去即可。
6.2 归并排序算法总结
归并排序在没有堆排序那么复杂的构建堆的过程前提下，使其拥有了与堆排序相当的时间复杂度。但其需要分配额外空间去存储拆分出来的元素。
归并排序采用将待排序序列进行拆分，再重组的思想简单而高效，这在很多种排序算法中都可以看到。属于典型的空间换时间。
空间换时间是算法里最重要的思想之一。指的是当内存空间充足的时候，为了追求代码的执行速度，可以舍弃对存储空间的要求，从而追求效率。
