【数据结构与算法】直接插入排序和希尔排序

引言

进入了初阶数据结构的一个新的主题——排序。所谓排序，就是一串记录，按照其中的某几个或某些关键字的大小（一定的规则），递增或递减排列起来的操作。

排序的稳定性：在一定的规则下，两个值相等的元素，在排序算法处理前后的相对位置是否发生变化，如果相对位置变化，称这种排序算法是稳定的，否则为不稳定的。（这个概念并不影响你对排序的学习）

排序将会是初阶数据结构的收尾模块，在这个模块中，将会带领大家学习七大知名的排序方式。而在本篇博客中，将会介绍其中的两个排序，一个是直接插入排序，另一个则是希尔排序。不过在开始我们排序的讲解之前，先介绍一下我们将要讲的排序算法都有哪些。

没错，我们今天将要处理的就是插入排序模块。

直接插入排序

直接插入排序是一种简单的插入排序法，如果想更好的理解希尔排序，首先需要弄懂直接插入排序，其基本思想是：

把待排序的元素按其大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

很像我们打扑克时，别人给你发一副乱序的牌让你自己手动排序的过程（需要从左往右依次排好顺序）：

直接插入排序核心逻辑：当你插入第 i 个元素时，前面的 array[0],array[1]……array[i-1] 已经排好序，此时让array[i]的数据按array[i-1]……往前的顺序依次比较，找到可插入的位置插入array[i]。原来位置上的元素顺序后移。

这里博主找了一个动图供大家参考理解：

实现直接插入排序

我们可以先来分析一下单趟的直接插入排序，分为两种情况：

1. 单趟排序（单独取一趟排序分析其过程）过程中end走到序列中间即插入，此时tmp小于a[end]

2. [0,end] 区间中元素均小于需插入元素 a[end+1] ，也就是tmp时，单趟排序end走到序列最前面，end == -1

下面是单趟的代码实现：

int end = 3;
int tmp = a[end + 1];
while (end >= 0) {
  if (tmp < a[end]) {
    a[end + 1] = a[end];
    --end;
  }
  else break;
}
a[end + 1] = tmp;

当end的值从1一直排到末尾序列值n - 2时，整个插入排序便完成了。

for循环遍历 end [0, n - 2] ，由于长度为n的数组有效下标最大为n - 1，当end为n - 1时，要插入的元素tmp存的刚好就是a[end + 1]，也就是下标为n - 1的数，同时也就是数组的最后一个值。

直接插入排序代码

// 直接插入排序
void InsertSort(int* a, int n)
{
  for (int i = 0; i < n - 1; i++) {
        // [0,end]区间内有序，end + 1位置是待插入元素
    int end = i;
        // tmp保存的是待插入元素的值
    int tmp = a[end + 1];
    while (end >= 0) {
      if (tmp < a[end]) {
                // 后移元素操作
        a[end + 1] = a[end];
        --end;
      }
      else break;
    }
        //元素的插入
    a[end + 1] = tmp;
  }
}

直接插入排序的特性：

1. 时间复杂度：O(N^2)
2. 空间复杂的：O(1)
3. 元素越接近有序，直接插入排序算法效率越高。
4. 稳定性：稳定
5. 最好情况：有序/接近有序
6. 最坏境况：逆序

当一个序列接近有序时，每一趟直接插入的过程都会变得简单很多，即往前走上几步便能找到比tmp大的值从而跳出单趟循环，在每一次循环的跳出过程中，直接插入排序的时间复杂度可达 O(N)。相反，当一个排序按逆序排列，每一趟都需要将前面的所有元素往后移动一次插入tmp，时间复杂度便成了计算一个等差数列和:

，其时间复杂度显而易见——O(N^2)。

希尔排序

希尔排序也是插入排序的一种，是一个名叫希尔（Donald Shell）的大佬思考推论得出的排序方式，其底层逻辑本质上来说还是直接插入排序。希尔大佬发现了直接插入排序元素越接近有序，直接插入排序算法效率越高这一特点，突发奇想：直接插入排序在非顺序的元素序列中，如果插入元素的值较小，需要从插入尾部一步步移到头部，这个过程中的消耗无疑是巨大的。如果能有一种方式，能将乱序元素序列通过允许远距离的交换元素进行预排列，快速生成一个接近有序的序列，这时候在调用直接插入排序，排序的速率是否会大大提升。

在希尔排序正真被众人所接受之前，这个排序方式也备受质疑，但时间总会给出答案，希尔排序在现今排序大家庭中有着举足轻重的地位。

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序序列中所有元素分成 i 个组，所有距离为 i 的记录分在同一组内，并对每一组内的元素进行直接插入排序。然后，取 i = n / 2 (n为排序序列元素个数) 重复上述分组和排序的工作。当到达 i = 1 时，所有记录在统一组内排好序。

总结一下其过程：

1. 预排序（gap > 1）
2. 直接插入排序(gap == 1)

实现希尔排序

我们可以首先来分析一下单趟的希尔排序。

设 gap == 3 的时候：

每隔3个元素取一个数，最后可以分成gap（gap == 3）组数

这时候，将分好的每一组进行排序，排序方式为直接插入排序。注意，在排序的过程中，不同的组之间的位置不会有交集，元素的位置始终实在自己组内变动的。拿上面举例，gap == 3的第一组数只会在0，3，6，9位置上排序，不会将数字排到其他组的位置上。

这里我们可以复用一下之前选择排序的单趟，只不过++变成了+=gap，--变成了-=gap（因为是按照gap分组间隔排序的，不同组需要排序的元素之间间隔都为gap），下面是排单组（第一组：4 8 3 7）元素时的代码。

int gap = 3;
for (int i = 0; i < n - gap; i += gap) {
  int end = i;
  int tmp = a[end + gap];
  while (end >= 0) {
    if (tmp < a[end]) {
      a[end + gap] = a[end];
      end -= gap;
    }
    else break;
  }
  a[end + gap] = tmp;
}

这时候，想要排分好的多组元素就会容易非常多了，我们再套一层循环，就可以达到排序不同组的效果。

gap = 3;
for (int rem = 0; rem < gap; rem++) {
  for (int i = 0; i < n - gap; i += gap) {
    int end = i;
    int tmp = a[end + gap];
    while (end >= 0) {
      if (tmp < a[end]) {
        a[end + gap] = a[end];
        end -= gap;
      }
      else break;
    }
    a[end + gap] = tmp;
  }
}

这里的代码，就成功的达到帮gap的所有组排序的效果了。现在，实现希尔排序就只差最后一步，就是改变gap的值，让其从n / 2，一直除2直到除到1为止，每得到一次gap都进行一次上面的分组排序运算，下面就是完整的希尔排序代码。

void ShellSort(int* a, int n)
{
  int gap = n;
  while (gap > 1) {
    gap = gap / 2;
    for (int rem = 0; rem < gap; rem++) {
      for (int i = 0; i < n - gap; i += gap) {
        int end = i;
        int tmp = a[end + gap];
        while (end >= 0) {
          if (tmp < a[end]) {
            a[end + gap] = a[end];
            end -= gap;
          }
          else break;
        }
        a[end + gap] = tmp;
      }
    }
  }
}

希尔排序代码

不过，你难道以为希尔排序到这里就结束了？其实这份代码还有优化的空间。比如说，其实你可以省去遍历不同组的for循环，像下面这样。其实本质没什么变化，就是把一组一组拿出来排序的方式改成按顺序在不同组之间换着排。

void ShellSort(int* a, int n)
{
  int gap = n;
  while (gap > 1) {
    gap = gap / 2;
        //去掉遍历不同组的for循环，下面遍历的i+=gap改为i++
    for (int i = 0; i < n - gap; i++) { 
      int end = i;
      int tmp = a[end + gap];
      while (end >= 0) {
        if (tmp < a[end]) {
          a[end + gap] = a[end];
          end -= gap;
        }
        else break;
      }
      a[end + gap] = tmp;
    }
  }
}

你还可以将gap = gap / 2 改成gap = gap / 3 + 1。

void ShellSort(int* a, int n)
{
  int gap = n;
  while (gap > 1) {
    gap = gap / 3 + 1;
    for (int i = 0; i < n - gap; i++) {
      int end = i;
      int tmp = a[end + gap];
      while (end >= 0) {
        if (tmp < a[end]) {
          a[end + gap] = a[end];
          end -= gap;
        }
        else break;
      }
      a[end + gap] = tmp;
    }
  }
}

关于希尔排序的一些特性和问题

不过对于gap的取法其实很多，最初Shell提出gap = gap / 2，后来Knuth提出取 gap = (gap / 3) + 1，还有人提出取奇数或者是互质更好。但无论哪一种主张都没有得到证明。

《数据结构-用面相对象方法与C++描述》--- 殷人昆

希尔排序的特性：

1. 时间复杂度：希尔排序的时间复杂度不好计算，gap的取值方法很多，导致很难去计算，在好些书中给出的希尔排序的时间复杂度都不固定。Knuth经过大量的实验统计，复杂度大概在O(n^1.25)~O(1.6*n^1.25)之间。现代更高效的增量序列可以使希尔排序达到O(N*logN)的复杂度。
2. 希尔排序是对直接插入排序的优化。
3. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。整体而言，可以达到优化的效果。
4. 稳定性：不稳定

《数据结构(C语言版)》--- 严蔚敏

测试计算效果

clock()函数是<time.h>头文件中的一个函数，用来返回程序启动到函数调用之间的CPU时钟周期数。这个主可以用来帮助我们衡量程序或程序某个部分的性能。

我们可以计算对比一下本篇博客两个排序方式占用的CPU时间

void TestOP()
{
  srand(time(0));
  const int N = 100000;
  int* a1 = (int*)malloc(sizeof(int) * N);
  int* a2 = (int*)malloc(sizeof(int) * N);
  for (int i = 0; i < N; ++i)
  {
    a1[i] = rand();
    a2[i] = a1[i];
  }
  int begin1 = clock();
  InsertSort(a1, N);
  int end1 = clock();
  int begin2 = clock();
  ShellSort(a2, N);
  int end2 = clock();
  printf("InsertSort:%d\n", end1 - begin1);
  printf("ShellSort:%d\n", end2 - begin2);
  
}

上面这段代码的功能是生成十万个随机数，分别用希尔排序和直接插入排序去排列，同时用clock记录所消耗的时间，打印结果。

我们可以发现希尔排序相比于直接插入排序的性能提升了很多。

结语

本篇博客的内容到这里就结束了，插入排序的序列元素越接近有序，直接插入排序算法效率越高。希尔正是发现了其特点，引入“增量”的概念，允许排序中远距离的交换元素，快速达到预排序效果，大幅度提高了对大规模数据集的排序效率。直接插入排序和希尔排序在计算机科学的排序算法领域中占有重要地位。在掌握其中规律之后，相信你对排序一定有了更加深入的理解。