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，因此每次合并后的每次传递都会调用 printArray。如果您将 intArray 从 mergeSortComparisons 方法返回到最初调用它的代码，您应该能够从那里调用 printArray 并且它只会执行一次。

于 2013-05-05T22:28:19.717 回答
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 回答
0

因为您调用printArraywithin mergeSortComparisons，所以每次调用 ofmergeSortComparisons都会有一行与之关联的输出。由于mergeSortComparisons是递归的，这意味着您会为每个递归步骤获得一行输出。

最简单的解决方案是将其从您最初调用的任何位置删除printArray并移动mergeSortComparisons到任何位置。mergeSortComparisons

于 2013-05-05T22:30:22.003 回答