希尔排序

希尔排序可以说是插入排序的一种变种。无论是插入排序还是冒泡排序，如果数组的最大值刚好是在第一位，要将它挪到正确的位置就需要 n - 1 次移动。也就是说，原数组的一个元素如果距离它正确的位置很远的话，则需要与相邻元素交换很多次才能到达正确的位置，这样是相对比较花时间了。

希尔排序就是为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序。

希尔排序的思想是采用插入排序的方法，先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是 h = n / 2,接着让 h = n / 4，让 h 一直缩小，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了。

为方便理解我还准备了图片：

实现代码：

package fg;

public class ShellSort {
    public static void shellSort(int[] arr) {
        if (arr == null || arr.length <2)   // 空数组 或 只有一个元素的数组，则什么都不做。
            return;
        int gap = arr.length / 2;   // 定义希尔增量。

        // gap缩小到0的时候就退出循环（判断结束条件）。
        while (gap != 0) {
            // 每组进行直接插入排序。
            for (int i = gap; i < arr.length; i++) {    // i 代表待插入元素的索引。
                int value = arr[i];
                int j = i - gap;    // j 代表i的上一个元素，相差一个增量gap。

                // j < 0 时退出循环，说明 j 是最小的元素的索引值。
                // 或者 arr[j] <= value 时退出循环，说明 j 是比value小的元素的索引值。
                for (; j >= 0 && arr[j] > value; j -= gap) {
                    arr[j + gap] = arr[j];  // 把元素往后挪。
                }
                arr[j + gap] = value;  //元素值

            }
            // 把每一趟排序的结果也输出一下。
            print(arr);

            // 缩小增量。
            gap /= 2;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 8, 2, 4, 6, 9, 7, 0, 1, 3};

        System.out.print("排序前:  ");
        print(arr);

        shellSort(arr);  //此时已经成功

        System.out.print("排序后:  ");
        print(arr);
    }

    // 打印数组
    public static void print(int[] arr) {
        if (arr == null)    return;
    //遍历并且输出
        for(int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

输出结果：

排序前:  5 8 2 4 6 9 7 0 1 3 5 7 0 1 3 9 8 2 4 6 0 1 3 2 4 6 5 7 8 9 0 1 2 3 4 5 6 7 8 9 排序后:  0 1 2 3 4 5 6 7 8 9 

注意：

对各个分组进行插入的时候并不是先对一个组排序完了再来对另一个组排序，而是轮流对每个组进行排序。

性质：

1、时间复杂度：O(nlogn)

2、空间复杂度：O(1)

3、非稳定排序

4、原地排序

总结

十大排序算法可以说是每个程序员都必须得掌握的，由于考虑到读者，保证每种排序速算法大概三分钟左右就能轻松掌握，所以分开讲解，对于希尔排序精髓就是一个希尔增量，大家了解这个就完全欧克了！但是呢得坚持下去，哪怕在简单的你一看就懂，但是你不看还是不懂的，脚踏实地一起努力输入，看到本篇文章的小伙伴们一起加油吧！