直接插入排序、折半插入排序、2路插入排序、希尔排序

本篇是排序专栏博客的第一篇，主要探讨以 “插入” 为核心思想的排序算法该如何实现

---

---

一、前言

所谓插入排序就是将数据整体的一部分独立看作有序，另一部分看作无序，然后将无序区间的数据一个一个地插入到有序区间中，并且在插入过程中始终保持有序区间有序的一种算法。

或许你会觉得很少见，但实际日常生活中，我们玩扑克牌游戏时就不自觉应用了这种思想。

既然插入排序要不断将数据插入有序区间中，那关键的地方就在于，如何在有序区间中找到一个合适的位置给新的数据。因此，根据查找插入位置的方法不同就衍生出了多种插入排序。

• 按顺序法查找插入位置的——直接插入排序。
• 按折半法（也叫二分法）查找插入位置的——折半插入排序。
• 通过缩小增量进行分组预排序的——希尔排序。
• 通过辅助空间减少挪动次数的——2路排序。

接下来就分别探讨这四个插入思想的排序算法如何实现。

二、直接插入排序

1. 算法思想与操作分析

思想：

假设我们现在要对 n 个数据排序：

1. 将第1个数据作为有序区间，后面的n-1个数据作为无序区间，然后将无序区间的首个数据插入到有序区间中，这个操作要进行n-1次。
2. 直接插入排序，又称顺序插入排序，因此，做法就是定义一个索引end指向有序区间的最后一个数据，每次插入操作都从后往前遍历有序区间，找到合适的插入位置。
3. 重复步骤 2，直到无序序列数据个数为 0 。

图解分析基本操作：

有一组数据如下，我们现在需要将其从小到大排序。

1. 首先将数据划分出有序区间和无序区间。

2. 定义索引end指向有序区间的末个数据，用于遍历有序区间；
   定义索引i指向无序区间的首个数据，遍历无序区间进行每一趟的数据插入。

3. a[end] > a[i]，说明 1 应该插入到 9 的前面，但是 9 的前面已经不是数组的有效空间。
   因此，9 要往后挪动一位，但是这样又会把a[i]给覆盖了，所以挪动前需要定义一个临时变量temp来保存a[i]的内容。
   然后--end（看到这里你会惊讶的说，end 为什么要 -1，减完它就越界了啊，这样做是不是错了，别急，先记住这里，后面会一起解释）。

4. 这样操作，待插入数据 1 就可以在 9 前面插入了，因为此时 end 的值为 -1，所以插入操作为a[end + 1] = temp。

5. 此时有序区间数据个数增加1，无序区间个数减少1，索引变量end、i也要随着更新，更新操作为i++、end = i - 1；

6. 第二轮待插入数据为 2，然后我们再重复上面的步骤 2、3、4、5；
   废话不多说，直接上图（为了节省画图压力个人这里就压缩成两张图了）；

7. 排序的步骤就演示到这里，接下来的操作无非就是重复步骤 2、3、5 的操作罢了，所以这里主要是总结一下排序过程的注意点。
   从 3、6 这两点的图中我们可以总结出，找到插入位置的情况有两种：

   1. 索引变量end遍历完有序区间，即 end == -1；

   2. 索引变量end未遍历完有序区间，但它指向的值a[end] < temp；

   这两种情况下，插入位置都在end的下一个位置。

2. 代码实现

version 1

typedef int DataType;
void InsertSort1(DataType* a, int n)
{// 待插入数据，即区间[1, n-1]int i = 0;for (i = 1; i < n; i++){// 单趟插入（默认有序区间[0, n-2]）int temp = a[i];int end = i - 1;// 找到合适位置的条件有2// 条件1：end == -1，退出循环while (end >= 0){if (a[end] > temp){a[end + 1] = a[end];--end;}else{// 条件2：a[end] <= temp// 按道理来说，这里应该进行插入操作的// 但是根据上面分析，条件1、2的插入操作都是一致，于是都放在循环外了break;}}a[end + 1] = temp;}
}

version 2

也许你会感觉，虽然上面的方法已经能够完成算法了，但是，索引变量end在遍历过程中毕竟越界了，有种不安全的感觉，这里提供了第二种实现思路。

typedef int DataType;
void InsertSort2(DataType* a, int n)
{// while --> for，结构紧凑，不会越界int i = 0;for (int i = 1; i < n; i++){int temp = a[i];int pos = 0;// 这里就很明显地看到找到合适位置有两个条件了for (pos = i; pos > 0 && a[pos - 1] > temp; pos--){a[pos] = a[pos - 1];}// 当退出循环后，pos指向的位置就是插入位置a[pos] = temp;}
}

3. 复杂度分析

时间复杂度

直接插入排序是一种受序列初始排布状态影响的排序算法。

我们来对比以下两组数据排升序的性能差别：

1. 第一组数据{10, 9, 8, 7, 6, 5, 4, 3, 2, 1}

2. 第一组数据{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

从上面两组数据中，我们不难看出，如果数据越接近于有序那么直接插入排序的效率越高，反之，效率越差，时间复杂度越高。
虽然我们希望每次排序时都出现最好情况，但是很遗憾，时间复杂度是一个悲观预期，它以最坏情况为标准。
因此，结论是：直接插入排序的时间复杂度是O(N^2)。

空间复杂度

空间复杂度取决算法实现过程中额外空间消耗的大小，像temp、end、i、pos这样的，常数个变量的开销的空间复杂度是O(1)。

三、折半插入排序

1. 算法思想与操作分析

思想：

同样，我们现在仍要对 n 个数据排序：

1. 将第1个数据作为有序区间，后面的n-1个数据作为无序区间，然后将无序区间的首个数据插入到有序区间中，这个操作要进行n-1次，直到无序区间数据个位数为 0。
2. 相比较于边比较边挪动数据的直接插入排序，折半插入排序先用二分法找到插入位置，然后再挪动数据
3. 最后将数据插入到合适的位置。

图解分析基本操作：

1. 首先将数据划分出有序区间和无序区间。
   （为了方便，折半插入排序仍旧采用与前面相同的一组数据）

2. 定义用于二分查找插入位置的 3 个索引变量left、mid、right；
   定义用于遍历控制无序区间数据插入的循环迭代变量i。

设计好变量后，接下来进行第一趟的插入，先说明一下变量的初始化：
首先是循环迭代变量i，它承担的任务和前面相同，从下标为 1 开始遍历完无序区间；
其次是折半查找的三个变量：

1. left指向有序区间的最左端，即初始化为left = 0；
2. right指向有序区间最右端，即初始化为right = i - 1；
3. mid指向当前区间的中间数据，即初始化为mid = (left + right) / 2；

3. 折半插入排序仅仅只是改变了插入位置的查找方式，数据挪动过程中仍会对待插入数据（a[i]）进行覆盖，因此挪动前要将a[i]用临时变量temp保存；
   然后，此时的a[mid] > temp，说明插入位置在a[mid]的左边，然后更新查找的边界，操作为right = mid - 1；
   更新完边界之后，我们 需要判断一下是否满足条件left <= right，如果满足，说明明仍要继续查找，当right < left时，left指向的位置就是插入位置，从left开始到有序区间的最右端的数据都要向后挪动一位（temp的作用就在这里体现了）；

4. 第一轮插入完毕，接下来进行第二轮插入
   首先要对变量left、mid、right、i分别进行更新

++i，使变量i重新指向无序区间的首个数据；
left = 0，使变量left重新指向有序区间左边界；
right = i - 1，使变量right重新指向有序区间的右边界；
mid = (left + right) / 2，使变量mid重新指向当前查找区间的中间值；

5. ①临时变量temp保存a[i]；
   ②比较得a[mid] < temp，说明插入位置在右半区间 [mid+1, right]，更新查找区间的左边界，即left = mid + 1，此时left < right，查找继续；
   ③边界发生变化，更新mid = (left + right) / 2；
   ④比较得temp < a[mid]，说明插入位置在左半区间 [left, mid-1]，更新查找区间的右边界边界，即right = mid - 1，此时left > right，查找停止；
   ⑤此时left指向的位置就是查找位置；

6. ①有序区间内从left开始的数据都向后挪动一位；
   ②将temp插入到left指向的位置；

7. 剩余数据的插入与上面的大同小异，唯一的不同点就是随着有序区间数据的增多，区间更新的次数也随之增加而已，这里就不再过多演示

2. 代码实现

typedef int DataType;
void BinaryInsertSort(DataType* a, int n)
{int i = 0;for (i = 1; i < n; i++)		// 无序区间[1, n-1]，n-1 次插入操作 {int temp = a[i];		// 临时变量保存a[i]int left = 0;int right = i - 1;// 二分查找插入位置while (left <= right){int mid = (left + right) / 2;if (a[mid] <= temp)	// 插入位置在右半区间{left = mid + 1;	// 左边界更新}else				// 插入位置在左半区间{right = mid - 1;// 右边界更新}}//数据挪动int j = 0;for (j = i; j > left; j--){a[j] = a[j - 1];}// 数据插入a[left] = temp;}
}

3. 复杂度分析

时间复杂度

折半插入排序不同于直接插入排序的边比较边挪数据，该算法将比较和挪动的捆绑关系解放，通过减少比较次数来进行一个小幅度的优化，但是数据挪动的次数相较于直接插入排序是没有优化的。
在最坏情况下，比如{10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }等
插入第1个数据，挪动1次；
插入第2个数据，挪动2次；
……
插入第10个数据，挪动10次；
……以此类推：
插入第n-1个数据，挪动n-1次；

在最坏情况下，虽然比较次数有所减少，但数据挪动次数却没有减少。
因此，结论是：折半插入排序的时间复杂度是O(N^2)。

空间复杂度

空间复杂度取决算法实现过程中额外空间消耗的大小，像temp、end、i、pos这样的，常数个变量的开销的空间复杂度是O(1)。

四、2路插入排序

前面提到过，折半插入排序是在直接插入排序的基础上，实现了比较次数和数据挪动之间的关系解绑，而在接下来要探讨的2路插入排序则是在直接插入排序上尽可能减少数据的挪动。

1. 算法思想与操作分析

思想：

2路插入排序是一种典型的通过牺牲空间换取时间的算法，先开辟与原数据等长的数据空间，然后遍历原数据，在辅助空间中排好序然后拷贝回源数据空间。

图解思想和基本操作：

1. 第一步:
   ①开辟等长的辅助排序空间，初始化为0，将源数组第一个数据拷贝过去；
   ②定义索引变量head，tail，指向assist数组的第一个值；
   ③定义循环变量i，用于遍历源数组进行数据插入。

2. 第二步：
   现在数据分成三种情况
   ①a[i] < assist[head]，a[i] 插入到 head 的前一个位置，更新 head；
   ②assist[tail] <= a[i]，a[i] 插入到 tail 的后一个位置，更新 tail；
   ③其余情况统一按直接插入排序处理；

接下来插入第一个数据：

a[i] (== 6) < assist[head]，属于第一种情况，head向前挪动一个位置，操作为head = (head - 1 + n) % n

这个就是这个算法的最核心之处了，如果你学过循环队列，那这个会很好理解，如果没有了解过这方面的知识，你可以把数组想象成一个首尾相接的圆

接下来插入第二个数据：

assist[head] < a[i] (== 7) < assist[tail]，属于第三种情况将a[i]插入有序区间 [head, tail]。

规定操作如下：

先让tail向后移动一个位置，再定义变量end控制数据挪动；

只有遇到 (end 的前一个数据) < a[i] 才停止挪动数据；

当 end 停止移动时，end指向的位置就是插入位置；

一般来说，tail 向后移动不会出现越界的情况，但为了代码的一致，统一对索引变量的移动进行取余操作；
当索引变量向后移动时，不再是++，而是变量 = (变量 + 1) % n
当索引变量向前移动时，不再是–，而是变量 = (变量 - 1 + n) % n

tail = (tail + 1) % n，向后移动一位。
定义变量end = tail，将end的前一个数据向后挪动一位，再更新end，即
assist[end] = assist[(end - 1 + n) % n]
end = (end - 1 + n) % n。
当end = 0 时，end 的前一个位置的值为6 < a[i] (== 7)，停止挪动、插入数据。

接下来插入第三个数据：

此时assist[tail] <= a[i] (== 7) ，属于第一种情况将a[i]插入tail的后一个位置。
操作为：
tail = (tail + 1) % n
assist[tail] = a[i];

三次插入操作分别讲述了算法操作过程中会遇到三种情况，图解分析就到此为止，就下来就是代码实现。

2. 代码实现

typedef int Datatype;
void TwoWayInsert(DataType* a, int n)
{// 辅助空间int* assist = (int*)calloc(n, sizeof(DataType));if (assist == NULL){printf("calloc failed\n");exit(-1);}assist[0] = a[0];// 索引变量，控制插入int head = 0, tail = 0;int i = 0;for (i = 1; i < n; i++){// < assist[head] 放头前if (assist[head] > a[i]){assist[head = (head - 1 + n) % n] = a[i];}// >= assist[tail] 放尾后else if (assist[tail] <= a[i]){assist[tail = (tail + 1) % n] = a[i];}// 其余统一按直接插入排序处理else{int end = ++tail;while (1){assist[end] = assist[(end - 1 + n) % n];end = (end - 1 + n) % n;// end前一个位置比a[i]小就退出if (assist[(end - 1 + n) % n] <= a[i]){break;}}assist[end] = a[i];}}for (i = 0; i < n; i++){a[i] = assist[head];head = (head + 1) % n;}free(assist);
}

3. 复杂度分析

时间复杂度

取决于移动元素和比较元素。
最坏情况：
放第一个元素，移动0，比较0，
放第二个元素，移动0，比较1，
放第三个元素，挪动1，比较2，
放第四个元素，挪动2，比较3，
放第五个元素，挪动3，比较4
…
放第n个元素，挪动(n-2)，比较(n-1)
比较次数之和大于挪动次数之和，以比较为标准，则排序部分的时间复杂度为O(N^2)。
最后还要将辅助空间数据拷贝回源数据，该操作复杂度为O(N)。
因此，结论为2路插入排序的时间复杂度为O(N^2)。

空间复杂度

算法在执行过程中，额外的空间开销取决于源数据个数，总的空间开销为 未知数N + 常数个变量。
因此，结论为2路插入排序的时间复杂度为O(N)。

五、希尔排序

前面提到过，“对于直接插入排序，如果数据越接近于有序，那么它的排序效率越高”，但是，现实中的数据不总是接近于有序。

那么如何使数据更加接近于有序呢？

1959年，有一个名叫 DL．Shell 提出了一种解决方法，对直接插入排序进行了大幅度的性能优化，最后，这个方法被以它的提出者来命名，叫做 “希尔排序”，这就是希尔排序的由来。

1. 算法思想与操作分析

思想：

希尔排序，又叫做 “缩小增量排序”，“分组插入排序”。

它的基本思想如下：

1. 将整个待排序数据序列以某个间隔(假设为gap)作为一组，划分成不同的子区间，分别进行直接插入排序；
2. 不断缩小gap、重新划分子区间、分别进行直接插入排序；
3. 直到整体数据接近于有序，再对全体元素进行一次直接插入排序。

图解分析基本操作：

以下为对一组简单的数据进行希尔排序的过程：

图中很清晰的展示了希尔排序是如何进行的：

1. 定义一个增量gap，设置初始值为n/2，将数据分为gap组，分别对gap组数据进行直接插入排序；
2. gap /= 2，缩小增量，再对新划分的gap组数据进行直接插入排序；
3. 重复步骤 2，如果gap > 1，进行的是预排序，目的是将较大的数据放到后面，较小的数据挪到前面，使数据更接近于有序；如果gap = 1，此时数据已经基本接近于有序，对数据整体进行一次直接插入排序，使数据完全有序。

2. 代码实现

version 1

根据上面基本操作分析，我们来将代码进行实现，实现过程中，个人建议从小到大写，即先写好对小组的直接插入排序，再用外循环控制增量gap的缩小。

对分组进行直接插入排序时要注意gap。

typedef int DataType;
void ShellSort(DataType* a, int left, int right)
{int gap = right;while (gap > 1){// 当 gap > 1 时进行的就是预排序// 当 gap = 1 时进行的就是直接插入排序gap /= 2;int i = 0;// 对分别划分出的gap组数据进行直接插入排序for (i = 0; i < gap; i++){int end = i;// 每组数据中，定义变量end来遍历有序区间，进行数据挪动// 注意间隔为gap，不再是1for (end = i; end < right - gap; end += gap){// 临时变量temp保存无序区间的第一个值int temp = a[end + gap];while (end >= 0){if (a[end] > temp){a[end + gap] = a[end];}else{break;}end -= gap;}a[end + gap] = temp;}}}
}

这样，代码就成功实现出来了，但是，这样的代码就是最优的吗？

我们接着往下看。

version 2

有人经过观察发现，下面两个循环在写法上可以进行合二为一。

何出此言？

typedef int DataType;
void ShellSort(DataType* a, int left, int right)
{int gap = right;while (gap > 1){// 当 gap > 1 时进行的就是预排序// 当 gap = 1 时进行的就是直接插入排序gap /= 2;int end = 0;// 对gap组进行多组并排for (end = 0; end < right - gap; end++){// 临时变量temp保存无序区间第一个值int temp = a[end + gap];while (end >= 0){if (a[end] > temp){a[end + gap] = a[end];}else{break;}end -= gap;}a[end + gap] = temp;}}
}

该写法相较于第一种写法，通过调整代码运行的逻辑结构，对代码进行简化，代码的易理解程度，个人认为相较于第一种有所下降。但这种方法进行调整的逻辑思维巧妙性，个人认为还是值得学习的。

version 3

探讨直接插入排序时，我们不是实现了两种方法吗，那版本二的代码能不能套进希尔排序呢——答案是可以的。

改动如下：

void ShellSort3(DataType a[], int left, int right)
{int gap = right;while (gap > 1){// 当 gap > 1 时进行的就是预排序// 当 gap = 1 时进行的就是直接插入排序gap /= 2;int tmp = 0;// 对gap组进行多组并排，i指向无序区间的第一个值for (int i = gap; i < right; i++){tmp = a[i];int pos = 0;// 上面的end是指向tmp的前一个位置，这里的pos直接指向tmp所在位置，// 当循环结束之后pos就是数据该插入的位置for (pos = i; pos >= gap && a[pos - gap] > tmp; pos -= gap){a[pos] = a[pos - gap];}a[pos] = tmp;}}
}

3. 复杂度分析

时间复杂度

希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定：

比如：《数据结构(C语言版)》—严蔚敏

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

个人这里gap的取值用的就是 shell 提出的gap = gap / 2，时间复杂度大概在O(N^1.5)。

空间复杂度

希尔排序过程中并未产生额外的线性空间开销，因此，它的空间复杂度为O(1)。