实测插入排序速度太快

Question

我在 Java 中通过向它们提供具有随机生成的数字的数组来加速测试各种排序算法，并且我得到了插入排序的奇怪结果。

我使用 System.nanoTime() 来测量运行时间，即使在对大型数组进行排序时，插入排序的值也低于快速排序和归并排序，这似乎是错误的。我在程序中看到冒泡排序或选择排序的正常（慢）运行时间，所以我认为我不正确地测量了 insertionSort 的速度，但我不确定如何：

public static int[] insertionSort(int[] array) {
    long startTime = System.nanoTime();

    int current;
    int innerIdx;

    int arrayLength = array.length;
    for (int idx = 1; idx < arrayLength; idx++) {
        // iterate through the array, happens just once
        current = array[idx];
        for (innerIdx = idx - 1; current < array[innerIdx] && innerIdx >= 0; innerIdx--) {
            // while current is "traveling" over larger values in array
            array[innerIdx + 1] = array[innerIdx];
            // shift the array elements over by 1 index
        }
        array[innerIdx + 1] = current;
    }

    long endTime = System.nanoTime() - startTime;
    System.out.println("Insertion Sort runtime (ns) = " + endTime);
    return array;
}

以下是主要方法，其中包含气泡和选择，似乎测量正确（merge 和 quick 是分开的类）：

import java.util.Random;
import java.util.Scanner;

public class Algorithms {

static boolean displayOutput = false;

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner scanner = new Scanner(System.in);
    System.out.println("How long do you want the test array? (give integer)");
    int lengthOfTestArray = scanner.nextInt();
    System.out.println("Generate random values between 1 and... (give integer)");
    int randomCeiling = scanner.nextInt();
    System.out.println("Display sorted arrays onto screen? ('true' or 'false')");
    displayOutput = scanner.nextBoolean();
    System.out.println("-~-~-~(╯ಠ_ರೃ)╯︵ ┻━┻ LET'S DO THIS! \n");
    // END INPUT, user has defined size of array and range for values

    int[] testArray = new int[lengthOfTestArray];
    for (int idx = 0; idx < testArray.length; idx++) {
        // generate an array of random numbers
        Random rand = new Random();
        testArray[idx] = rand.nextInt(randomCeiling) + 1;
    }

    // create copies for each of the sorting algorithms
    int[] bubbleArray = testArray;
    int[] selectionArray = testArray;
    int[] insertionArray = testArray;
    int[] quickArray = testArray;
    int[] mergeArray = testArray;

    bubbleArray = bubbleSort(bubbleArray);
    System.out.println("Bubble Sort:");
    for (int value : bubbleArray) {
        System.out.print(value + " ");
    }

    System.out.println("\n-----------------");

    selectionArray = selectionSort(selectionArray);
    System.out.println("Selection Sort Output:");
    if (displayOutput) {
        for (int value : selectionArray) {
            System.out.print(value + " ");
        }
    }

    System.out.println("\n-----------------");

    insertionArray = insertionSort(insertionArray);
    System.out.println("Insertion Sort Output");
    if (displayOutput) {
        for (int value : insertionArray) {
            System.out.print(value + " ");
        }
    }

    System.out.println("\n-----------------");

    Quicksort.run(quickArray);
    System.out.println("Quick Sort Output");
    if (displayOutput) {
        for (int value : quickArray) {
            System.out.print(value + " ");
        }
    }

    System.out.println("\n-----------------");

    Mergesort.run(quickArray);
    System.out.println("Merge Sort Output");
    if (displayOutput) {
        for (int value : mergeArray) {
            System.out.print(value + " ");
        }
    }

}

public static int[] bubbleSort(int[] array) {
    // bubble sort iterates through array, rearranging 2 at a time
    // currently makes it ASCENDING
    long startTime = System.nanoTime();

    int trailingNum = 0;
    int arrayLength = array.length;
    boolean flag = true;

    while (flag) {
        flag = false;
        for (int idx = arrayLength - 1; idx > 0; idx--) {
            if (array[idx] < array[idx - 1]) {
                trailingNum = array[idx];
                array[idx] = array[idx - 1];
                array[idx - 1] = trailingNum;
                flag = true;
            }
        }
    }

    long endTime = System.nanoTime() - startTime;
    System.out.println("Bubble Sort runtime (ns) = " + endTime);
    return array;
}

public static int[] selectionSort(int[] array) {
    // finds next element out of order, swaps with correct position
    // currently ASCENDING
    long startTime = System.nanoTime();

    int arrayLength = array.length;

    for (int idx = 0; idx < array.length; idx++) {
        int lastMinimum = 0;
        int lastMinimumIndex = 0;

        for (int innerIdx = idx; innerIdx < array.length; innerIdx++) {
            if (innerIdx == idx) {
                // if first iteration, set the minimum as first value
                lastMinimumIndex = innerIdx;
            }
            if (array[innerIdx] < array[lastMinimumIndex]) {
                // if value at position smaller than min index, replace
                lastMinimumIndex = innerIdx;
            }
            // loop exit with best min index starting from index of outer
        }

        if (idx != lastMinimumIndex) {
            // if minimum value is not at the current index
            int tempMin = array[lastMinimumIndex];
            array[lastMinimumIndex] = array[idx];
            array[idx] = tempMin;
        }
    }

    long endTime = System.nanoTime() - startTime;
    System.out.println("Selection Sort runtime (ns) = " + endTime);
    return array;
}

public static int[] insertionSort(int[] array) {
    long startTime = System.nanoTime();

    int current;
    int innerIdx;

    int arrayLength = array.length;
    for (int idx = 1; idx < arrayLength; idx++) {
        // iterate through the array, happens just once
        current = array[idx];
        for (innerIdx = idx - 1; current < array[innerIdx] && innerIdx >= 0; innerIdx--) {
            // while current is "traveling" over larger values in array
            array[innerIdx + 1] = array[innerIdx];
            // shift the array elements over by 1 index
        }
        array[innerIdx + 1] = current;
    }

    long endTime = System.nanoTime() - startTime;
    System.out.println("Insertion Sort runtime (ns) = " + endTime);
    return array;
}

}

Answer 1

// create copies for each of the sorting algorithms
int[] bubbleArray = testArray;
int[] selectionArray = testArray;
int[] insertionArray = testArray;
int[] quickArray = testArray;
int[] mergeArray = testArray;

这没有创建副本，所有 int[] 变量都指向同一个数组。在你对它进行排序后，一旦其他算法收到一个已经排序的数组。

要创建副本，请使用 java.util.Arrays.copyOf(...) 或 java.lang.System.arrayCopy(...)

Answer 2

无论您是否正确计时，您的程序都会无意中将插入排序设置为获胜者。您没有创建 testArray 的副本，而是创建了对单个数组的多个引用。 Insertion sort is Θ(n) for already sorted data，因此通过首先使用另一种算法对共享数组进行排序，您创建了一个插入排序优于其他算法的场景。

实测插入排序速度太快

Measured insertion sort speed is too fast

java

algorithm

sorting

insertion-sort