如何正确统计Python中冒泡排序的操作次数（时间复杂度）

一、最优场景的问题：代码缺少冒泡排序的提前终止优化 #

你现在的代码是基础版冒泡排序，没有加入“判断列表是否已完全有序”的逻辑。不管输入列表有没有排好序，它都会执行完所有n-1轮外层循环，所以已排序列表的比较次数固定为n(n-1)/2。

标准的优化冒泡排序会在每轮遍历前设置一个交换标志，若某一轮遍历中没有发生任何交换，说明列表已经有序，直接终止循环，这样最优场景下只需要进行n-1次比较（O(n)级别），交换次数为0。优化后的代码示例：

def sort_bubble_optimized(list):
    comp_counter = 0
    swap_counter = 0
    n = len(list)
    for i in range(n-1):
        swapped = False  # 新增交换标志
        for j in range(n-i-1):
            comp_counter += 1
            if list[j] > list[j+1]:
                swap_counter += 1
                list[j], list[j+1] = list[j+1], list[j]
                swapped = True
        if not swapped:  # 本轮无交换，提前终止
            break
    return comp_counter, swap_counter

二、最坏场景的时间复杂度理解：O(n²)是渐近复杂度，忽略系数和低阶项 #

时间复杂度的O(n²)描述的是当n趋近于无穷大时的增长趋势，它会忽略常数系数和低阶项。你得到的比较次数n(n-1)/2 = (n² -n)/2，当n很大时（比如20000），n²项的影响远大于n项，所以这个复杂度仍然属于O(n²)范畴，和你认知的“最坏场景O(n²)”并不矛盾。实际数值接近n²/2是正常的，因为渐近复杂度不关心具体的系数大小。

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