冒泡排序的稳定性藏在一个大于号里：再算清 key 的调用成本

摘要：相邻比较写成大于还是大于等于，会改变同分记录的顺序；把取键放进内层循环，又会让同一条记录被反复计算。本文从一次 Python 排序练习出发，用独立本地实验说明稳定性、提前结束和键缓存各自解决什么问题。

按分数排序时，分数正确并不等于记录顺序符合要求。假设输入依次为 A（90）、B（80）、C（90）、D（90），升序结果应为 B、A、C、D；其中同为90分的 A、C、D 保持输入时的先后，这才叫稳定。

10月31日的本地冒泡排序练习采用 key(left) > key(right) 时交换。我据此另建演示，给取键函数增加计数，并构造一个把条件改为 >= 的反例，没有修改原练习。

为什么相等时不能交换

在整数键的相邻交换排序中，两个同分记录若要颠倒顺序，必须跨过彼此。只交换严格逆序对，就不会发生这一步。因此，稳定性来自交换条件和相邻交换方式共同形成的约束。

实际演示中，严格比较得到 B、A、C、D；改为大于等于后得到 B、D、C、A。两者分数都是80、90、90、90，但后者改变了同分顺序。只断言分数升序，发现不了这个问题；还应检查相同键对应的记录标识。

每轮没有交换即可结束，也有明确理由：整数键的所有相邻对都已满足升序，整段便有序。已有序的16个数只比较15次。这个优化减少比较轮数，却没有保证取键只执行一次。

比较一次，可能取键两次

直接在条件中调用左右两次 key，一共比较多少次，就会产生两倍的取键调用。下面是本次实际计数；两种冒泡实现都保留无交换时提前结束。

对于降序的16个互异整数，比较次数是15加14一直加到1，共120次。缓存把取键次数降到16，但比较仍是120次。若取键涉及日期解析或较长文本转换，这个区别值得关注；本次只测调用次数，没有测耗时，不能写成“快了15倍”。

把键和记录一起移动

一种完整的教学实现如下。这里只比较缓存键，不比较整个二元组，避免同键时继续尝试比较原记录。

def bubble_cached(items, key):
    pairs = [(key(item), item) for item in items]
    for end in range(len(pairs) - 1, 0, -1):
        swapped = False
        for i in range(end):
            if pairs[i][0] > pairs[i + 1][0]:
                pairs[i], pairs[i + 1] = pairs[i + 1], pairs[i]
                swapped = True
        if not swapped:
            break
    return [item for _, item in pairs]

交换的是整对数据，缓存键始终跟着对应记录移动。返回值是新列表；其中的记录仍是原对象，并没有深拷贝。缓存需要额外保存每个元素的键，也没有改变冒泡排序最坏情况下的二次方比较规模。实际业务可优先使用 sorted(items, key=...)，本次也用它核对结果与取键次数。

缓存还改变了调用时机：单元素输入时，直接比较版不取键，缓存版与本次运行的 sorted 都取键一次。因此，两版不能对任意副作用函数宣称行为完全等价。应让键在排序期间保持确定，不修改记录，也不依赖变化的外部状态。

本次于2026年11月1日在 Windows、Python 3.12.14下运行独立标准库演示。五组正常输入与一个不稳定反例均符合预期，退出码0，stderr为空；正常输入还核对了三种结果一致及输入内容未变。实验不涉及云环境，也不证明其他键类型、异常路径或大数据性能。练习中一个大于号和一处缓存，分别对应顺序承诺与计算成本，值得分开验证。