希尔排序是对直接排序插入排序算法的改进，又称为缩小增量排序。其基本思想是将待排序的记录分成几组，每组中元素都比原来的序列少，从而减少参与直接插入排序的数据量，在各组中分别进行直接插入排序。经过几次分组排序后，记录的排列已经基本有序，这个时候在对所有的记录实施直接排序。
具体步骤描述如下：假设待排序的记录为n个，先取整数 d< n，例如 d= [n/2](取整，不大于n/2的最大整数)，将所有距离为d的记录构成一组，从而将真个待排序序列分割成d个子序列，对每个分组分别进行直接插入排序，然后再缩小间隔d，例如 d = d/2，重复上述的分组，在对每个分组分别进行直接插入排序，直到最后取 d = 1，即将所有的记录都放在一组进行一次直接插入排序，最终将所有的记录重新排泄成按关键字有序的序列。
（注：d 的取值不一定是 n/2，每次缩小间隔 d 也不一定是 d/2，只要逐渐缩小，最后到d = 1，即可）
这里举个实例分析：
初始状态： 125 11 22 34 15 44 76 66 100 8 14 20 2 5 1 共15个元素
第一次分组：125 11 22 34 15 44 76 66 100 8 14 20 2 5 1 取d=[15/2] = 7，分成7组，相同分组内的元素用相同颜色表示
组内排序：1 11 8 14 15 2 5 66 100 22 34 20 44 76 125 在同一个组内使用直接插入排序算法，使每个小组内是有序的
第二次分组：1 11 8 14 15 2 5 66 100 22 34 20 44 76 125 去d =[7/2] = 3，分成3组，相同分组内的元素用相同的颜色表示
组内排序：1 11 2 5 15 8 14 34 20 22 66 100 44 76 125 在同一个组内使用直接插入排序算法，使每个小组内是有序的
第三次分组：1 11 2 5 15 8 14 34 20 22 66 100 44 76 125 去d =[3/2] = 1，分成1组，所有元素在同一个组，现在的序列基本有序，使用直接插入排序比较快
组内排序：1 2 5 8 11 14 15 20 22 34 44 66 76 100 125 在同一个组内使用直接插入排序算法，使每个小组内是有序的
参考代码：
#include <stdio.h> #define MAX_NUM 80 void shellsort(int* a, int n) { for(int d = n/2; d >= 1; d = d/2) { int guard = -1; for (int i = 0; i < n; i++) { guard = a[i]; int j = i - d; while(guard < a[j] && j >= 0) { a[j+d] = a[j]; j = j-d; } a[j+d] = guard; } for(int i = 0; i < n;i++) { printf("%d ",a[i]); } printf(" "); } } int main(int argc, char* argv[]) { int a[MAX_NUM]; int n; printf("Input total numbers: "); scanf("%d",&n); if( n > MAX_NUM ) n = MAX_NUM; for(int i = 0; i < n;i++) { scanf("%d",&a[i]); } printf("排序步骤： "); shellsort(a,n); return 0; }
案例结果截图：
希尔排序算法效率与稳定性分析
在希尔排序中，由于开始插入n个待排序列的记录分成了d组，所以每组的记录数目将会减少。在数据量较少的时，利用直接插入排序的效率较高。随着反复分组排序，d值逐渐变小，每个分组中的待排序的记录数目将会变多，但此时记录的排列将会更加接近有序，所以利用直接插入排序不会降低排序的时间效率。
上述过程中分组次数为log（n）。最好的情况，待排序序列已经排好序，在每次分组，直接插入排序的总时间复杂度为O(n),算法时间复杂度为O(nlog(n))。其他情况的复杂度分析相对复杂很多，本人理解的也不是很透彻，书中介绍说最坏情况和平均时间复杂度也均为 O(nlog(n))。
希尔排序使用与待排序列的元素数目较大的情况。在此情况下，希尔排序方法一般要比直接插入排序方法快。同直接插入排序一样，希尔排序也只需要一个记录大小的辅助空间，用于暂时记录当前待插入的记录。
由于排序时分组的原因导致序列输入顺序与原始顺序不一致，关键字相同的元素在排序前后可能发生变化，因而希尔排序是一种不稳定的排序算法。
注：主要参考彭军、向毅主编的 《数据结构与算法》