为何我实现的「快速冒泡排序」反而比普通冒泡排序更慢？

哈哈，这个结果确实有点反直觉对吧？我仔细看了你的代码和测试用例，发现问题出在测试场景的特殊性和两个实现的实际开销差异上：

1. 你以为的O(n)检查，实际是O(1)开销 #

先看你的check_sorted函数：它并不是每次都要遍历整个数组，而是遇到第一个逆序对就立刻返回False。你的测试用例是list(reversed(range(5000)))——完全逆序的数组，所以check_sorted只需要比较A[1]和A[0]这一对，就会直接返回False。也就是说，这个检查的实际开销几乎可以忽略不计，根本不是你担心的O(n)。

2. 「快速版」多了大量额外的赋值操作 #

在完全逆序的场景下，两个版本每一轮都要做满n-1次交换，但bubble_sort_fast每次交换后都要多执行一次swap = True的赋值。单次赋值虽然快架不住次数多：5000个元素的逆序数组，要进行近5000轮排序，每轮又有几千次赋值，这些累积起来的开销就超过了原始版本那点微不足道的检查开销。

3. 换个测试用例，「快速版」的优势就出来了 #

如果你的测试用例是接近有序的数组（比如A = list(range(5000)) + [4999]），bubble_sort_fast就会比原始版本快很多：它会在数组变有序的那一轮结束后立刻停止循环，而原始版本还要多跑一次check_sorted（虽然这次会遍历整个数组，但之后就停了）。

给你个更高效的冒泡排序优化方案 #

其实标准的冒泡排序优化除了swap标记，还可以记录最后一次交换的位置——因为最后一次交换位置之后的元素已经是有序的了，下一轮根本不用再碰它们。试试这个版本：

def bubble_sort_optimized(A):
    last_swap_pos = len(A) - 1
    while last_swap_pos > 0:
        current_swap = 0
        for i in range(1, last_swap_pos + 1):
            if A[i] < A[i-1]:
                A[i], A[i-1] = A[i-1], A[i]
                current_swap = i
        last_swap_pos = current_swap - 1
    return A

不管是完全逆序还是接近有序的场景，这个版本都会比你的两个实现快不少~

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