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

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

你所有的计时 block 都是这样的:

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 block 并放入循环中，从而使整个代码更紧凑且更易于维护。此外，您可以针对不同的数组大小围绕该循环创建另一个循环。

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