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

Question

我正在使用Java进行基准标记排序算法。当我比较平均情况下的冒泡排序和使用范围为0到99的随机数组的选择排序时，冒泡排序的性能明显更好。我已阅读的大多数性能参考都指出，Section排序是两者中较好的一种。

此我的选择实现：

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

我对Bubble排序的实现未优化，如果列表已排序，则退出：

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上，您可以看到如果数组已经或几乎已排序，则实际发生的情况。