概述

希尔排序是插入排序的一种更高效的改进版本.

希尔排序的基本思想是: 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止

就是将插入排序分组一下

分组排序步骤如下:

1. 选定一个增量, 即将数组分为几组
2. 根据增量分别对几个分组进行插入排序
3. 减小增量, 重复步骤1-2, 直到增量为1进行最后一次排序

其时间空间复杂度为:

Java代码实现

/**
 * 对数组进行插入排序
 * @param arr
 * @param index
 *      第一个元素下标
 * @param d
 *      增量
 */
private static void insertSort(int[] arr, int index, int d) {
    /*
     * 1. 从数组第二个元素开始(第一个被认为已经排序)向后遍历
     * 2. 将已排序数组中所有大于当前元素的向后移动一位
     * 3. 将当前元素插入到已排序数组中
     * 4. 拿到下一个元素, 重复步骤2
     */
    // 从分组的第二个元素开始遍历
    for(int i = index + d; i < arr.length; i += d) {
        // 保存当前元素
        int tmp = arr[i];
        int j;
        // 将元素左侧所有大于当前元素的值右移一位
        for(j = i - d; j >= 0 && arr[j] > tmp; j -= d) {
            arr[j + d] = arr[j];
        }
        // 将当前元素插入序列中
        arr[j + d] = tmp;
    }
}

/**
 * 希尔排序实现数组排序, 从小到大顺序
 * @param arr
 * @return
 */
public static int[] insertionSort(int[] arr){
    /*
     * 1. 对数组进行分组, 对每组进行插入排序
     * 2. 减小分组数量, 重复步骤1
     * 3. 直到分组数为1进行最后一次排序
     */
    if(arr == null || arr.length <= 1){
        return arr;
    }
    // 以arr.length/2为初始增量, 每次减半
    for (int d = arr.length / 2; d > 0; d /= 2){
        /*
         * 对每组进行插入排序
         */
        // i为每组的第一个元素
        for(int i = 0; i < d; i++) {
            // 对分组进行插入排序
            insertSort(arr, i, d);
        }
    }
    return arr;
}