【数据结构与算法】选择排序篇----详解直接插入排序和哈希排序【图文讲解】

 欢迎来到CILMY23的博客

🏆本篇主题为：【数据结构与算法】选择排序篇----详解直接插入排序和哈希排序

🏆个人主页：CILMY23-CSDN博客

🏆系列专栏：Python | C++ | C语言 | 数据结构与算法 | 贪心算法 | Linux | 算法专题 | 代码训练营

🏆感谢观看，支持的可以给个一键三连，点赞关注+收藏。

---

 前言

本期要讲解的是常见排序算法中的插入排序，插入排序又分两种，一种是直接插入排序，一种是希尔排序。

---

一、直接插入排序

1.1 插入排序的基本思想：

插入排序是一种简单的插入排序方法，其基本思想是：

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

实际中我们玩扑克牌时，就用了插入排序的思想，我们从桌面抽一张牌，然后把牌按照我们所想的情况排序，插入到合适的位置，这就是插入排序的大致过程。

 

1.2 直接插入排序操作：

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移 

 

1.3 直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)（逆序），最好情况是O(N) (顺序有序)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

1.4 代码实现 

第一部分：

先写单趟的排序，现在取 end 之前的位置都是有序的，要比对的数值是 end+1 的位置数，这里我们用一个变量 tmp 来存储。

我们想实现升序的tmp

如果 tmp 比 end 位置的值小，那么就要把 end 位置的数值往后移动，end 往前移动，直到我们找到 tmp 比 end 位置的数值小，我们就可以直接插入。 

特殊情况：

当 end+1 处的位置为最小值时，此时 end 为 -1 ，tmp 也就是 end+1 的位置处于 0 。

代码：

首先先不管end 是多少，我们知道[0,end]是有序，那end + 1 位置就是我们要比较的数，假设这个数比end位置小，那前面的位置就往后移动，直到数组尽头，或者找到比 end位置要大的数，在这个数的后面进行插入。 

int end;
int tmp = a[end+1];
while(tmp < a[end])
{a[end+1] = a[end];end--;
}
a[end+1] = tmp

为什么最后是end+1？

 取第二种极端情况，也就是插入排序的end走到尽头了，此时end 为 -1 这时候我们要在数组下标0的位置插入，所以要+1。

第二部分

确认多趟的情况 ，首先得保证前 end 都是有序的，想要确认end前有序，我们就再套一层循环，从0开始，让 end 从 0 的位置开始，遍历每个数值过去，这样整个数组都可以实现排序了。

void Insert_Sort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int end = i;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.5 动图理解

二、希尔排序（缩小增量排序）

2.1 基本思想

希尔排序法又称缩小增量法。

希尔排序法的基本思想是：

先选定一个整数，把待排序文件中所有记录分成按距离的个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达gap=1时，所有记录在统一组内排好序。

例如下图： 

第一趟排序，gap = 5,从第一个数开始，每隔五个数取一组，9和4为一组；1和8为一组；2和6为一组；5和3为一组，7和5为一组，这样整个数组都分好了，然后在每个小组里面进行排序，9和4排序，因为9比4大，所以9在后面，4在前面，以此类推……

第二趟排序，gap = 3，从第一个数开始，每隔三个数取一组，4,2,5,8,5为一组；1,3,9,6,7为一组；这样整个数组就又分好了，然后在每个小组里面进行排序，4，2，5，8，5排序，排好后，就是4，2，5，8，5.同样以此类推排第二个小组。

在这样的排序下就逐渐接近了有序的数组。我们把这样的操作叫做预排序。

最后第三趟排序，当gap == 1时，你会发现，这个跟直接插入排序没有区别，开始取第一个数，保证第一个数有序，然后开始走直接插入的思想。 

通过这样的过程我们就可以发现，直接插入排序也是希尔排序中的一步骤。 

2.2 希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样排序起来就会很快。对整体而言，可以达到优化的效果。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定，但也有大致算出来的。估计结果为O(n^1.3)

4. 稳定性：不稳定

2.3 希尔排序代码

void Shell_Sort(int *a,int n)
{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{tmp;}}a[end] = tmp;}}
}

2.4 希尔排序操作详解

 希尔排序分两步走，一步是预排序，它的目的是让整个数组接近有序，第二步是直接插入排序。

第一种预排序（一组一组排序）：

预排序的思路如下：

1. 先把数组分成以gap为距离的各个小组
2. 把分好的各单位小组进行插入排序
3. 对每个小组进行插入排序

第一步：

假设我们现在有这样的三个小组，分别用红，橙，绿三种颜色进行标记。 

把红色的第一个小组单独拿出来

我们标上下标，我们发现对这一个小组进行插入排序，原先的end+1就变成了end+gap。 

现在是交换红色的部分，橙色和绿色我们并不在乎。，因为tmp < nums[end],所以只需要比较end处和end+gap处的值，然后继续直接插入排序的操作即可。

 我们可以仿照直接插入排序写出如下的红色单区排序。

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

第二步： 

 然后控制多个红色小组

 我们套一层for循环，注意，j不能超过n-gap，防止end+gap越界。

最大的地方是：end+gap = n - 1

所以 j == end <= n-gap-1 == j < n - gap。

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

第三步：

控制多个组进行插入排序 

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

 第二种预排序（多组并排）：

 其实这里的多组并排原理很简单，就是让end按照顺序走下去：

也就是将第二步和第三步合并了，这就很接近我们刚开始的步骤。

所以预排序：

gap越大，大的值更快调整到后面，小的值更快调用到前面， 越不接近有序

gap越小， 跳的越慢 越接近有序，如果gap==1，那就是插入排序。

代码：

end每次只走一步，这样一组组的跳，就是多组并排了。 

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{tmp;}}a[end] = tmp;
}

第二步 直接插入排序

要想最后接近有序，每次gap就要变化，最后一次gap==1，所以gap要跟着n进行变化

 所以在外围添加一个循环，当gap > 1的时候是预排序，当gap == 1的时候是直接插入排序。

int gap = n;
while (gap > 1)
{gap = gap / 2;//觉得一次2太小//gap = gap / 3 + 1//...	
}

2.5 希尔排序动图

 

---

🛎️感谢各位同伴的支持，本期数据结构与算法---选择排序篇就讲解到这啦，如果你觉得写的不错的话，可以给个一键三连，点赞，关注+收藏，若有不足，欢迎各位在评论区讨论。