java - 为什么测试顺序会改变测试结果？

Question

我编写了 2 种排序方法(冒泡排序和归并排序)，我知道它们具有不同的效率，因此我想针对不同的数组大小绘制出这些方法。为了检查时间是否符合预期，我进行了一次测试运行，生成了 10000 个随机值并将它们放入一个数组中，对其进行了冒泡排序，然后再次生成它们并进行了合并排序。我都计时了。但是当我查看冒泡排序所花费的时间时，它远远少于合并排序所花费的时间。所以我切换了我先做的那个，现在合并排序是最快的。为什么会发生这种情况，我该如何阻止它？这是我的所有代码。

import java.util.ArrayList;
public class Sorter {
public static <T extends Comparable> boolean isInOrder(ArrayList<T> ar) {
    for (int i = 0; i < ar.size() - 1; i++) {
        if (ar.get(i).compareTo(ar.get(i + 1)) > 0) {
            return false;
        }
    }
    return true;
}

public static <T extends Comparable> boolean isInOrder(T[] ar) {
    for (int i = 0; i < ar.length - 1; i++) {
        if (ar[i].compareTo(ar[i + 1]) > 0) {
            return false;
        }
    }
    return true;
}

private static <T> ArrayList<T> splitArrayList(ArrayList<T> ar, int start, int end) {
    ArrayList<T> toReturn = new ArrayList<>();
    for (int i = start; i < end; i++) {
        toReturn.add(ar.get(i));
    }
    return toReturn;
}

private static <T extends Comparable> ArrayList<T> merge(ArrayList<T> a, ArrayList<T> b) {
    ArrayList<T> toReturn = new ArrayList<>();
    int bIndex = 0;
    for (T value : a) {
        while (bIndex < b.size() && (b.get(bIndex).compareTo(value) < 0)) {
            toReturn.add(b.get(bIndex));
            bIndex++;
        }
        toReturn.add(value);
    }
    if (bIndex <= b.size()) {
        for (int i = bIndex; i < b.size(); i++) {
            toReturn.add(b.get(i));
        }
    }
    return toReturn;
}

public static <T extends Comparable> ArrayList<T> mergeSort(ArrayList<T> ar) {
    if (ar.size() == 1) return ar;
    else {
        int splitPoint = ar.size() / 2;
        ArrayList<T> split1 = mergeSort(splitArrayList(ar, 0, ar.size() / 2));
        ArrayList<T> split2 = mergeSort(splitArrayList(ar, ar.size() / 2, ar.size()));
        ar = merge(split1, split2);
    }
    return ar;
}


public static <T extends Comparable> ArrayList<T> bubbleSort(ArrayList<T> ar) {
    boolean isSorted = false;
    while (!isSorted) {
        isSorted = true;
        for (int i = 0; i < ar.size() - 1; i++) {
            if (ar.get(i).compareTo(ar.get(i + 1)) > 1) {
                T holdValue = ar.get(i);
                ar.set(i, ar.get(i + 1));
                ar.set(i + 1, holdValue);
                isSorted = false;
            }
        }
    }
    return ar;
}

public static void main(String[] args) {
    ArrayList<Double> test = generateRandomData(100000);
    double t1 = System.currentTimeMillis();
    mergeSort(test);
    double t2 = System.currentTimeMillis();
    test = generateRandomData(100000);
    double t3 = System.currentTimeMillis();
    bubbleSort(test);
    double t4 = System.currentTimeMillis();
    System.out.println("Merge sort " + (t2-t1) + " Bubble Sort "  + (t4-t3));
}
public static ArrayList<Double> generateRandomData(int size){
    ArrayList<Double> toReturn = new ArrayList<>();
    for (int i = 0; i < size; i++) {
        toReturn.add(Math.random());
    }
    return toReturn;
}
}

Answer 1

这看起来很奇怪的原因是因为您的 BubbleSort 实际上并未对数组进行排序。使用您的代码，给定一个数组 [6.0, 5.0, 4.0, 3.0, 2.0, 1.0]，在运行我们结束的方法之后:[6.0, 5.0, 4.0, 3.0, 2.0 , 1.0]。嗯。这看起来很像我们开始的时候。

错误很简单。在行中

if (ar.get(i).compareTo(ar.get(i + 1)) > 1) {

compareTo 方法返回 -1、0、1 之一，具体取决于是否参数分别小于、等于或大于。改成

if (ar.get(i).compareTo(ar.get(i + 1)) > 0) {

它会正常工作(而且运行非常非常慢)。

当您的 MergeSort 正常工作时，您应该会看到 BubbleSort 和 MergeSort 之间截然不同的画面。