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

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

如果列表已排序，我的冒泡排序实现未优化退出:

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