一、希尔排序与插入排序
1）希尔排序的概念
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
2）插入排序实现
既然希尔排序是插入排序的优化，那么我们有必要先了解一下插入排序的过程，基本操作是将需要进行排序的元素插入到已排序区当中，这样每次插入都会使已排序区长度加一。
直观的看，插入排序的操作就和我们在打扑克牌时一样，我们默认将小的或者大的往一边插进去，插入排序也是如此。
1、我们从第二个元素开始插入排序，因为这样左边只有一个数，必然有序，我们把左边的称为已排序区，右边的称为待排序区。
2、将待排序区的第一个元素向已排序区插入，将其与已排序区元素从后向前比较，将其插入到合适位置，已排序区元素个数+1。
3、然后待排序区重复2的步骤向已排序区从后往前比较，找到合适位置插入。
4、 继续将待排序区元素插入到已排序区，当待排序区元素为0时，这组数据就已经排序完成。
我们明白了插入排序的过程，接下来就是实现插入排序了，我们先来分析，插入排序中第一个元素(0位置处)本来就是有序的，所以我们直接从第二个元素开始操作（1位置处）。
1、定义待排序区的首元素下标为end,用tmp记录下end下标的元素，将tmp与已排序区元素进行比较，发现小于5，则将待排序区的元素插入到首元素位置。
2、已排序区数组元素加一，待排序区首元素变为3，end也变为3的下标，tmp记录此元素的值，将tmp与已排序区元素进行比较，首先与5比较，小于5。
3、再跟1比较发现大于1，那么这个值就插入在1和5之间，已排序元素加一，待排序数组元素减一。
4、一直刷新end与tmp值，与已排序区进行从右往左的比较，比较到合适的位置才进行插入，而不是每次比较都插入元素。
时间复杂度：最坏情况下为 O(N^2)，此时待排序列为逆序，或者说接近逆序。最好情况下为 O(N)，此时待排序列为升序，或者说接近升序。平均为O(N^2)。
空间复杂度：没有额外使用空间，所以空间复杂度为 O(1)。
代码实现：
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<assert.h> void InsertSort(int *a, int len)//插入排序 { int i = 0; for(i = 1 ; i < len ; i++)//从下标为1的位置进行插入排序 { int end = i;//用end记录待排序区的首元素下标 int tmp = a[end];//用tmp记录待排序区首元素的值 while(end > 0)//保证不越界tmp就一直往前进行比较，找到合适的位置break { if(a[end - 1] > tmp) { a[end] = a[end - 1]; end--; } else { break; } } a[end] = tmp;//最后在将tmp值放在end的下标下 } } void Print(int *a, int len)//打印数组元素 { int i = 0; for(i = 0 ; i < len ; i++) { printf("%3d",a[i]); } printf("\n"); return; } void Test()//测试 { int a[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1 }; int len = sizeof(a) / sizeof(int); InsertSort(a, len); Print(a, len); return; } int main() { Test(); return 0; }
运行结果：
二、希尔排序实现
希尔排序法又称为缩小增量法。希尔排序法的基本思想是：首先选定一个整数，把待排序文件中所有记录分成gap个组（增量），所有距离为gap的数据记录在同一组内，并对每一组内的记录进行排序。然后，再取gap/2个组（缩小增量），重复上述分组和排序的工作。当gap == 1时所有记录在统一组内排好序。
注：希尔排序缩小增量在数学上是个难题，大家经常用的就是gap/2。
我们有这样一个数组：a[] = {6, 1, 5, 2, 4, 8, 3, 7, 9}。我们对这个数组进行排序，首先假设设置gap的值为3，那么这组数就会分为三组：
接下来控制这三组，每组分别进行插入排序，结果为：
那么gap为3时的所有组已经排完了，接下来就该缩小增量了，gap /= 2，gap == 1:
知晓了希尔排序是如何进行数据管理的，下面来看看具体的操作是如何完成的：
1、首先， 我们需要对gap进行控制，在gap>0范围内，每次分组后的所有组排完序之后都要除以二，可以用while循环来控制gap的大小：
void ShellSort(int *a, int n) { assert(a); int gap = n; int i = 0; while(gap > 1) { if(gap > 1) gap /= 2; //..分完组后的预排序 } }
2、我们已经将缩小增量设置好了，接下来只需要把每次分完组都进行排序，也就是预排序。如何进行预排序呢？既然希尔排序是插入排序的优化，我们不妨以插排的思路对希尔预排序进行调整。
用for循环对所有数据进行预排序，值得注意的是这里不会像插排那样循环到n，我们只需要限制在n - gap 的范围就行了，例如上图：
这个数组从3往后就不需要排了，因为在每一组的排序中最后一个值都是被拍过序的，没必要再次进行一次排序，总共为n个数据，那么就是只需要n - gap - 1个数据进行排序。则：
void ShellSort(int *a, int n) { assert(a); int gap = n; int i = 0; while(gap > 1) { if(gap > 1) gap /= 2; for(i = 0 ; i < n - gap ; i++)//控制n - gap数据进行预排序 { //具体排序过程... } } }
3、其实预排序的实现和直接插入排序的过程几乎是完全相似，前面也说了当希尔排序的缩小增量为1时，和插入排序没区别，也就是说，插入排序每次都对相邻的数据处理，而希尔排序是将分好的组看成新的数组，例如上面数据的6， 2， 3为一组，我们可以看成其他的数据不存在，只有这一组存在，那么对于这一组而言，希尔排序就是插入排序，将上图的三组都排完序，这一趟预排序就算完成了。
与插入排序相同，定义一个end记录当前元素下标，定义一个tmp记录a[end + gap]处的值，为什么不是a[end]处的值？可别忘了第一个值是默认有序的，所以要从第二个值向前比较，当end对应的值要大于tmp那么就将end处的值赋给下一个位置，也就是end+gap处，当不满足end处的值大于end+gap时，代表前面已经没有比自己大的值了，直接break，最后在循环结束的时候记得将a[end + gap]之前被覆盖的地方重新赋值：
void ShellSort(int *a, int n) { assert(a); int gap = n; int i = 0; while(gap > 1) { if(gap > 1) gap /= 2; for( i = 0; i < n - gap; i++)//对n组数据进行n - gap次预排序 { int end = i; int tmp = a[gap + end]; while(end >= 0)//当end >= 0时候对每组进行预排序 { if(tmp < a[end]) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } return; }
这样希尔排序就完成了，其实在希尔排序的过程中，或许你还有疑问，为什么for循环这里是连续的？不是进行分组了吗？其实你仔细想想， 我们还是以上面gap==3为例，首先是第一个数据，就是对第一组的首个数据进行排序，当到了第二个数据的时候，就是对第二组首个数据进行排序，但是因为有gap的控制，这两组数据其实是互不影响的，所以连续的遍历数据进行预排序也是没有问题的。
总结希尔排序的特性：
1、希尔排序是对直接插入排序的优化。
2、当gap > 1时，都是预排序，目的是让数组更接近有序，当gap==1时，将前面预排序的结果进行直接插入排序而完成排序。
时间复杂度：O(NlogN)（近似），因为增量问题并不能准确得出时间复杂度。
空间复杂度：没有开额外的空间，所以空间复杂度为O(1)。
以下是希尔排序的完整代码：
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> void ShellSort(int *a, int n) { assert(a); int gap = n; int i = 0; while(gap > 1) { if(gap > 1) gap /= 2; for( i = 0; i < n - gap; i++)//对n组数据进行n - gap次预排序 { int end = i; int tmp = a[gap + end]; while(end >= 0)//当end >= 0时候对每组进行预排序 { if(tmp < a[end]) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } return; } void Print(int *a, int n) { assert(a); int i = 0; for(i = 0 ; i < n ; i++) { printf("%d ",a[i]); } printf("\n"); return; } int main() { int a[] = {5,6,1,2,7,4,8,3,9}; int len = sizeof(a) / sizeof(int); ShellSort(a, len); Print(a, len); return 0; }
如果这篇文章对你有帮助的话，还望各位佬能多多三连~~[doge][玫瑰]
