0

昨日からマージソートの例(効率的なもの)を読んでいますが、コードを見てもどのように機能するのかまだ理解できません:

private static void sort(int[] list) {
    a = list;
    int n = a.length;
    // according to variant either/or:
    b = new int[n];
    b = new int[(n + 1) / 2];
    mergesort(0, n - 1);
}

private static void mergesort(int first, int last) {
    if (first < last) {
        int mid = (first + last) / 2;
        mergesort(first, mid);
        mergesort(mid + 1, last);
        merge(first, mid, last);
    }
}

ここまではアルゴリズムを理解するのに問題はありませんが、次の方法に混乱があります。

private static void merge(int first, int mid, int last) {
    int i, j, k;

    i = 0;
    j = first;

    while (j <= mid)
        b[i++] = a[j++]; // *j's value is now mid*

    i = 0; // *i is reset to 0, nothing's been done to j*
    k = first;


    // *before entering the following while loop, j still carries mid's value*
    while (k < j && j <= last)
        if (b[i] <= a[j])
            a[k++] = b[i++];
        else
            a[k++] = a[j++];        

    // copy back remaining elements of first half (if any)
    while (k < j)
        a[k++] = b[i++];
}

2 番目の while ループに入ると、while (k < j && j <= last)この並べ替えのしくみがわかりません。私が理解したことから、配列の前半aはすでに補助配列にコピーされており、次bは配列全体a[j++]（後半）を補助配列と比較して配置しb[i++]、小さい方の配列要素を取得して配置できるようにします。 it in arrayaを使用して、配列を昇順に並べ替えます。

しかし、なぜwhile (k < j && j <= last)ですか？k < j補助配列からすべての値を取得する必要があるため、十分に論理的に聞こえますが、なぜj <= lastですか? そして、なぜ私たちはできないのwhile (k <= last)ですか？

また、上記のコードの j の値に関する私の理解が正しいことを誰かが断言できますか?

4

1 に答える 1

0

k < j 補助配列bにまだ要素が含まれていることを示します

j <= lasta の 2 番目の部分にまだ要素が含まれていることを示します

jがlast+1になると、境界を越えて配列インデックスにアクセスするk <= last可能性があるため、ここでは使用できません

コメントするには長すぎます。ここに追加:

このバリアントは、使用可能なメモリが限られている場合 (大規模なデータセット) に役立ちます。いくつかのチュートリアルで言及されています（Delphiのアルゴリズムに関するJ.Bucknallの本で会ったことがあります）。安定している ( (b[i] <= a[j]) が安定性を保持している場合。データをまったくコピーしない方がよいため、通常は高速ではありませんが、たとえば、「トリガー」ソースと宛先配列 (ポインタ）すべての段階で

于 2013-04-13T11:08:09.780 に答える