五、希尔排序

希尔排序法(缩小增量法) 属于插入排序，是将整个无序列分割成若干小的子序列分别进行【插入排序】的方法。

我们知道，插入排序适合有序度高的数组排序。而希尔排序就是一个可以先使数组部分有序，然后通过插入排序实现高效率的排序算法。如果对插入排序没有一个明确的概念，没有实际使用过插入排序的话，建议先去把插入排序走一遍。希尔排序是基于插入排序的！下面放图解~

一个简单的希尔排序图解.png

希尔排序更高效的原因是它权衡了子数组的规模和有序性。排序之初，各个子数组都很短，排序之后子数组都是部分有序的，这两种情况都很适合插入排序。子数组部分有序的程度取决于递增序列的选择。透彻理解希尔排序的性能至今仍然是一项挑战。实际上，希尔排序是我们唯一无法准确描述其对于乱序的数组的性能特征的排序方法

public static void main(String[] args) {
        Comparable[] a = new Comparable[]{2, 6, 4, 1, 6, 9, 7, 8, 5, 23, 5, 7, 12, 54, 23, 43, 11};
        sort(a);
    }

    /**
     * 希尔排序
     *
     * @param a
     */
    public static void sort(Comparable[] a) { // 将a[]按升序排列
        int N = a.length;
        int h = 1;
        while (h < N / 3) h = 3 * h + 1;//初始h

        //此循环用于逐渐减小h的值
        while (h >= 1) {
            //从第h位往右边循环
            for (int i = h; i < N; i++) {
                //循环往左比较h有序数组
                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
                    exch(a, j, j - h);
                    show(a);
                }
            }
            h = h / 3;
        }
    }

    /**
     * 左边的数字比右边的小吗？
     *
     * @param v
     * @param w
     * @return
     */
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    /**
     * 交换数组两个元素
     *
     * @param a 数组
     * @param i 要交换的数组下标
     * @param j 要交换的数组下标
     */
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    /**
     * 打印数组
     *
     * @param a
     */
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }

运行程序：

image.png

上结果比较一下希尔排序和插入排序。（详细测试代码就不贴了，有兴趣的自己去实现或者文章末尾的地址有源码）

image.png

有意思的是，由插入排序到希尔排序，一个小小的改变就突破了平方级别的运行时间的屏障。这正是许多算法设计问题想要达到的目标。
有经验的程序员有时会选择希尔排序，因为对于中等大小的数组它的运行时间是可以接受的。它的代码量很小，且不需要使用额外的内存空间。在下面的几节中我们会看到更加高效的算法，但除了对于很大的 N，它们可能只会比希尔排序快两倍（可能还达不到），而且更复杂。如果你需要解决一个排序问题而又没有系统排序函数可用（例如直接接触硬件或是运行于嵌入式系统中的代码），可以先用希尔排序，然后再考虑是否值得将它替换为更加复杂的排序算法。

---

  本系列所有的代码都会在github同步更新，立刻前往