java - 为什么选择排序比冒泡排序更快？

Question

这个问题已经有答案了:

How do I write a correct micro-benchmark in Java? (11 个回答)

已关闭 4 年前。

我使用 Java 进行了一项实验，以确定哪种排序方法(冒泡或选择)的运行时间更快。程序提示用户输入数字 n这是数组中要排序的项目数。然后，它创建并排序 500 个相同大小的不同数组，并对运行进行计时，以获得使用两种排序方法进行排序的平均时间。我使用 500、1000 和 2500 作为 n 的测试输入。我下面的结果表明选择排序比冒泡排序运行得更快，但这两种算法的时间复杂度都是 O(n^2)，那么为什么选择排序运行得这么快呢？

TimeBubbleSort 类

public class TimeBubbleSort {
    public static void main(String[] args) {

        System.out.print("Enter a number of items in array: ");
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();

        long start_time = 0;
        long end_time = 0;
        long running_time = 0;
        long final_time = 0;
        BubbleSort bubbleSort = new BubbleSort();

        for(int i = 0; i < 500; i++) {
            int[] array = new int[n];
            for(int j = 0; j < array.length; j++) {
                array[j] = (int)(Math.random() * n) + 1;
            }
            start_time = System.nanoTime();
            bubbleSort.bubbleSort(array);
            end_time = System.nanoTime();
            running_time = end_time - start_time;
            final_time = final_time + running_time;
        }
        System.out.println("The average time of each array took " + 
(final_time / 500) + " nanoseconds");
    }
}

冒泡排序类

public class BubbleSort {

    void bubbleSort(int[] arr) {
        int n = arr.length;
        int temp = 0;
        for (int i = 0; i < n; i++)
            for (int j = 1; j < (n - i); j++)
                if (arr[j - 1] > arr[j]) {
                    temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                }
    }

    void printArray(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}

TimeSelectionSort 类

public class TimeBubbleSort {
    public static void main(String[] args) {

        System.out.print("Enter a number of items in array: ");
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();

        long start_time = 0;
        long end_time = 0;
        long running_time = 0;
        long final_time = 0;
        SelectionSort selectionSort = new SelectionSort();

        for(int i = 0; i < 500; i++) {
            int[] array = new int[n];
            for(int j = 0; j < array.length; j++) {
                array[j] = (int)(Math.random() * n) + 1;
            }
            start_time = System.nanoTime();
            selectionSort.selectionSort(array);
            end_time = System.nanoTime();
            running_time = end_time - start_time;
            final_time = final_time + running_time;
        }
        System.out.println("The average time of each array took " + 
(final_time / 500) + " nanoseconds");
    }
}

SelectionSort 类

public class SelectionSort {
    void sort(int arr[]) {
        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {
            int min_idx = i;
            for (int j = i + 1; j < n; j++)
                if (arr[j] < arr[min_idx])
                    min_idx = j;

            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }

    void printArray(int arr[]) {
        int n = arr.length;
        for (int i=0; i<n; ++i)
            System.out.print(arr[i]+" ");
        System.out.println();
    }
}

使用冒泡排序的结果

数组大小为 500:花费了 284,979 纳秒

数组大小为 1000:花费了 960,067 纳秒

数组大小为 2500:花费了 7,448,865 纳秒

使用选择排序的结果

数组大小为 500:花费了 107,035 纳秒

数组大小为 100:花费了 342,464 纳秒

数组大小为 2500:花费了 1,880,215 纳秒

Answer 1

首先，与系统时间进行比较并不是分析两种算法时间复杂度的正确方法，因为请记住 - 您的程序并不是系统上运行的唯一程序。因此，即使算法和输入相同，两个运行时间也可能完全不同。

现在回答你的问题了，与我们在每次迭代中仅在最后一步交换的选择排序相比，冒泡排序具有更多的交换次数。所以可能是这个原因。

两种算法具有相同的时间复杂度并不意味着它们的运行时间会相同。首先，近似地取它们的时间复杂度，这是贡献最大的最大因素。在上述两种情况下，最大的因子是 n^2，但还有其他更小的 n 次幂和常数会产生差异。