データ構造基盤集計ソートjava実装

java実装の集計ソート
実現構想.

シーケンスは、隣接する2つの要素ごとに集計され、n/2のシーケンスが得られ、各シーケンスは2つの要素を含む.

は、上記のシーケンスをさらに集計する、各シーケンスには4つの要素

がある.

手順2

を繰り返す

最後のステップは、2つのシーケンスの合計長が元の配列の長さ

である2つのシーケンスを集計することである.
クイックソートとの比較

の集計ソートには追加の空間が必要であり、空間複雑度はO(n)であり、高速で追加の空間を必要としない

は安定であり、速い列は安定ではない

である.

の2つのソートは実は少し分治法の味がして、ソートを小さな問題に分解して、これらの問題を組み合わせて原問題の解を得ました.

高速は、まず元の配列を2つのブロックに分割し、1つは中間位置の値より小さく、1つは中間位置の値より大きい.各ブロックの要素の数が1になるまで、各ブロックを繰り返します.大きいものから小さいものへ.

は、単一要素ごとに集計され、2つの要素を含むシーケンスを集計し、上記の手順を繰り返します.小さい頃から大きいです.

まず統合アルゴリズムを実現します
コードは次のとおりです.

 *      ，    
     * 
     * @param data
     *              
     * @param low
     *                
     * @param mid
     *                    ，        mid+1
     * @param high
     *                 
     */
    private static void merge(Integer[] data, int low, int mid, int high) {
        if (mid < low || high < mid) {
            return;
        }

        //     
        System.out.println("2Arrays:" + Arrays.toString(Arrays.copyOfRange(data, low, mid + 1))
                + Arrays.toString(Arrays.copyOfRange(data, mid + 1, high + 1)));

        //       ，         ，      
        Integer[] temp = new Integer[high - low + 1];

        int l = low;
        int m = mid + 1;
        int i = 0;

        while (l <= mid && m <= high) {
            if (data[l] < data[m]) {
                temp[i++] = data[l++];
            } else {
                temp[i++] = data[m++];
            }
        }

        //                
        if (l <= mid) {
            while (l <= mid)
                temp[i++] = data[l++];
        }

        if (m <= high) {
            while (m <= high)
                temp[i++] = data[m++];
        }

        //      k   low   ，    0
        int k = low;
        for (int d : temp) {
            data[k++] = d;
        }

        System.out.println("Merged: " + Arrays.toString(Arrays.copyOfRange(data, low, high + 1)));

    }

一度に合併する.
各秩序テーブルの長さがrangeであると仮定すると、数字はlength/rangeサブシーケンス:0~range-1;range ~ range*2-1;などなど.注意:秩序テーブルの個数は偶数で、長さはrangeです.-秩序テーブルの長さが奇数(最後のサブ継続テーブルが空であり、考慮されない)-秩序テーブルの長さは偶数であり、最後のサブシーケンスの長さはrangeより小さい

    /** *           range          *         data.length/range     *          3   ： * 1.             * 2.           ，       * 3.           ，        * * @param data *   ，   0   * @param length */
    private static void mergePass(Integer[] data, int range) {

        int i = 0;
        //       ，        
        while (i + 2 * range - 1 < data.length - 1) {
            merge(data, i, i + range - 1, i + 2 * range - 1);
            i = i + 2 * range; //    i     
        }

        //               ，              
        if (i + range - 1 < data.length - 1) {
            merge(data, i, i + range - 1, data.length - 1);
        }

        //           ，            

        //            ？    ？

    }

にじゅうマージソート

    /** *        * @param data        */
    private static void mergeSort(Integer[] data) {

        //len       
        int len = 1;
        while (len < data.length) {
            mergePass(data, len);
            len *= 2;

        }

    }

ここでは前回の集計の繰り返し呼び出しですが、range値を呼び出すたびに2倍になります.range最大はrange*2がdata以上である.lengthの時.
テストプログラム

    public static void main(String[] args) {
        Random r = new Random();
        Integer[] data = new Integer[r.nextInt(10) + 8];

        for (int ii = 0; ii < 10; ii++) {
            for (int i = 0; i < data.length; i++) {
                data[i] = r.nextInt(30);
            }
            System.out.println("------------------------");
            System.out.println(Arrays.toString(data));

            mergeSort(data);

            System.out.println(Arrays.toString(data));
        }

しゅつりょく

------------------------
[8, 2, 4, 11, 9, 22, 23, 17, 1, 2, 25, 28, 15, 16, 9, 17]
2Arrays:[8][2]
Merged: [2, 8]
2Arrays:[4][11]
Merged: [4, 11]
2Arrays:[9][22]
Merged: [9, 22]
2Arrays:[23][17]
Merged: [17, 23]
2Arrays:[1][2]
Merged: [1, 2]
2Arrays:[25][28]
Merged: [25, 28]
2Arrays:[15][16]
Merged: [15, 16]
2Arrays:[9][17]
Merged: [9, 17]
2Arrays:[2, 8][4, 11]
Merged: [2, 4, 8, 11]
2Arrays:[9, 22][17, 23]
Merged: [9, 17, 22, 23]
2Arrays:[1, 2][25, 28]
Merged: [1, 2, 25, 28]
2Arrays:[15, 16][9, 17]
Merged: [9, 15, 16, 17]
2Arrays:[2, 4, 8, 11][9, 17, 22, 23]
Merged: [2, 4, 8, 9, 11, 17, 22, 23]
2Arrays:[1, 2, 25, 28][9, 15, 16, 17]
Merged: [1, 2, 9, 15, 16, 17, 25, 28]
2Arrays:[2, 4, 8, 9, 11, 17, 22, 23][1, 2, 9, 15, 16, 17, 25, 28]
Merged: [1, 2, 2, 4, 8, 9, 9, 11, 15, 16, 17, 17, 22, 23, 25, 28]
[1, 2, 2, 4, 8, 9, 9, 11, 15, 16, 17, 17, 22, 23, 25, 28] ------------------------

上の出力から集計の過程がわかります.
参考記事
http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.5.1.1.htm