如何高效统计冒泡排序外循环的迭代次数？

嘿，这个问题戳中了冒泡排序的经典痛点——常规统计外循环次数的方法完全跟着冒泡排序的O(N²)流程走，效率太低。其实咱们可以跳出“模拟冒泡过程”的思维，从冒泡排序的本质出发找答案。

先搞懂：冒泡排序的外循环次数到底由什么决定？ #

冒泡排序的核心是大元素向右“冒泡”，小元素向左逐步移动。这里的关键是：小元素每次外循环最多只能向左移动1位，而大元素可以在一次外循环中连续向右跳多步。因此，外循环的总次数，完全由数组中需要向左移动步数最多的那个元素的移动步数 + 1决定（加1是因为最后还要跑一次确认无交换的循环）。

举个例子：数组[3,2,1]里，元素1需要从位置2移动到0，共2步。所以外循环要跑2次让它到位，再跑1次确认有序，总次数是3——和实际模拟的结果一致。

那问题就转化为：如何在O(N log N)的时间内，计算每个元素的最终排序位置，然后找到最大的「初始位置 - 最终位置」（也就是向左移动的步数），最后加1就是外循环次数。

具体实现思路（O(N log N)复杂度） #

我们可以用**离散化+树状数组（Fenwick Tree）**来高效计算每个元素的最终位置，步骤如下：

• 离散化处理：如果数组元素很大（比如包含1e9级别的数），直接用树状数组会浪费空间，所以先把元素映射到1~N的连续整数范围。比如数组[2,3,1,5,4]，离散化后对应[2,3,1,5,4]（因为元素排序后是1,2,3,4,5，直接映射即可）。
• 用树状数组统计最终位置：从右往左遍历原数组，对于每个元素A[i]，查询树状数组中已插入的元素里比A[i]小的数量，这个数量就是A[i]在排序后的最终位置；之后把A[i]插入树状数组。
• 计算最大左移步数：对每个元素计算diff[i] = i - pos[i]（i是初始位置，从0开始），找到最大的diff[i]。
• 得到外循环次数：如果数组已有序（max_diff <= 0），外循环次数是1；否则就是max_diff + 1。

伪代码实现 #

procedure getBubbleSortIterationCount(A : list of sortable items):
    n = length(A)
    if n <= 1:
        return 1
    
    // 步骤1：离散化处理
    sorted_A = sorted(A)
    // 给每个元素分配离散化后的索引（从1开始，适配树状数组）
    rank = {val: idx+1 for idx, val in enumerate(sorted_A)}
    discretized_A = [rank[val] for val in A]
    
    // 步骤2：实现树状数组
    class FenwickTree:
        def __init__(self, size):
            self.size = size
            self.tree = [0]*(size+1)
        
        def update(self, idx, delta=1):
            while idx <= self.size:
                self.tree[idx] += delta
                idx += idx & -idx
        
        def query(self, idx):
            res = 0
            while idx > 0:
                res += self.tree[idx]
                idx -= idx & -idx
            return res
    
    ft = FenwickTree(n)
    pos = [0]*n
    
    // 从右往左遍历，计算每个元素的最终位置
    for i from n-1 downto 0:
        // 查询比当前元素小的元素数量，即为最终位置（从0开始）
        pos[i] = ft.query(discretized_A[i] - 1)
        ft.update(discretized_A[i])
    
    // 步骤3：计算最大左移步数
    max_diff = max(i - pos[i] for i in range(n))
    
    // 步骤4：返回外循环次数
    if max_diff <= 0:
        return 1
    else:
        return max_diff + 1

为什么这个方法是O(N log N)？ #

• 离散化的排序步骤是O(N log N)。
• 树状数组的每个update和query操作都是O(log N)，一共执行N次，这部分是O(N log N)。
• 整体复杂度远低于O(N²)，适合处理大规模数组。

验证例子 #

比如数组[2,3,1,5,4]：

• 离散化后是[2,3,1,5,4]
• 从右往左遍历计算pos数组：[1,2,0,4,3]
• diff数组是[-1,-1,2,-1,1]，max_diff=2
• 外循环次数是2+1=3，和实际模拟的结果一致。

内容的提问来源于stack exchange，提问作者Victor Yin