🫡和我一起感受 两种排序算法的魅力吧！
前言：
理解排序算法最好的方法就是：先单趟后整体
- 先从一个元素的一趟开始理解
- 再扩展到所有元素的排序
【下面用到的：随机数生成测试排序性能器的代码】
一、直接插入排序
理解排序算法最好的方法就是：先单趟后整体
插入排序：以升序排序为例
总体思路
- 一个元素向前比较，遇到比自己大的元素，该较大元素就向后移动一位
- 遇到前一个元素比自己小，则自己就在当前位置插入（就是前一个元素的下一个位置）
单趟逻辑
int end; // end 代表前一个元素下标
int tmp = a[end + 1]; // tmp 就是当前要向前比较的当前元素
while (end >= 0)
{
if (a[end] > tmp) { // 遇到比自己大的元素，
a[end + 1] = a[end]; // 该较大元素就向后一位，
end--; // 同时下标前移
}
else break; // 当自己大于或等于前一个元素时，自己可以插入当前位置了
}
a[end + 1] = tmp; // 插入在当前位置
整体逻辑：所有元素排序
由单个元素排序逻辑可知：可以同时表示当前元素和前一个元素的，就是 end
则 需要循环 end，使每一个元素可以遍历到
由动图可知，end 最多可以到达的位置为 n - 2（数组从 0 开始），因为最后一个元素的位置在 n - 1，而 end+1 必须合法（若 end == n-1，则 end+1 == n， 越界了 ）
注意：插入排序是从前向后循环 end 的
不能从后往前：前面的序列不是 有序的，插排无效
插入排序需要保证自己当前元素的前面序列全部有序
其中 end 从 0 开始，第一个真正开始比较的元素是 end + 1，这里默认 数组首元素已经算作有序
动图演示
// 外层 for，循环 end
for (int i = 0; i < n - 1; ++i) {
int end = i; // end 每轮为 i
int tmp = a[end + 1]; // tmp 就是当前要向前比较的自己
while (end >= 0)
{
if (a[end] > tmp) { // 遇到比自己大的元素，
a[end + 1] = a[end]; // 该较大元素就向后一位，
end--; // 同时下标前移
}
else break; // 当自己大于或等于前一个元素时，自己可以插入当前位置了
}
a[end + 1] = tmp; // 插入在当前位置
}
时间复杂度计算
计算时间复杂度：
当元素全部逆序时为最坏情况
排序次数和为 1 + 2 + 3 + 4 + … + n 成等差数列
由等差数列公式求和得出： (n^2 + n) / 2
时间复杂度就是 O(n^2) 级别的
==最好情况是顺序：O(n) ==
启发：当一个序列基本有序时，使用插排可以 有接近 O(n) 的时间复杂度
二、希尔排序
希尔排序是对直接插入排序的优化，建议先学了 直接插入排序 后再来学这个，否则较难理解
希尔排序可以说是对插入排序的一种升华，一种升级版插入排序，通过 预排序 使局部有序率放大，从而便于提高插入排序效率，具体下面解释：
效率优化的具体原理：
由于插入排序在序列有序时，效率较高，希尔就通过这个特性，设计一种算法，使待排序的序列接近有序、
观察
直接插入排序：可以发现，有一些较大的值，本身最终就是要排序到末尾位置的，而这个值偏偏又在序列前面，还要一点一点的挪动，中间浪费的较多的时间则这部分时间就可以优化掉，这就是希尔的思路
希尔排序会 进行 预排序：分组插入排序
目的：将较大值更快的放到后面的位置，较小值更快的放大前面位置
动图演示
可以看到每次数据进行交换 都是和自己同一颜色的进行交换，这就是 分组进行插入排序
分组依据：设置 gap 间隔，动图为例，每个数据间隔位置为 gap == 5 ，最多不超过 第 n-1 个
循环对每一组数据插入排序
代码如下：
int gap = 5;
for (int i = 0; i < n - gap; i += gap) {
int end = i;
int tmp = a[end + gap];
while (end >= 0) {
if (a[end] > tmp) {
a[end + gap] = a[end];
end -= gap;
}
else break;
}
a[end + gap] = tmp;
}
可以发现，该代码和 前面讲解的 直接插入排序 一摸一样😋
没错，前面讲解的 直接插入排序 属于 gap == 1 的情况，间隔为 1，则每一个数据都是 “ 一组”
希尔排序 这里就是 gap > 1 的情况，只需要将 前面讲解的 直接插入排序 的代码中 的 某部分的 1 改成 gap 就好
前言：gap > 1 的排序称为 预排序，都是为最后一次 gap == 1 排序服务
其实希尔排序也可以说是对插入排序的一种升华，我们有提到插入排序的效率大于冒泡排序，是因为它有较好的局部有序性，那么希尔排序就是对这一优势的放大，使局部有序性加大
预排序 会将数组 局部有序率放大到极高，所以最后一次插入排序的时间复杂度很低，则极大提升效率
进行完一次 gap == 5 的排序后，各小组内部已经有序了，但是 小组之间还未有序，则需要缩小 gap 再次进行比较
后续需要缩小 gap 再次比较，那 gap 应该以什么规律缩小，同时需要满足最后可以缩小至 gap == 1，进行最后一次？
方案：每轮减半，最后 gap == 1 可以进行最后一次
int gap = n;
while (gap > 1) {
gap = gap / 2;
// .....
}
希尔排序第二轮：gap = gap / 2 = 2
希尔排序最后一轮：gap = gap / 2 = 1
最终代码：
int gap = n;
while (gap > 1) {
gap = gap / 2;
///
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 == 1 就是直接插入排序 gap > 1 就是希尔排序
希尔排序的时间复杂度不好计算，因为 gap 的取值方法很多，导致很难去计算
直接插入排序和希尔排序的性能对比
下面我用代码随机生成 1000000 个数据，执行两个排序算法，显示的数据为 代码运行时间，以 ms 为单位
【上面用到的：随机数生成测试排序性能器的代码】
🤣直接插入排序 直接执行了 约 2min，而 希尔排序只有 89 ms ！！！！！
😎怎么样，是不是惊呆了，这个差距相当大了，这里不得不佩服 希尔大神！！！
🫡至此，第一章完结！
【若文章有什么错误或则可以改进的地方，非常欢迎评论区讨论或私信指出】**