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

Question

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

TimeBubbleSort Class

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

冒泡排序Class

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 Class

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

选择排序Class

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 次方和常数会产生差异。

Answer 2

虽然您在这里对系统计时器的使用存在疑问，但您进行了足够多的试验，我认为这不是罪魁祸首。我也很难相信交换消耗了 Brij Raj Kishore 的正确答案所需总时间的近 2/3。

虽然您的循环结构不完全相同，但都运行大约 n^2/2 次，所以应该也没有什么大的区别。

因此，我认为需要进行更多挖掘。我不知道您的系统上有哪些分析器可用，但除非有人在这里发现一些重要的东西，否则这将是我的下一步。查看您的例程实际将时间花在哪里。

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

Why is selection sort faster than bubble sort?

java

arrays

sorting

bubble-sort

selection-sort