【排序算法】希尔排序

前言：学习希尔排序前最好先掌握插入排序，在进行；不会的可以点击——>【排序算法】插入排序-CSDN博客

一、希尔排序：

        希尔排序，也称为缩小增量排序，是一种基于插入排序的快速改进算法。由Donald Shell于1959年提出。 它的基本思想是将待排序的元素按照一定的增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。希尔排序在一般用于处理大量数据！！

二、思路：

分成2个阶段：

1、预排序：这个阶段将待排序的数据分成gap组，对每组数据进行插入排序。

2、插入排序：gap==1时，也就是只有1组的情况，这个数组就变成有序数组了。

 具体详情：

1、将一个小于n（元素个数的）的整数作为gap增量，所有距离为gap的元素作为一组数据（也就是我们说的将数组分成gap组）然后对每一组数据进行插入排序，排好后，取一个比第一增量小的整数（比原gap小的组数）重新将新的gap距离的元素作为一组数据，接着上述操作；重复这些操作

2、当gap不断细分到了gap==1即将所有元素分为一组时，进行插入排序，数据变成有序！

下面的动图，我觉的比较直观的了？当然没看懂也没关系，下面会有讲解

---

 先分组，然后你会发现我们分了三组，我们以3个元素为一组分的，但是有的组元素个数未满三个，因为元素之间的距离和数组长度的差异，会有点不同，但是影响不大哈，值得注意的是距离差3，不是元素个数差3哈，个数是只差了2个元素，从图里也可以看出来

分为3个组：

第一组：8、7、5

第二组：9、2、4

第三组：1、3

 对第一组进行插入排序

 然后接下来是下标为0+gap+gap的位置来一次插入排序，该位置本来的元素是5，经过插入排序后，5到了这组数据的最前面；此时这一组的数据是不是变成有序了

当每组都进行完插入排序后，我们可以发现小的数几乎靠近左边，大的数几乎靠近右边。大致粗略有点顺序了 

 然后将gap==1，进行一次整体的插入排序；因为数据比较少 所以这里gap的分化次数也比较少

---

三、时间复杂度：(有点难证明，记住即可)

O（N^1.3）

四、实现：

先考虑一组的实现哈。发现了没？其实和插入排序实现很相似，如果gap==1就是插入排序了。

---

对每一组都要进行插入；发现了么，先写底层逻辑真的很清晰；我们会顺畅很多

但是我不想要三层循环嵌套，可以修改一下，之前是一组一组的进行，就是说排好一组在进行另一组。现在我直接交错进行，先第一组的第一个元素，然后第二组的第一个元素，然后第三组的第一个元素，再是第一组的第二个元素……

下标到最后一组倒数第二个元素的位置即可，因为我们是将end的下一个元素抽出来，注意不要越界访问

最后要完成gap的变化，gap不是一直不变的，会不断地变小，直到gap==1；也就是第二个阶段：对整个数组进行插入排序，所以gap是个变值

 整体代码：

void ShellSort(int* a, int n)
{int gap = n;//gap的组数越大，数据可以更快的跳到后面，小的更快跳到前面，但是越不接近有序；反之，gap越接近有序while (gap > 1){//巧妙的用的除法，/2 /3 /4都行，但是有人证明了/3更好，还要加1，因为gap小于3的话gap/3==0//最后一次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 (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}}

 gap的选取：

        gap刚开始时从每组3个数据开始进行分组插入排序，然后gap=gap/3+1不断地分化组数（分的组数在减少，但是相反的每组数据个数在增加）加一个 1 是为了保证最后一次满足gap==1，因为gap/3 gap小于3时得到的商只能是0；并不是只能gap/3，也可以gap/2等等，但是目前gap/3+1是时间复杂度被验证过了的

分组组数的特点：

gap越大，每一组的数据间隔越大（中间隔的元素个数多），插入一次的幅度更大，大的数据能够更快的跳到后面，小的数据也能更快的跳到前面，但是越远离有序

gep越小，每组数据间隔越小（中间隔的元素个数少），此时数据跳到后面也就越慢，小的数据跳到前面也越慢；但是越接近有序，即gap==1时就是有序的

感                       谢                 观                 看