前言
当待插入元素是一个很小(当需求是从小到大排序时，从大到小排序时此处为很大)直接插入排序需要移动较多次数，性能会很差。希尔排序解决了这一问题。文章源自随机的未知-https://sjdwz.com/11140.html
基本思想
希尔排序的基本思想：
把序列按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
如果对直接插入排序不了解的朋友，可以看我的这篇文章：
https://sjdwz.com/11139.html文章源自随机的未知-https://sjdwz.com/11140.html
例子
给定数组arr为 [ 3 , 6 , 5 , 12 , 1 , 75 , 10 ， -3， 0 ]
初始状态见下图：文章源自随机的未知-https://sjdwz.com/11140.html
定义变量 h为增量，初始值为5 。文章源自随机的未知-https://sjdwz.com/11140.html
第一轮
根据增量设置成5组，颜色相同的为一组。
文章源自随机的未知-https://sjdwz.com/11140.html
对每一组进行直接插入排序得到：
文章源自随机的未知-https://sjdwz.com/11140.html
然后 h减半向下取整；
则 h = 3；文章源自随机的未知-https://sjdwz.com/11140.html
第二轮
根据增量设置成5组，颜色相同的为一组。文章源自随机的未知-https://sjdwz.com/11140.html
对每一组进行直接插入排序得到：文章源自随机的未知-https://sjdwz.com/11140.html
然后 h减半向下取整；
则 h = 1；文章源自随机的未知-https://sjdwz.com/11140.html
第三轮
增量为1，所有序列为一组。文章源自随机的未知-https://sjdwz.com/11140.html
插入排序后得到：
h此时为1，全部有序，完毕。文章源自随机的未知-https://sjdwz.com/11140.html
由例子可知，每次都可以达到组内部分有序，大大减少了插入排序的移动开销。文章源自随机的未知-https://sjdwz.com/11140.html
代码
首先说下步长的选择：
步长的选择一般时这样的：文章源自随机的未知-https://sjdwz.com/11140.html
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，是为了演示方便。文章源自随机的未知-https://sjdwz.com/11140.html
根据步长分组后，进行插入排序的代码为:文章源自随机的未知-https://sjdwz.com/11140.html
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++表示下一组待插入元素的索引。文章源自随机的未知-https://sjdwz.com/11140.html
内层循环就是插入排序的代码。
如果对直接插入排序不了解的朋友，可以看我的这篇文章：
https://sjdwz.com/11139.html文章源自随机的未知-https://sjdwz.com/11140.html
其他
希尔排序的时间复杂度有很多种说法，证明也比较复杂，本文不过多讨论。
关于稳定性：
在不同的插入排序过程中，相等的元素可能在各自的插入排序中发生移动，最后其前后相对位置会发生改变，所以希尔排序是不稳定的。文章源自随机的未知-https://sjdwz.com/11140.html
** 欢迎关注**
欢迎大家的关注文章源自随机的未知-https://sjdwz.com/11140.html
扫描下方的二维码关注我的微信公众号：随机的未知
文章源自随机的未知-https://sjdwz.com/11140.html
