【数据结构】– 明解 ‘ 希尔排序 ‘

100年前，人类发明了味精；
20年前，太太乐创造了鸡精；
xxx年前，希尔创造了希尔排序：

希尔排序的思想就是：
把一个数组拆分成多个组进行排序，先分组再进行插入排序，然后缩小组间的间隔进行排序，这一步会使得整个数组接近排序，这也称为预排序。
其中的组不是连续的数值组成，而是间隔 gap 个后的下一个数值组成。当 gap == 1 时，整个数组已经排序成功。
为什么用希尔排序：
答案当然是快啦，插入排序的时间复杂度为 O(N^2)，而希尔排序的时间复杂度为O(N^1.3—N^2）
希尔排序的 gap 取值：
gap 值越大，大的和小的数可以更快地挪到对应的位置去，但越不接近有序；
gap 值越小，大的和小的数可以更慢地挪到对应的位置去，就越接近有序；
取值看数组长度大小，一般用 gap /= 3 + 1 ，加一是为了防0，0就等于原地踏步了。
下面进行代码讲解：
首先给一个数组，要求升序；
int a[] = { 10,9,8,7,6,5,4,3,2,1,-1,-2,-3,-4,-5,-6,-7,-8,-9,-

【数据结构】– 明解 ‘ 希尔排序 ‘最先出现在Python成神之路。