什么是希尔排序

希尔排序也叫做：缩小增量排序。 分组（分组的组数需要循环递减，直到减为1）排序。
先将待排序序列分成若干组，然后使用直接插入排序在组内排序。循环着将分组数减小，执行以上过程。直到分组减为1. 所有的分组数都互质。

分组可为任意数字，且每次分组数都比上一次分组要小，直至分组数为1。

为什么不直接使用插入排序

相比较插入排序，希尔排序输入直接插入排序的一种，但是在两种算法的比较上

希尔排序: 就是直接插入排序的优化， 数据越有序，排序越快
时间复杂度： 时间复杂度是与增量序列相关的函数 O(n^1.3~1.5)
空间复杂度： O(1)
稳定性： 不稳定
直接插入排序
时间复杂度： 等差数列 O(n^2)
数据序列已经有序，则能达到最好时间复杂度: O(n)
数据趋于有序（部分有序）: 时间复杂度就可以趋于 O(n)，–> 数据越有序，时间复杂度越低。
空间复杂度： O(1)
稳定性： 稳定的

对于一个长度为10000的需要排序的数组，希尔排序只需要更少的比较次数与交换次数。

希尔排序代码实现

void Shell(int *arr, int len, int width)
{for(int i = width; i < len; ++i){int tmp = arr[i];int j = i - width;for(; j >= 0 && arr[j] > tmp; j -= width){arr[j+width] = arr[j];}arr[j+width] = tmp;}
}void ShellSort(int *arr, int len)
{int group[] = {5, 3, 1};for(int i = 0; i < sizeof(group)/sizeof(group[0]); ++i){Shell(arr, len, group[i]);}
}

很显然，希尔排序不过对直接插入排序前进行了一次分组。分组使得希尔排序对于大量的数据处理更有优势，但是也增加了不稳定性。