如何计算冒泡排序最坏情况下的比较次数？求解计算矛盾与疑问

为什么你的手动计算和公式结果不一样？ #

你算出6次比较，肯定是用了未优化的冒泡排序实现，而公式n*(n-1)/2对应的是标准优化版的最坏情况比较次数，两者的逻辑差异导致了结果不同。

1. 标准优化版冒泡排序（以n=3，数组[3,2,1]为例） #

标准冒泡排序每一轮会把当前最大的元素“沉”到数组末尾，所以每一轮的比较范围会缩小1：

• 第1轮：比较3和2（交换）、3和1（交换）→ 2次比较，数组变成[2,1,3]
• 第2轮：只需要比较前两个元素，2和1（交换）→1次比较，数组变成[1,2,3]
• 第3轮：数组已经有序，直接终止（如果加了提前结束的标志位）
  总比较次数是2+1=3次，刚好匹配3*2/2=3的结果。

2. 未优化版冒泡排序（同样n=3，数组[3,2,1]） #

如果你的代码是每一轮都从头比到尾，不缩小比较范围也不提前终止，比如：

def my_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

那每一轮都会做n-1次比较：

• 第1轮：2次比较，数组变[2,1,3]
• 第2轮：还是2次比较（比2和1、1和3），数组变[1,2,3]
• 第3轮：依旧2次比较（比1和2、2和3）
  总次数就是2+2+2=6次，这就是你手动算的结果。但这种实现效率很低，不是冒泡排序的最优写法。

关于几种说法的澄清 #

• n*(n-1)/2：这是标准优化版冒泡排序最坏情况（数组完全逆序）的比较次数，是正确的。
• n*(n+1)/2：这个说法是错的，大概率是混淆了其他排序算法，或者把比较、交换次数乱加了，冒泡排序不存在这个计算逻辑。
• O(n²)：这是时间复杂度的渐近表示，用来描述数据量很大时算法的时间增长趋势。n*(n-1)/2的最高次项是n²，所以归为O(n²)，和具体的常数项无关。

最坏情况下比较次数等于交换次数吗？ #

分情况：

• 对于标准优化版冒泡排序，最坏情况（数组完全逆序）下，每一次比较都会触发交换（前一个元素必然比后一个大），所以比较次数等于交换次数。比如n=3时，3次比较对应3次交换。
• 对于未优化版冒泡排序，即使是最坏情况，后面的轮次会出现“无效比较”（数组已经有序但仍继续比较），这些比较不会触发交换，所以比较次数会大于交换次数。比如n=3时，6次比较但只有3次交换。

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