希尔排序算法
前言
当待插入元素是一个很小(当需求是从小到大排序时，从大到小排序时此处为很大)直接插入排序需要移动较多次数，性能会很差。希尔排序解决了这一问题。
基本思想
希尔排序的基本思想：把序列按下标的一定增量分组，对每组使用直接插入排序算法排序； 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。 如果对直接插入排序不了解的朋友，可以看我的这篇文章： 详解直接插入排序算法
例子
给定数组arr为 [ 3 , 6 , 5 , 12 , 1 , 75 , 10 ， -3， 0 ] 初始状态见下图：
初始序列
定义变量 h为增量，初始值为5 。
第一轮根据增量设置成5组，颜色相同的为一组。
对每一组进行直接插入排序得到：
然后 h减半向下取整； 则 h = 3；
第二轮根据增量设置成5组，颜色相同的为一组。
对每一组进行直接插入排序得到：
第二轮进行插入排序
然后 h减半向下取整； 则 h = 1；
第三轮增量为1，所有序列为一组。
第三轮进行插入排序
插入排序后得到：
h此时为1，全部有序，完毕。
由例子可知，每次都可以达到组内部分有序，大大减少了插入排序的移动开销。
代码
首先说下步长的选择：步长的选择一般时这样的：
int h = 1;
while(h < arr.length / 2){
h = 2 * h + 1;
}
即先把步长设置为1，只要 h 小于数组长度一半（向下取整）就在原基础上乘以2再加上1； 那么，本文的例子中的步长计算为： 初始设为1； arr.length为9，其一半向下取整为4； 1 < 4；则 h 修正为 h = 1 * 2 + 1 = 3； 3 <4 仍成立，h修正为 h = 3 *2 + 1 = 7 。 本文一开始将 h 选为5，是为了演示方便。
根据步长分组后，进行插入排序的代码为:
for(int i= h ; i< arr.length;i++){
value = arr[i];
index = i - h;//初始为前一个元素
while(index >=0 && value < arr[index]){
//需要保证index合法
//每当前面的元素比待插入元素大，就向后移动
arr[index + h] = arr[index];
//不用怕覆盖，因为value保存着待插入的值
index -= h;
}
//当退出循环，表明已经找到了待插入位置，即index + h
arr[index + h] = value;
}
对外层循环进行解释：i 的初始值为 h,即第一个待进行插入排序的元素的索引， i - h即为本组待插入元素的最前面元素的索引。
i++表示下一组待插入元素的索引。
内层循环就是插入排序的代码。 如果对直接插入排序不了解的朋友，可以看我的这篇文章：
其他
希尔排序的时间复杂度有很多种说法，证明也比较复杂，本文不过多讨论。 关于稳定性： 在不同的插入排序过程中，相等的元素可能在各自的插入排序中发生移动，最后其前后相对位置会发生改变，所以希尔排序是不稳定的。
欢迎关注
欢迎大家的关注
扫描下方的二维码关注我的微信公众号：code随笔