冒泡排序详解：原理、代码与时间复杂度

通俗地说，思路是什么

比较前两个元素，如果第一个更大就交换。然后比较第二个和第三个，再比较第三个和第四个，依此类推直到列表末尾。这就是一趟。第一趟结束后，最大的元素一定在最后，因为每次比较都把它向右带了一步。

对未排序的部分重复这一趟，每次未排序部分缩短一个元素。如果某一趟没有发生任何交换，说明列表已经有序，可以提前停止。

逐趟演示

将 [5, 1, 4, 2, 8] 按升序排序。竖线之后的元素已在最终位置。

如果没有提前退出，算法还会再跑第四趟；有了提前退出，这里三趟就够了。

Python 实现

def bubble_sort(items):
    """Sort a list in place, ascending. Returns the same list."""
    n = len(items)
    for end in range(n - 1, 0, -1):     # last index of the unsorted part
        swapped = False
        for i in range(end):
            if items[i] > items[i + 1]:  # strict >, keeps equal items in order
                items[i], items[i + 1] = items[i + 1], items[i]
                swapped = True
        if not swapped:                  # no swaps: already sorted
            break
    return items
print(bubble_sort([5, 1, 4, 2, 8]))     # [1, 2, 4, 5, 8]
print(bubble_sort([3, 3, 1]))           # [1, 3, 3]
print(bubble_sort([]))                  # []

内层循环在 end 处停止，因为它之后的元素都已就位。swapped 标志使有序输入下达到 O(n) 的最好情况。

时间与空间复杂度

对于逆序的 10,000 个元素，这将近有 5000 万次比较和交换。交换次数始终等于逆序对的数量，所谓逆序对，就是顺序颠倒的元素对。

冒泡排序与其他排序算法的比较

冒泡排序是稳定的，因为它只交换相邻元素，并且只在严格逆序时才交换，所以相等的元素永远不会越过彼此。插入排序的复杂度和稳定性与它相同，但在实践中写入次数更少、速度更快，因此像 Timsort 这样的混合算法内部用的是插入排序，而不是冒泡排序。

变体与常见错误

• 鸡尾酒排序在交替的趟中先从左到右、再从右到左，能更快地把末尾的小元素（俗称「乌龟」）移到前面。它仍然是 O(n²)。
• 梳排序比较相隔一定间距的元素，并逐步缩小间距，能提早消除大量「乌龟」；间距为 1 时就退化成冒泡排序。
• 奇偶排序先比较所有奇数对，再比较所有偶数对，常用于讲解并行排序。

何时使用冒泡排序

在生产代码中几乎不用。在 Python 中，请调用 sorted(items) 或 items.sort()，它们使用 Timsort，时间 O(n log n)，并且是稳定的。冒泡排序仍然值得了解：它是最容易讲清楚的排序，正确性证明也很好懂，而且是考察循环、交换和复杂度时常见的入门面试题或考试题。

它唯一的实际优势是只需一趟 O(n) 就能检测出列表已有序，但只比较相邻元素的普通循环无需排序也能做到这一点。