直接插入排序、折半插入排序、2路插入排序、希尔排序
本篇是排序专栏博客的第一篇，主要探讨以 “插入” 为核心思想的排序算法该如何实现
文章目录
- 一、前言
- 二、直接插入排序
- 1. 算法思想与操作分析
- 2. 代码实现
- version 1
- version 2
- 3. 复杂度分析
- 三、折半插入排序
- 1. 算法思想与操作分析
- 2. 代码实现
- 3. 复杂度分析
- 四、2路插入排序
- 1. 算法思想与操作分析
- 2. 代码实现
- 3. 复杂度分析
- 五、希尔排序
- 1. 算法思想与操作分析
- 2. 代码实现
- version 1
- version 2
- version 3
- 3. 复杂度分析
一、前言
所谓插入排序就是将数据整体的一部分独立看作有序，另一部分看作无序，然后将无序区间的数据一个一个地插入到有序区间中，并且在插入过程中始终保持有序区间有序的一种算法。
或许你会觉得很少见，但实际日常生活中，我们玩扑克牌游戏时就不自觉应用了这种思想。
既然插入排序要不断将数据插入有序区间中，那关键的地方就在于，如何在有序区间中找到一个合适的位置给新的数据。因此，根据查找插入位置的方法不同就衍生出了多种插入排序。
- 按顺序法查找插入位置的——直接插入排序。
- 按折半法（也叫二分法）查找插入位置的——折半插入排序。
- 通过缩小增量进行分组预排序的——希尔排序。
- 通过辅助空间减少挪动次数的——2路排序。
接下来就分别探讨这四个插入思想的排序算法如何实现。
二、直接插入排序
1. 算法思想与操作分析
思想：
假设我们现在要对 n 个数据排序：
- 将第
1个数据作为有序区间，后面的n-1个数据作为无序区间，然后将无序区间的首个数据插入到有序区间中，这个操作要进行n-1次。 - 直接插入排序，又称顺序插入排序，因此，做法就是定义一个索引
end指向有序区间的最后一个数据，每次插入操作都从后往前遍历有序区间，找到合适的插入位置。 - 重复步骤 2，直到无序序列数据个数为 0 。
图解分析基本操作：
有一组数据如下，我们现在需要将其从小到大排序。
- 首先将数据划分出有序区间和无序区间。
- 定义索引
end指向有序区间的末个数据，用于遍历有序区间；
定义索引i指向无序区间的首个数据，遍历无序区间进行每一趟的数据插入。
a[end]>a[i]，说明 1 应该插入到 9 的前面，但是 9 的前面已经不是数组的有效空间。
因此，9 要往后挪动一位，但是这样又会把a[i]给覆盖了，所以挪动前需要定义一个临时变量temp来保存a[i]的内容。
然后--end（看到这里你会惊讶的说，end 为什么要 -1，减完它就越界了啊，这样做是不是错了，别急，先记住这里，后面会一起解释）。
- 这样操作，待插入数据 1 就可以在 9 前面插入了，因为此时 end 的值为 -1，所以插入操作为
a[end + 1] = temp。
- 此时有序区间数据个数增加1，无序区间个数减少1，索引变量
end、i也要随着更新，更新操作为i++、end = i - 1；
- 第二轮待插入数据为 2，然后我们再重复上面的步骤 2、3、4、5；
废话不多说，直接上图（为了节省画图压力个人这里就压缩成两张图了）；
-
排序的步骤就演示到这里，接下来的操作无非就是重复步骤 2、3、5 的操作罢了，所以这里主要是总结一下排序过程的注意点。
从 3、6 这两点的图中我们可以总结出，找到插入位置的情况有两种：-
索引变量
end遍历完有序区间，即end == -1； -
索引变量
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. 复杂度分析
时间复杂度
直接插入排序是一种受序列初始排布状态影响的排序算法。
我们来对比以下两组数据排升序的性能差别：
- 第一组数据
{10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
- 第一组数据
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
从上面两组数据中，我们不难看出，如果数据越接近于有序那么直接插入排序的效率越高，反之，效率越差，时间复杂度越高。
虽然我们希望每次排序时都出现最好情况，但是很遗憾，时间复杂度是一个悲观预期，它以最坏情况为标准。
因此，结论是：直接插入排序的时间复杂度是O(N^2)。
空间复杂度
空间复杂度取决算法实现过程中额外空间消耗的大小，像
temp、end、i、pos这样的，常数个变量的开销的空间复杂度是O(1)。
三、折半插入排序
1. 算法思想与操作分析
思想：
同样，我们现在仍要对 n 个数据排序：
- 将第
1个数据作为有序区间，后面的n-1个数据作为无序区间，然后将无序区间的首个数据插入到有序区间中，这个操作要进行n-1次，直到无序区间数据个位数为 0。 - 相比较于边比较边挪动数据的直接插入排序，折半插入排序先用二分法找到插入位置，然后再挪动数据
- 最后将数据插入到合适的位置。
图解分析基本操作：
- 首先将数据划分出有序区间和无序区间。
（为了方便，折半插入排序仍旧采用与前面相同的一组数据）
- 定义用于二分查找插入位置的 3 个索引变量
left、mid、right；
定义用于遍历控制无序区间数据插入的循环迭代变量i。
设计好变量后，接下来进行第一趟的插入，先说明一下变量的初始化：
首先是循环迭代变量i，它承担的任务和前面相同，从下标为 1 开始遍历完无序区间；
其次是折半查找的三个变量：
- left指向有序区间的最左端，即初始化为
left = 0；- right指向有序区间最右端，即初始化为
right = i - 1；- mid指向当前区间的中间数据，即初始化为
mid = (left + right) / 2；
- 折半插入排序仅仅只是改变了插入位置的查找方式，数据挪动过程中仍会对待插入数据（
a[i]）进行覆盖，因此挪动前要将a[i]用临时变量temp保存；
然后，此时的a[mid]>temp，说明插入位置在a[mid]的左边，然后更新查找的边界，操作为right = mid - 1；
更新完边界之后，我们 需要判断一下是否满足条件left <= right，如果满足，说明明仍要继续查找，当right < left时，left指向的位置就是插入位置，从left开始到有序区间的最右端的数据都要向后挪动一位（temp的作用就在这里体现了）；
- 第一轮插入完毕，接下来进行第二轮插入
首先要对变量left、mid、right、i分别进行更新
++i，使变量i重新指向无序区间的首个数据；
left = 0，使变量left重新指向有序区间左边界；
right = i - 1，使变量right重新指向有序区间的右边界；
mid = (left + right) / 2，使变量mid重新指向当前查找区间的中间值；
- ①临时变量
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指向的位置就是查找位置；
- ①有序区间内从
left开始的数据都向后挪动一位；
②将temp插入到left指向的位置；
- 剩余数据的插入与上面的大同小异，唯一的不同点就是随着有序区间数据的增多，区间更新的次数也随之增加而已，这里就不再过多演示
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路插入排序是一种典型的通过牺牲空间换取时间的算法，先开辟与原数据等长的数据空间，然后遍历原数据，在辅助空间中排好序然后拷贝回源数据空间。
图解思想和基本操作：
- 第一步:
①开辟等长的辅助排序空间，初始化为0，将源数组第一个数据拷贝过去；
②定义索引变量head，tail，指向assist数组的第一个值；
③定义循环变量i，用于遍历源数组进行数据插入。
- 第二步：
现在数据分成三种情况
①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. 算法思想与操作分析
思想：
希尔排序，又叫做 “缩小增量排序”，“分组插入排序”。
它的基本思想如下：
- 将整个待排序数据序列以某个间隔(假设为gap)作为一组，划分成不同的子区间，分别进行直接插入排序；
- 不断缩小gap、重新划分子区间、分别进行直接插入排序；
- 直到整体数据接近于有序，再对全体元素进行一次直接插入排序。
图解分析基本操作：
以下为对一组简单的数据进行希尔排序的过程：
图中很清晰的展示了希尔排序是如何进行的：
- 定义一个增量
gap，设置初始值为n/2，将数据分为gap组，分别对gap组数据进行直接插入排序；gap /= 2，缩小增量，再对新划分的gap组数据进行直接插入排序；- 重复步骤 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，不再是1
for (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)。