算法——初级排序算法之希尔排序

介绍&特点

对于大规模乱序数组插入排序很慢，因为它只会交换相邻的元素，元素只会一点一点地从数组一端移到另一端。例如，如果主键最小的元素正好在数组的尽头，要将它挪到正确的位置就需要N-1次移到。希尔排序为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。

通过提升速度来解决其他方式无法解决的问题是研究算法的设计和性能的主要原因之一

代码

public class HillSort {

    public static void main(String[] args) {
        Integer[] arr = {1, 2, 3, 4, 5, 22, 2, 12, 13, 21, 9};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    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], a[i-2*h], a[i-3*h] 之中
                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
                    exchange(a, j, j - h);
                }
                h = h / 3;
            }
        }
    }

    // 比较v是否小于w
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    private static void exchange(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    private static void show(Comparable[] a) {
        for (Comparable comparable : a) {
            System.out.println("a[i]= " + comparable);
        }
    }

    private static boolean isSorted(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            if (less(a[i], a[i - 1])) {
                return false;
            }
        }
        return true;
    }
}