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 希尔排序算法总结

同插入排序类似，希尔排序仍然需要一个辅助空间，但其时间复杂度要小一些。有的说法是n^1.3，有的说法是n^1.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 归并排序算法总结

归并排序在没有堆排序那么复杂的构建堆的过程前提下，使其拥有了与堆排序相当的时间复杂度。但其需要分配额外空间去存储拆分出来的元素。

归并排序采用将待排序序列进行拆分，再重组的思想简单而高效，这在很多种排序算法中都可以看到。属于典型的空间换时间。

空间换时间是算法里最重要的思想之一。指的是当内存空间充足的时候，为了追求代码的执行速度，可以舍弃对存储空间的要求，从而追求效率。

十大经典排序算法（C语言实现）(二)