如何测试特定的排序算法是否实际实现？

Question

我正在寻找一个自动化测试来验证合并排序是否实际实现。我知道如何验证排序算法是否确实可以排序，但是如何验证是否使用了合并排序而不是冒泡排序？

我回顾了以前的讲座，他们为 20,000 个元素列表硬编码了 0.01 秒的目标时间。他们没有对如何得出 0.01 秒发表任何评论。所以我的问题是如何验证合并排序是否已实现？

下面的代码显示了讲座提出的这个“幽灵”0.01。这个0.01是哪里来的？

仅供参考，BIG_SORT_SIZE = 20,000

 /** @return true if test passes, else false */
 private boolean testTimeToSortBigList() {
    final int bigNum = BIG_SORT_SIZE; //okay, not THAT big
    final double maxTime = 0.02;
    final double targetTime = 0.01;
    try {
        IndexedUnsortedList<Integer> list1 = newList();
        Random rand = new Random(123);
        for (int i = 0; i < bigNum; i++) {
            list1.add(new Integer(rand.nextInt()));
        }

        long startTime = System.nanoTime();
        Sort.sort(list1);
        long endTime = System.nanoTime();
        long totalTime = endTime - startTime;
        double seconds = (double)totalTime/10e9;
        System.out.printf("\nTime to sort %d random integers: %.3f seconds\n", bigNum, seconds);
        System.out.printf("Target time < %.3f seconds. Time > %.3f suggests O(n^2) runtime.\n", targetTime, maxTime);

        return (seconds < maxTime);
    } catch (Exception e) {
        System.out.printf("caught unexpected %s\n", e.toString());
        return false;
    }
}   

Answer 1

您可以尝试使用最坏情况的示例来测试各种算法的时间差异。例如，对一个很长的递减数字序列进行冒泡排序，其执行速度将比对同一序列进行合并排序慢得多。它不是自动化的，但如果您想检查算法，这可能是一种暴力方法。