如何一步测量排序算法的时间？

Question

我正在做一项练习，但我被困在一个点上

我想使用七个不同的数组来测量 3 种排序算法（冒泡、插入和选择）的排序时间。我尝试了多种方法，但无法在一步中测量所有数组的所有三种算法的排序时间。我的程序应该：

• 用整数随机填充数组
• 对它们进行排序
• 测量时间
• 打印时间

结果总是 0 毫秒，但不可能是这样，因为我尝试了 100 万个整数数组，所以不可能出现 0 毫秒。最后，我尝试了“for 循环”来实现我将要做什么。

我应该写下我的所有方法，因为您可能会在其他方法中发现其他错误。

public static void randomlyFillArray(int[] array, int a, int b) {
    for (int i = 0; i < array.length; i++) {
        array[i] = randomInt(a, b);
    }
}

public static int randomInt(int a, int b) {
    return (int) ((b - a + 1) * Math.random() + a);

}

public static void SelectionSort(int[] array) {

    for (int i = 0; i < array.length - 1; i++) {
        for (int j = i + 1; j < array.length; j++) {
            if (array[i] > array[j]) {
                // ... Exchange elements
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }
}

public static void insertionSort(int[] array) {
    int i, j, temp;
    for (i = 1; i < array.length; i++) {
        temp = array[i];
        j = i;
        while (j > 0 && array[j - 1] > temp) {
            array[j] = array[j - 1];
            j--;
        }
        array[j] = temp;
    }
}

public static void bubbleSort(int[] array) {
    boolean swapped = true;
    int j = 0;
    int temp;
    while (swapped) {
        swapped = false;
        j++;
        for (int i = 0; i < array.length - j; i++) {
            if (array[i] > array[i + 1]) {
                temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
                swapped = true;
            }
        }
    }
}

public static void main(String[] args) {
    // int[] array500 = new int[500];  //These are my arrays that I should do the process for //each one.
    // int[] array1000 = new int[1000];
    // int[] array5000 = new int[5000];
    // int[] array10000 = new int[10000];
    // int[] array50000 = new int[50000];
    // int[] array100000 = new int[100000];
    // int[] array500000 = new int[500000];
    // int[] array1000000 = new int[1000000];
    for (int i = 0; i < 4; i++) {

        int[] array = new int[500];
        if (i == 1) {
            randomlyFillArray(array, 1, 1000);
            SelectionSort(array);

            long startTime = System.currentTimeMillis();
            long total = 0;

            long stopTime = System.currentTimeMillis();
            long elapsedTime = stopTime - startTime;
            SelectionSort(array);
            System.out.println("SelectionSort for 500 integer :  "
                    + elapsedTime);

        } else if (i == 2) {
            randomlyFillArray(array, 1, 1000);
            insertionSort(array);
            long startTime = System.currentTimeMillis();

            long total = 0;

            long stopTime = System.currentTimeMillis();
            long elapsedTime = stopTime - startTime;
            insertionSort(array);
            System.out.println("InsertionSort for 500 integer :  "
                    + elapsedTime);
        } else if (i == 3) {
            randomlyFillArray(array, 1, 1000);
            bubbleSort(array);

            long startTime = System.currentTimeMillis();
            long total = 0;

            long stopTime = System.currentTimeMillis();
            long elapsedTime = stopTime - startTime;
            bubbleSort(array);

            System.out.println("BubbleSort for 500 integer :  "
                    + elapsedTime);

        }

    }

}

感谢您对 stackoverflow 家族的所有建议。

真挚地。

Answer 1

所有的计时块看起来都是这样的：

randomlyFillArray(array, 1, 1000);
SelectionSort(array);
long startTime = System.currentTimeMillis();
long total = 0;
long stopTime = System.currentTimeMillis();
long elapsedTime = stopTime - startTime;
SelectionSort(array);
System.out.println("SelectionSort for 500 integer :  " + elapsedTime);

您排序，然后获取开始时间，然后立即获取结束时间，然后再次排序，然后打印时间。您必须在排序后获取结束时间。如果您有理由进行两次排序（“预热”JVM？），请确保在执行定时排序之前重新随机化数组。对已排序数组进行排序的算法的性能可能会有很大不同。

randomlyFillArray(array, 1, 1000);
long startTime = System.currentTimeMillis();
long total = 0;  // this thing is never used...
SelectionSort(array); // move this line between start time and end time!
long stopTime = System.currentTimeMillis();
long elapsedTime = stopTime - startTime;
System.out.println("SelectionSort for 500 integer :  " + elapsedTime);

此外，对于每种类型来说，大部分代码都是相同的。您可以将这些部分移出if/else块并移入循环，使整个代码更紧凑且更易于维护。此外，您还可以针对不同的数组大小围绕该循环创建另一个循环。

for (int num : new int[] {500, 1000, 5000, ...}) {
    for (int i = 0; i < 4; i++) {
        String sort = null;
        int[] array = new int[num];
        randomlyFillArray(array, 1, 1000);
        long startTime = System.currentTimeMillis();
        if (i == 1) {
            sort = "SelectionSort";
            SelectionSort(array);
        } else if (i == ...) {
            // analogeous for other sorts
        }
        long stopTime = System.currentTimeMillis();
        long elapsedTime = stopTime - startTime;
        System.out.println(sort + " for " + num + " integers: " + elapsedTime);
    }
}