为什么冒泡排序在一般情况下比选择排序表现更好

Question

我正在使用 java 对排序算法进行基准测试。当我使用范围为 0 到 99 的随机数组比较平均情况下的冒泡排序和选择排序时，冒泡排序的性能明显更好。我读过的大多数关于性能的参考资料都指出，部分排序是两者中较好的。

这是我的选择实现：

public static void selectionSort(int[] arr) {
        /*
         * Selection sort sorting algorithm. Cycle: The minimum element form the
         * unsorted sub-array on he right is picked and moved to the sorted sub-array on
         * the left.
         * 
         * The outer loop runs n-1 times. Inner loop n/2 on average. this results in
         * (−1)×2≈2 best, worst and average cases.
         * 
         */

        // Count outer
        for (int i = 0; i < arr.length; i++) {
            // Assign the default min index
            int min = i;
            // Find the index with smallest value
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            // Swap index arr[min] with a[i]
            int temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }

我的冒泡排序：

public static void optimalBubbleSort(int[] arr) {
          /**
           * The optimized version will check whether the list
           * is sorted at each iteration. If the list is sorted the 
           * program will exist.
           * Thus the best case for the optimized bubble sort 
           * is O{n). Conversely the above algorithm
           * the best case will always be the same as the average case.
           * 
           */
        boolean sorted = false;
        int n = arr.length;
        while (!sorted) {
          sorted = true;
          for (int i = 0; i < n - 1; i++) {
            if (arr[i] > arr[i + 1]) {
              int temp = arr[i + 1];
              arr[i + 1] = arr[i];
              arr[i] = temp;
              sorted = false;
            }
          }
          n--;
        }
      }

我的冒泡排序实现没有优化以在列表排序后退出：

for (int i = 0; i < arr.length - 1; i++) {
          /*
           * Iteration of the outer loop will ensure
           * that at the end the largest element is in the 
           * (array.lenght-(i+1))th index.
           * Thus the loop invariant is that 

           * In other words, the loop invariant is that
           * the subsection bounded by the indices
           * [arr.length - i, arr.length] is sorted and
           * contains the i biggest elements in array.
           */

          for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
              /*
               * In the case where an inversion exists in 
               * arr[j] > arr[j + 1],
               * arr[j] and arr[j + 1] are
               * thus swapped.
               */
              int temp = arr[j + 1];
              arr[j + 1] = arr[j];
              arr[j] = temp;
            }
          }
        }

这就是我为 inout 生成随机数组的方式：

int[] random = new int[n];
        for (int i = 0; i < n; i++) {
            random[i] = randomInteger.nextInt(100);
        }

关于为什么冒泡排序更快受到赞赏的任何意见。

Answer 1

所以如果我们比较比较的次数，两种算法都会有大约 n*(n+1)/2 的东西（或者只是从 n 到 1 的所有数字的总和），这大约是 n^2 因为你声明。

选择排序确实比冒泡排序有更少的交换，但问题是它会遍历整个数组并排序，即使它已经排序。当数组排序时，冒泡排序实际上会围绕 n 进行比较，这使得它在最佳情况下具有 O(n) 时间复杂度。当数组接近排序时它也会更快，这平均导致冒泡排序比插入排序更快。您可以在 this site

上找到每个案例的大 O

在 this site 上，您可以看到如果数组已经排序或接近排序，实际会发生什么。

Answer 2

如您所见，冒泡排序和 select 离子排序的主要区别在于，当数组（几乎）排序。在你的例子中，当你 select 你的随机数在 0 和 100 之间时，如果选择的数组长度 n 远小于 100，则（几乎）排序样本的概率将增加。从这个意义上说，你可以发现冒泡排序的平均复杂度优于select离子排序。

所以大家要注意，这个比较依赖于n，如果增加n的值，随着数组排序的概率下降，你会发现这两条曲线更近。

Answer 3

如果我是对的，您正在对 [0, 99] 范围内的值和长度最大为 100000 的数组进行排序。这意味着每个值平均最多可以重复 1000 次。

IMO 你你可以丢弃你所有的结果 as 你正在测试非常特殊的情况，其中大量的键是相等的并且算法可能具有非标准行为。它们的性能将对通常不重要的实现细节更加敏感。经典的排序算法不是为这种极端情况设计的。

我想补充一点，在大数据集上比较慢速排序和快速排序没有多大意义（快速排序的曲线非常紧凑，您无法比较它们中的任何一个。）

为什么冒泡排序在一般情况下比选择排序表现更好

Why is Bubble sort performing better than Selection sort in average case

java

algorithm

sorting

bubble-sort

selection-sort