思想
希尔排序实际上是对插入排序的改进，增加了一个一个间隔X，每次都将间隔X的两个数进行比较，确定位置，然后减小间隔X，直达间隔X=1，也就是原始的插入排序。
举例
借用网友分享的图片进行说明：
步长的确定
间隔也就是步长，那么这个步长怎么确定呢？
一般是这样的：
第一次增量的取法为： d=count/2;
第二次增量的取法为: d=(count/2)/2;
最后一直到: d=1;
代码
/// 希尔排序
public void shellSort(int [] input){
if (input == null || input.length == 0) {
return;
}
int increament = input.length / 2;
while (increament >=1) {
for(int i = 0;i< input.length;i++){
for(int j = i + increament;j< input.length;j+=increament){
if (input[i]>input[j] ) {
int temp = input[i];
input[i] = input[j];
input[j] = temp;
}
}
}
increament = increament/ 2;
}
}
复杂度分析
希尔排序适合数据较少的数组的排序，一般适用于少于5000的数组。他是所有复杂度为O(n2)的排序算法中最快的。
最坏的情况是O(n2)，
最好是O(nlogn)
平均情况是O(nlogn) – O(n2).
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
