个人主页：欢迎大家光临——>沙漠下的胡杨

  各位大帅哥，大漂亮

 如果觉得文章对自己有帮助

 可以一键三连支持博主

 你的每一分关心都是我坚持的动力

 

 ☄： 本期重点：希尔排序

  希望大家每天都心情愉悦的学习工作。 

 ☄： 本期重点：希尔排序

插入排序：

插入排序的思想：

示意图分析：

代码实现：

希尔排序（重点）：

希尔排序的预排序：

希尔排序的代码实现：

希尔排序和直接插入排序对比：

我们今天进入排序大章节，我们首先学习的是插入排序。

插入排序：

插入排序的思想：

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

例如：

今天你女朋友给你送一些奥特曼，你要把他们按照身高从小到大排序，怎么办呢？

我们可以拿出一个迪迦奥特曼，然后再拿另外一个艾斯奥特曼做比较，如果艾斯比迪迦高，那么我们就把迪迦放前面，艾斯放后面，这样这两个奥特曼身高就从小到大了，然后再拿其他奥特曼做比较，如果比前面矮，那么我们就把这个奥特曼向前移动，这样我们就把奥特曼的身高从小到大排序了。

示意图分析：

我们先排序要先写单次排序，然后再写多趟排序。

单次排序，如下图分析：

 这是单次排序，多次排序就是循环起来，控制下标即可。

代码实现：

void InsertSort(int *a,int n)//插入排序{for (int i = 0; i = 0)//如果下标 大于等于0 就继续{if (tmp < a[end])//如果要插入的值，比原来小{a[end + 1] = a[end];//把原来的值向后移动--end;//下标也改变。}else{break;//插入完毕}}a[end + 1] = tmp;//把要插入的值放到跳出循环的下标后。}}

代码也比较简单，需要注意的是控制下标，不要越界。

在时间复杂度上是典型的O(N*N)

希尔排序（重点）：

希尔排序思想：

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个 组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工 作。当到达=1时，所有记录在统一组内排好序。

简单来说就是在插入排序之前先进行预排序，把数据尽量变的有序。

希尔排序的预排序：

我们如何进行预排序呢？

 这里就引入了一个叫 gap 的概念，我们把间隔为 gap 的元素分为一组，对每一组进行插入排序。

 

 

 

 此时在进行插入排序要快的多。

希尔排序的代码实现：

一般情况下，我们会让gap从大到小进行预排序，然后让最后一次的gap为1，就是直接插入排序。每次gap进行预排序和直接排序代码上十分相似，只不过是每次移动gap步，最后一次gap为1，也就是移动1步，变为插入排序。

那我们的每次调整的截止在哪里呢？如下图分析：

 

代码如下：

void ShellSort(int *a, int n){int gap = n;//gap刚开始赋值为n//保证最后一次gap为1，循环的条件就是 >1while (gap > 1){//每次预排序前计算gap，并且+1后，最后一次的gap是1.gap = gap / 3 + 1;//最多访问到gap-1即可。for (int i = 0; i = 0)//插入排序{if (tmp < a[end]){a[end + gap] = a[end];//每次移动gap步end -= gap;}else{break;}}a[end + gap] = tmp;}}}

希尔排序和直接插入排序对比：

直接插入排序：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

希尔排序：

1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就 会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的 希尔排序的时间复杂度都不固定。

4. 稳定性：不稳定

 

总的来说：

希尔排序是对插入排序的优化，插入排序每次只能移动一步，希尔排序因为gap的存在可以一次移动多步，这样就可以是数据跳动的更快。当gap越大时，预排序效果越差，当gap越小时，预排序效果越好，越接近有序，当gap为1时，就是插入排序。