0

私はマージソートアルゴリズムを実装するプログラムを作成していますが、毎回2つの部分に分割するのではなく、毎回3つの部分に分割し、再帰的にマージソートします。基本的にはマージソートですが、2つの部分でマージソートするのではなく、毎回3でマージソートするので、かなり楽しいですね。まあ、それは間違いなくそうではありません。

これが私のマージソートの実装です：

public static void mergesort(int[] data) {
    int elements = data.length;
    int sizeLeft;
    int sizeCenter;
    int sizeRight;

    if (elements > 2) {

        if (elements % 3 == 0) {
            sizeLeft = elements / 3;
            sizeCenter = elements / 3;
            sizeRight = elements / 3;
        } else if (elements % 3 == 1) {
            sizeLeft = (elements / 3) + 1;
            sizeCenter = elements / 3;
            sizeRight = elements / 3;
        } else { //if (elements % 3 == 2)
            sizeLeft = (elements / 3) + 1;
            sizeCenter = elements / 3;
            sizeRight = (elements / 3) + 1;
        }

        int[] left = makeArray(data, 0, sizeLeft);
        int[] center = makeArray(data, sizeLeft, sizeCenter);
        int[] right = makeArray(data, sizeLeft + sizeCenter, sizeRight);

        mergesort(left);
        mergesort(center);
        mergesort(right);

        merge(data, left, center, right);
    }
}

マージ方法は次のとおりです。

public static void merge(int[] data, int[] left, int[] center, int[] right) {
    int[] temp = new int[left.length + center.length + right.length];
    int copiedTotal = 0;
    int copiedLeft = 0;
    int copiedCenter = 0;
    int copiedRight = 0;

    while ((copiedLeft < left.length)
            && (copiedCenter < center.length)
            && (copiedRight < right.length)) {

        if ((left[copiedLeft] < center[copiedCenter])
                && (left[copiedLeft] < right[copiedRight])) {

            temp[copiedTotal++] = left[(copiedLeft++)];
        } else if ((center[copiedCenter] < left[copiedLeft])
                && (center[copiedCenter] < right[copiedRight])) {
            temp[copiedTotal++] = center[copiedCenter++];
        } else {
            temp[copiedTotal++] = right[copiedRight++];
        }
    }

    while ((copiedLeft < left.length) && (copiedCenter < center.length)) {
        if (left[copiedLeft] < center[copiedCenter]) {
            temp[copiedTotal++] = left[copiedLeft++];
        } else{
            temp[copiedTotal++] = center[copiedCenter++];
        }
    }

    while ((copiedLeft < left.length) && (copiedRight < right.length)) {
        if (left[copiedLeft] < right[copiedRight]) {
            temp[copiedTotal++] = left[copiedLeft++];
        } else{
            temp[copiedTotal++] = right[copiedRight++];
        }
    }

    while ((copiedCenter < center.length) && (copiedRight < right.length)) {
        if (center[copiedCenter] < right[copiedRight]) {
            temp[copiedTotal++] = center[copiedCenter++];
        } else{
            temp[copiedTotal++] = right[copiedRight++];
        }
    }

    while (copiedLeft < left.length) {
        temp[copiedTotal++] = left[copiedLeft++];
    }

    while (copiedCenter < center.length) {
        temp[copiedTotal++] = center[copiedCenter++];
    }

    while (copiedRight < right.length) {
        temp[copiedTotal++] = right[copiedRight++];
    }
    System.arraycopy(temp, 0, data, 0, left.length + center.length + right.length);
//        for (int i = 0; i < data.length; i++) {
//            if ((copiedRight >= right.length) && (copiedCenter >= center.length)) {
//                data[i] = left[copiedLeft];    // take from left
//                copiedLeft++;
//            } else if ((copiedRight >= right.length) && (copiedLeft >= left.length)) {
//                data[i] = center[copiedCenter];    // take from left
//                copiedCenter++;
//            } else if ((copiedCenter >= center.length) && (copiedLeft >= left.length)) {
//                data[i] = right[copiedRight];    // take from left
//                copiedRight++;
//            } else if ((copiedLeft < left.length
//                    && left[copiedLeft] <= right[copiedRight])
//                    && left[copiedLeft] <= center[copiedCenter]) {
//
//                data[i] = left[copiedLeft];    // take from left
//                copiedLeft++;
//
//            } else if ((copiedRight >= right.length) && (copiedLeft >= left.length)
//                    || (copiedCenter < center.length
//                    && center[copiedCenter] <= right[copiedRight])
//                    && center[copiedCenter] <= left[copiedLeft]) {
//
//                data[i] = center[copiedCenter];    // take from center
//                copiedCenter++;
//            } else {
//                data[i] = right[copiedRight];
//                copiedRight++;// take from center
//            }
//
//        }
    }
}

マージメソッド内のコメントには、私が作成しようとした別のマージメソッドがありますが、それはまったくうまく終了せず、事態はさらに複雑になりましたが、参照用にそのままにしておきました。

問題は、これがまったく機能しないことです。たとえば、次のような場合です。

入力：6 5 4 3 2 1

それから私は持っているでしょう：

出力：[2、1、4、3、6、5]

私は正直にこれに一生懸命努力しました、そして2日間続けて、私はこの種のマージソートについて聞いているのは2人だけでした、そしてGoogleで何時間も検索した後、私はここで同様の質問（理解するには複雑すぎました）と別のスレッドを見つけました決して答えられなかったwikiの答えで。

もちろん、私は学ぼうとしているので直接的な解決策を求めているわけではありませんが、ヒントやヒント、そして私が間違ったことをしたことが大いに役立ちます。

前もって感謝します。

4

1 に答える 1

2

問題は、2要素の配列がある場合は何もしないことだと思われます。並べ替える必要があります。例をとると：[6,5,4,3,2,1]、再帰の2番目のステップには[2,1]があります。[4,3]と[6,5]そしてあなたはそれらをそのようにマージします。それらを最初にソートすると、正しい順序が得られます。マージ関数でそれらをソートするには、以下を追加する必要があります。

if ((elements==2)&&(data[1]<data[0])){
 int aux = data[1];
 data[1] = data[0];
 data[0] = aux;

}

それが役に立てば幸い。

アップデート

純粋なマージソートが必要な場合は、（コメントで説明したように）次のコードを追加してみてください。

if (elements==2){
 int[] center = [];
 int[] left = makeArray(data,0,1);
 int[] right =makeArray(data,1,1);

 mergesort(left); //you can call these methods or not, on a empty or 1 element array they dont have an effect
 mergesort(center);
 mergesort(right);

 merge(data, left, center, right); //it should work well when center is an empty array

}

UPDATE 2 表示したコードをリファクタリングして、見栄えを良くすることができます。基本的な考え方は、Javaで空の配列を使用でき、マージ関数がそれを適切に処理することです。私の主張をもう少し明確にしたいと思います。

于 2012-05-20T15:45:43.847 に答える