希尔排序是基于插入排序的快速排序算法。希尔排序的思想是使数组中任意间隔为h的元素是有序的。这样的数组被称为h有序数组。进行排序时如果h很大，我们就能将元素移动到很远的地方，为实现更小的h有序创造方便。用这中方式，对于任意以一为结尾的h序列，我们都能将数组排序。

希尔排序动态图

代码只需要在插入排序加个外循环即可

public static void sort(Comparable[] a) {    int N = a.length;    int h = 1;    while (h <= N / 3) {        h = 3 * h + 1;    }    while (h >= 1) {        //将数组变为h有序        for (int i = h; i < N; i++) {            //将a[i]插入到a[i-h]            if (less(a[i], a[i - h])) { //小于时，需将 r[i] 插入有序表      Comparable temp = a[i];                int j = i - h;                for (; j >= 0 && less(temp, a[j]); j = j - h) {                    a[j + h] = a[j];//记录后移 [j];                }                a[j + h] = temp;            }        }        h = h / 3;    }}private static void exch(Comparable[] a, int i, int min) {    Comparable t = a[i];    a[i] = a[min];    a[min] = t;}private static boolean less(Comparable v, Comparable w) {    return v.compareTo(w) < 0;}private static void show(Comparable[] a) {    for (int i = 0; i < a.length; i++) {        System.out.print(a[i] + " ");    }}public static void main(String[] args) {    String[] a = new String[]{"t", "g", "c", "p", "f", "w", "v"};    sort(a);    show(a);}