1

我无法计算 Java 中合并排序的比较次数。下面是我的代码。不确定我是否将其放置在错误的位置等。

任何帮助都非常感谢，谢谢。

private static int merge(int[] intArray, int first, int n1, int n2) {
    int numComparisons = 0;
        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 numComparisons;
    }


    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);
        }

        return first;
    }
4

1 回答 1

1

如果要计算比较次数，请执行比较步骤，将其重构为方法，然后检测方法。你numComparisons在错误的地方增加。

private static boolean lessThan(int[] ia, int leftIndex, int rightIndex) {
    numComparisons++;
    return ia[leftIndex] < ia[rightIndex];
}

使用它而不是靠近顶部的比较线merge。

此外，编写 JUnit 测试以确保您的排序工作正常。最后，你需要让你的所有方法都是静态的吗？

于 2013-05-05T21:03:17.543 回答