【排序算法】第一章：插入排序----直接插入排序与希尔排序的详解和对比

🫡和我一起感受两种排序算法的魅力吧！
在这里插入图片描述

前言：

理解排序算法最好的方法就是：先单趟后整体

先从一个元素的一趟开始理解
再扩展到所有元素的排序

一、直接插入排序

理解排序算法最好的方法就是：先单趟后整体

插入排序：以升序排序为例
总体思路

一个元素向前比较，遇到比自己大的元素，该较大元素就向后移动一位
遇到前一个元素比自己小，则自己就在当前位置插入（就是前一个元素的下一个位置）

单趟逻辑

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 每轮为 iint 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;}///}