冒泡排序的最佳情况是 O(n) 而不是 O(n^2) 的解释？

Question

给定一个冒泡排序算法

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

如果给定的数组已经排序，则内部循环中的 if 语句将始终为 false，从而破坏内部 for 循环并递增j直到A.length-i-1到达。当A.length-i-1达到时，i增加。这个过程循环进行，直到i达到A.length-1。

我的困惑：

如果两个嵌套循环都迭代到各自的上限，尽管没有进行交换，但最佳情况下时间复杂度不是仍然是O(n^2)吗？谁能简单地向我解释一下为什么它会是O(n)

Answer 1

如果程序原样，是的，在最好的情况下它仍然需要 O(n^2) 。但你可以增强这个程序。

在第一次通过时，您将看到没有发生任何交换。您可以保留一个标志来检查如果在一次传递期间没有发生交换，则您不需要进一步传递。

在这种情况下，您只需执行一次，时间复杂度将为 O(n)

示例程序（结构可以更好）：

        boolean previousIterationSwap = false;
        final int[] A = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        for (int i = 0; i < A.length - 1; i++) {
            // After the first iteration check if previous iteration had any
            // swap
            if (i > 0 && !previousIterationSwap) {
                break;
            }
            for (int j = 0; j < A.length - i - 1; j++) {
                if (A[j] > A[j + 1]) {
                    previousIterationSwap = true;
                    final int temp = A[j];
                    A[j] = A[j + 1];
                    A[j + 1] = temp;
                } else {
                    previousIterationSwap = false;
                }
            }
        }