时间戳

首页 > 解决方案 > 冒泡排序的最佳情况是 O(n) 而不是 O(n^2) 的解释？

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

问题描述

给定一个冒泡排序算法

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 语句将始终为假，打破内部 for 循环并递增j直到A.length-i-1到达。A.length-i-1达到时，递增i。这个过程循环直到i到达A.length-1。

我的困惑：

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

标签： javatimetime-complexity

解决方案

如果程序按原样，是的，最好的情况仍然需要 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;
                }
            }
        }

推荐阅读