希尔排序
概括：其实希尔排序就是将数组进行拆分，对分出来的每一个数组进行直接插入排序。
具体讲解
设置一个step（步长），step初始值为数组长度 / 2，每隔相同步长的元素被划分为同一个组，如下图。
分组
我们可以发现规律，step是多少，那么arr这个数组就会被分成几组。
之后对每一组进行直接插入排序，不懂直接插入排序请先去参看我写的直接插入排序的文章:https://www.jianshu.com/p/553ae4c822e0
将五组插入排序结束之后，arr数组如下图。
第一次结束
之后改变step的大小，将step再次 / 2，step = 5 / 2 = 2，继续分组。
第二次分组
分别对两组进行直接插入排序，结果如下图
第二次插入结束
最后再将step / 2， step = 2 / 2 = 1。当step等于1时就是最后一次排序，也就只有一组了，就是arr本身。对整体进行一次直接插入排序，完成希尔排序。
希尔排序结束
总结
- 无论step设置为多少，最后一次排序时，step都必须为1，因为最后要对数组整体进行一次直接插入排序。
- 数组分成的组数 == step的值
- 进行希尔排序一定要了解直接插入排序。
总体代码如下
/**
* Created by ShouJingGuo on 2018/3/14.
* 希尔排序
* 组数也等于step
*/
public class ShellSort {
public static <T> void shellSort(T[] arr, Comparator<T> comparator){
for(int step = arr.length / 2; step > 0; step /= 2){ //步长序列，最后必须为1进行一次，因为要整体进行一次插入排序
for(int i = 0; i < step; i++){ //分别对step数量组进行插入排序
for(int j = step + i; j < arr.length; j += step){ //对其中一组进行排序
T temp = arr[j];
int k = j - step;
while((k >= 0) && (comparator.compare(temp, arr[k]) < 0)){
arr[k+step] = arr[k];
k -= step;
}
arr[k + step] = temp;
}
}
}
}
public static void main(String[] args) {
Integer arr[] = {10,50,24,11,68,20,41,0,24,25,4,7,94,15,5,44,66};
ShellSort.shellSort(arr, new IntegerComparator());
System.out.println(Arrays.toString(arr));
}
}
