软设之希尔排序

假设有n个元素，先取一个小于n的整数d1作为一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组中进行直接插入排序;然后，取第二个增量d2<d1重复上诉的分组和排序，直到所取得增量dt=1，也就是所有记录放在一个同一个组进行插入排序。

比如说有数组57 68 59 52 72 28 96 33 24 19进行希尔排序。

d1=10/2=5

第1个第6个为一组，第2个第7个为一组，第3个第8个为一组，第4个第9个为一组，第5个第10个为一组，进行插入排序

排序如下

28 68 33 24 19 57 96 59 52 72

d2=5/2取奇数为3

再次分组，排序如下

24 19 33 28 59 52 72 68 57 96

d3=3/2=1

排序如下

19 24 28 33 52 59 68 72 57 96

最后对整个数组进行插入排序就可以了。这时候整个数组排列相对有序了，只要进行很少插入排序就可以完成排序了。

希尔排序是一种不稳定的排序方法，时间复杂度是O(n^1.3),空间复杂度是O(1)