クラシックアルゴリズムの集計ソート

10502 ワード

集計アルゴリズム
集計アルゴリズムの核心は分而治之である.時間複雑度O(n logn)、比較的安定
アルゴリズムステップ
1.統合後のシーケンスを格納するための空間を開く.2つのポインタを設定し、開始位置はそれぞれ2つの並べ替えられたシーケンスの開始位置3にある.2つのポインタが表す要素を比較し、より小さい要素をマージスペースに入れ、ポインタを後ろに移動します.1つのポインタが末尾5に達するまで、手順3を繰り返す.別のシーケンスの残りの要素を連結シーケンスの末尾にコピー
ダイレクトコード
public int[] sort(int[] sourceArray) {

        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        if (arr.length < 2) {
            return arr;
        }
        //      ,      
        int middle = (int) Math.floor(arr.length / 2);

        int[] left = Arrays.copyOfRange(arr, 0, middle);

        int[] right = Arrays.copyOfRange(arr, middle, arr.length);
		//      、  
        return merge(sort(left), sort(right));
    }
 public int[] merge(int[] left, int[] right) {

        int[] result = new int[left.length + right.length];//   ,    
        int i = 0;

        while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);//       ,  left  
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);//       ,  right  
            }
        }

        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }

        return result;
    }