3

この作業バージョンのmergesortをコード化しました：

static int[] merge(int[] first, int[] second){
    int totalsize = first.length + second.length;
    int[] merged_array = new int[totalsize];
    int i = 0, firstpointer = 0, secondpointer = 0;
    while(i < totalsize){
        if(firstpointer == first.length){
            merged_array[i] = second[secondpointer];
            ++secondpointer;
        }
        else if(secondpointer == second.length){
            merged_array[i] = first[firstpointer];
            ++firstpointer;
        }
        else if(first[firstpointer] < second[secondpointer]){
            merged_array[i] = first[firstpointer];
            ++firstpointer;
        }
        else{
            merged_array[i] = second[secondpointer];
            ++secondpointer;
        }
        ++i;
    }
    return merged_array;
}

static int[] mergesort(int[] array){

    if(array.length == 1){
        return array;
    }
    else{
        int length = array.length;
        int[] first = Arrays.copyOfRange(array, 0, (int) length / 2);
        int[] second = Arrays.copyOfRange(array, (int) length / 2, length);
        return merge(mergesort(first), mergesort(second));
    }

}

ただし、お気づきの場合は、親配列の特定の部分のコピーである新しい配列を作成する copyOfRange 関数を使用します。これよりスペース効率の良いマージソート実装が Java にありますか?

4

1 に答える 1

2

重複：マージソートアルゴリズムを使用してインプレースでソートする方法は?

要約: はい、メモリ効率の良いマージソートがありますが、a) 非常に複雑であるか、b) 時間効率が悪い: O(n^2 log n)

基本的に、気にしないでください。実際に節約できるのはそれほど多くのメモリではありません。本当にしたい場合は、代わりにクイックソートを使用してください。

于 2013-02-12T01:05:43.400 に答える