ソートアルゴリズム-集計ソート

紹介する
集計ソート(英語:Merge sort、またはmergesort)は、集計操作に有効なソートアルゴリズムであり、効率はO(n log n)である.このアルゴリズムは分割法(Divide and Conquer)を用いた非常に典型的な応用であり,各層の分割再帰は同時に行うことができる.
マージ操作
集計操作は集計アルゴリズムとも呼ばれ、2つの並べ替えられたシーケンスを1つのシーケンスに統合する操作を指す.集計ソートアルゴリズムは集計操作に依存する.
反復法

は、統合されたシーケンスを格納するために使用される2つの並べ替えられたシーケンスの和の大きさを有する空間を申請する.

は、2つのポインタを設定し、最初の位置はそれぞれ2つの並べ替えられたシーケンスの開始位置である.

は、2つのポインタが指す要素を比較し、比較的小さい要素を選択してマージ空間に入れ、ポインタを次の位置に移動する.

ステップ3は、あるポインタがシーケンスの最後に到達するまで繰り返される.

は、別のシーケンスの残りのすべての要素を連結シーケンスの最後に直接コピーします.

再帰法
原理は以下の通りである(シーケンスにn個の要素があると仮定する):

シーケンスは、隣接する2つの数字毎に集計動作を行い、floor(n/2)を形成する.

シーケンスで、ソート後の各シーケンスには2つの要素が含まれます.

上記シーケンスを再び集計し、floor(n/4)を形成する.

個のシーケンスで、各シーケンスは4つの要素を含む.

すべての要素が並べ替えられるまで、手順2を繰り返します.

コード#コード#

/** * Created by lysongzi on 16/3/2. *      */
public class MergeSort {

    public static void sort(int[] arr){
        int[] reg = new int[arr.length];
        merge_recursive(arr, reg, 0, arr.length - 1);
    }

    private static void merge_recursive(int[] arr, int[] reg, int start, int end){
        if (start >= end)
            return;

        int len = end - start;
        //     
        int mid = (len >> 2) + start;

        //            
        int sls = start, els = mid;
        int srs = mid + 1, ers = end;
        merge_recursive(arr, reg, sls, els);
        merge_recursive(arr, reg, srs, ers);

        int pos = start;
        //           ,                ,            
        while (sls <= els && srs <= ers)
            reg[pos++] = arr[sls] < arr[srs] ? arr[sls++] : arr[srs++];

        //           ,                 
        while (sls <= els)
            reg[pos++] = arr[sls++];

        //           ,                 
        while (srs <= ers)
            reg[pos++] = arr[srs++];

        //          arr 
        for (pos = start; pos <= end; pos++)
            arr[pos] = reg[pos];
    }
}