汤科资源网

希尔排序是基于插入排序的快速排序算法。希尔排序的思想是使数组中任意间隔为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);}