希尔排序法

一、基本思想

温馨提示

让数组越来越有序，不能只处理相邻的逆序对！

二、希尔排序法的基本原理

温馨提示

• 对元素间距为n/2 的所有数组做插入排序
• 对元素间距为n/4 的所有数组做插入排序
• 对元素间距为n/8 的所有数组做插入排序
• ...
• 对元素间距为1的所有数组做插入排序

三、希尔排序法的简单实现

public class ShellSort {
    private ShellSort() {
    }

    public static <E extends Comparable<E>> void sort(E[] data) {
        int h = data.length / 2;
        while (h >= 1) {

            for (int start = 0; start < h; start++) {
                // 对 data[start,start + h ,start + 2h, start + 3h] ,进行插入排序
                for (int i = start + h; i < data.length; i += h) {
                    E t = data[i];
                    int j;
                    for (j = i; j - h >= 0 && t.compareTo(data[j - h]) < 0; j -= h) {
                        data[j] = data[j - h];
                    }
                    data[j] = t;
                }
            }

            h /= 2;
        }
    }
}

四、希尔排序法的性能

温馨提示

我们可以看到，在50000规模的数据下，这个希尔排序的性能居然可以和归并排序法不相上下，是不是有点可怕，好像进行了4个循环，为什么那么快呢？

五、换个方式实现希尔排序法

    public static <E extends Comparable<E>> void sort(E[] data) {
        int h = data.length / 2;
        while (h >= 1) {
                // 对 data[ h , n] ,进行插入排序
                for (int i = h; i < data.length; i ++) {
                    E t = data[i];
                    int j;
                    for (j = i; j - h >= 0 && t.compareTo(data[j - h]) < 0; j -= h) {
                        data[j] = data[j - h];
                    }
                    data[j] = t;
                }


            h /= 2;
        }
    }

    public static void main(String[] args) {
        int n = 1000000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
        Integer[] arr3 = Arrays.copyOf(arr,arr.length);
        SortingHelper.sortTest("ShellSort", arr);
        SortingHelper.sortTest("MergeSortBU", arr3);
    }

温馨提示

可以看到，依然可以实现，我们将4重循环变成了3重循环。

六、希尔排序——步长序列

温馨提示

步长不再是1,2,4,8....
而是1,4,13,40....
也就是 h * 3 + 1
换一种方式来实现！

    public static <E extends Comparable<E>> void sort2(E[] data) {
        int h = 1;
        while (h < data.length) {
            // 1,4,13,40
            h = h * 3 + 1;
        }
        while (h >= 1) {
            // 对 data[ h , n] ,进行插入排序
            for (int i = h; i < data.length; i++) {
                E t = data[i];
                int j;
                for (j = i; j - h >= 0 && t.compareTo(data[j - h]) < 0; j -= h) {
                    data[j] = data[j - h];
                }
                data[j] = t;
            }


            h /= 3;
        }
    }