希尔排序

概括：其实希尔排序就是将数组进行拆分，对分出来的每一个数组进行直接插入排序。

具体讲解

设置一个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));
    }
}