1

MergeSort で問題が発生しました。配列を並べ替えた後、すべてのパスではなく、完全に並べ替えられた配列のみを出力するようにします。私のコードは以下です。配列がソートされたように見えた後、printArray(intArray) を実行しています。多分私はそれを間違った場所に置いていますか？最後の mergesortComparisons 関数で確認できます。

private static int merge(int[] intArray, int first, int n1, int n2) {

        int[] temp = new int[n1+n2];
        int copied = 0, copied1 = 0, copied2 = 0;
        while((copied1 < n1) && (copied2 < n2)){
            if (intArray[first + copied1] < intArray[first + n1 + copied2]) 
                temp[copied++] = intArray[first + copied1++];
            else 
                temp[copied++] = intArray[first + n1 + copied2++];
        }

        while(copied1 < n1)
            temp[copied++] = intArray[first + copied1++];
        while(copied2 < n2) 
            temp[copied++] = intArray[first + n1 +copied2++];

        for(int i = 0; i < n1+n2; i++) {
            numComparisons++;
            intArray[first + i] = temp[i];
        }

        return first;
    }

    public static int mergeSortComparisons(int[] intArray, int first, int last){
        int n1, n2;
        if (last > 1){

            n1 = last/2;
            n2 = last - n1;

            mergeSortComparisons(intArray, first, n1);
            mergeSortComparisons(intArray, first + n1, n2);

            merge(intArray, first, n1, n2);
        }

        printArray(intArray);
        return numComparisons;
    }
4

3 に答える 3

1

中に印刷しないでくださいmergeSortComparisons。ラッパー関数を作成し、そこに出力します。

public static int mergeSort(int[] intArray, int first, int last) {
    int comparisons = mergeSortComparisons(intArray, first, last);
    printArray(intArray);
    return comparisons;
}

ラッパーは時々役に立ちます。

編集：

ラッパーが必要ない場合は、別の簡単な解決策を次に示します。

public static int mergeSortComparisons(int[] intArray, int first, int last, boolean wantToPrint){
    int n1, n2;
    if (last > 1){

        n1 = last/2;
        n2 = last - n1;

        mergeSortComparisons(intArray, first, n1, false);
        mergeSortComparisons(intArray, first + n1, n2, false);

        merge(intArray, first, n1, n2);
    }

    if (wantToPrint) {
        printArray(intArray);
    }

    return numComparisons;
}

外部的に、配列を出力したい場合は、 の値を渡すだけですtrue。このように、配列を印刷せずに同じことを行うこの関数のコピーを作成する必要はありません。配列の印刷をオプションにします。

于 2013-05-05T22:25:16.680 に答える
1

mergeSortComparisons を再帰的に呼び出しているため、printArray への呼び出しは、すべてのマージ後のすべてのパスで発生します。intArray を mergeSortComparisons メソッドから最初に呼び出したコードに返す場合、そこから printArray を呼び出すことができ、一度だけ実行されます。

于 2013-05-05T22:28:19.717 に答える