【C语言】排序算法——希尔排序以及插入排序 ——详解！！！

【C语言】排序算法——希尔排序以及插入排序详解

• 前言
• 一 、插入排序
  • 1. 视频演示
  • 2. 算法思想
  • 3. 实现思路
  • 4. 代码演示
• 二 、希尔排序
  • 1. 视频演示
  • 2. 算法思想
  • 3. 实现思路
    • （1）分组
    • （2）预排序
    • （3）最终排序
    • （4）gap的取值
  • 4. 代码演示
• 结语

前言

在学习循环的时候，我们学习到了冒泡排序这个算法
那么，除了冒泡排序，还有什么排序算法呢？
今天给大家带来的是插入排序以及希尔排序

一 、插入排序

1. 视频演示

首先给大家看一段视频，让大家先看看插入排序是怎么运行的

插入排序演示

2. 算法思想

我们可以从视频里看见，插入排序就像是我们打扑克牌一样，一张一张插入到了有序队列
每次都有一个数据 x（标红的）要跟前面的数据一一比大小
若 x 比前一个数据小，则 x 就再向前比较
若 x 比前一个数据大，则 x 就插入到这个数据的后面

3. 实现思路

由视频可知，数据 x（标红的）前面的序列都是有序的，故每一次只需要将 x 插入其中即可

• 第一步

我们给定下标范围【0，end】区间是有序的，tmp为要插入的数据的值，故tmp为下标为end + 1所对应的值

• 第二步

将下标为end所对应的值与tmp比较
若tmp比前一个数据小，则tmp就再向前一个数比较
若tmp比前一个数据大，则tmp就插入到这个数据的后面

• 第三步

循环遍历整个数组，直到数组全部插入进去

4. 代码演示

// 插入排序voidInsertSort(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. 视频演示

首先给大家看一段视频，让大家先看看希尔排序是怎么运行的

希尔排序视频演示

2. 算法思想

当你看完视频，你也许就会发现希尔排序和插入排序很相似
只不过，希尔排序相当于间隔插入排序 n 次
而每一次都越来越接近有序数组，直到最后一次排成有序

3. 实现思路

那该怎么实现呢？

（1）分组

• 第一步：分组

由视频可知，每次排序并不是一个一个排，而是每间隔几个数据成一组来排序
一组一组排，这组排完就到下一组，直到全部排完
这里先假设分成3组数据进行排序，也就是每隔2个数据成一组

如图：

（2）预排序

• 第二步：预排序

分成了几组后，每一组就开始插入排序，称为预排序
插入排序前面讲了，就不赘述了

代码演示：
（ gap 就是被分成了几组）

int gap = n;while(gap >1){ gap =3;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;}}

预排序是干什么呢？
预排序的主要功能就是让一个数组接近有序，为了给后面的插入排序节省大量的时间

（3）最终排序

• 第三步：最终排序

现在，在排序完三组数据后，我们的数组已经很接近有序
所以现在只需要用插入排序排最后一次收尾就行了

这里就不进行代码演示了，就是一个普通的插入排序

（4）gap的取值

• 第四步：gap的取值

一、前面我们的代码中 gap 的取值定为了 3，但是这不可能对于每个数组都适应
那么该如何给 gap 来取值呢？
根据科学的实验，发现当gap为 n / 3时，排序最快
所以，在排序的过程中，gap 的值是不断发生变化的

二、到这里，可能已经有人发现了，刚刚写的预排序和前面写的插入排序几乎一摸一样
只是将 1 变成了 gap
>其实，当gap为1时，就是普通的插入排序

那么我们能不能设计一个循环，既能在排序的过程中满足gap的动态变化，又能使gap的最后一次取值为 1 呢？

所以我们可以有一些改进，在函数外面再套一层循环：
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
…………
…………//这里省去代码
}

这样，gap能够很好的动态变化，且最后一次循环的gap值为1，恰好能完成一次普通的插入排序

4. 代码演示

代码演示：

// 希尔排序voidShellSort(int* a,int n){int gap = n;while(gap >1){ gap = gap /3+1;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;}}}

结语

OK，本期的排序算法详解到这里就结束了

若内容对大家有所帮助,可以收藏慢慢看,感谢大家支持

本文有若有不足之处，希望各位兄弟们能给出宝贵的意见。谢谢大家！！！

新人，本期制作不易希望各位兄弟们能动动小手，三连走一走！！！

支持一下（三连必回QwQ）