亚洲国产日韩欧美一区二区三区,精品亚洲国产成人av在线,国产99视频精品免视看7,99国产精品久久久久久久成人热,欧美日韩亚洲国产综合乱

插入排序：對于隨機排列長度為N且主見不重復的數(shù)組，平均情況下插入排序需要~N^2/4次比較以及~N^2/4。最壞情況下需要~N^2/2次比較和~N^2/2次交換。

• 第一個問題：想請教一下這個效率是怎么計算的？

希爾排序是基于插入排序所改進的算法。書上是這樣描述的：中心思想是使數(shù)組中任意間隔為h的元素都是有序的。這樣的數(shù)組被稱為h有序數(shù)組。也就是說，一個h有序數(shù)組就是h個互相獨立的有序數(shù)組編織在一起組成一個數(shù)組。
這樣說我是能夠理解的，但是它的代碼有點令我難以理解。

//一些簡單的通用性代碼就不粘貼了，減少篇幅，以免各位看官看的煩
    public static void sort(Comparable[] a) {
        int n = a.length;

        // 3x+1 increment sequence:  1, 4, 13, 40, 121, 364, 1093, ... 
        int h = 1;
        while (h < n/3) h = 3*h + 1; 

        while (h >= 1) {
            for (int i = h; i < n; i++) {、
                //less是用來比較大小的，a[j]<[j-h]
                for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
                    //交換a[j]和a[j-h]的位置
                    exch(a, j, j-h);
                }
            }
            assert isHsorted(a, h); //判斷是否有序的代碼
            h /= 3;
        }
        assert isSorted(a);
    }

• 第二個問題是：h這個遞增序列是什么意思？它有什么作用？為什么是h=3*h+1？

• 第三個問題是：書上說最壞的情況是N^(3/2)。N是數(shù)組大小。這個效率是如何計算出來的？