Python bisect.insort 怎么用 key 参数维护对象排序

如果列表里放的不是数字，而是带有 name、score 等字段的对象，仍然可以用 bisect.insort() 保持排序。关键写法是把排序字段交给 key：key 负责从对象中提取比较值，插入动作仍然把完整对象放回列表。这个参数从 Python 3.10 开始提供。

官方文档：https://docs.python.org/3/library/bisect.html

维护对象有序列表时，使用 insort(records, item, key=lambda x: x["score"]) 即可。不要把 key(item) 的结果当成要插入的元素；它只用于找到位置，真正插入的还是 item。

先做一个小型排行榜

我在处理一组小规模排行榜时遇到过这个场景：新记录不断到来，列表已经按分数升序排列，希望每次只找到合适位置，而不是插入后再完整调用一次 sort()。列表元素是字典，排序依据是 score，展示内容还要保留玩家名和来源。

这里故意选择升序，便于直接观察插入点；如果业务展示需要高分在前，可以把分数转换成负数，或者维护降序所需的独立键。本文只讨论 key 如何参与查找和插入，不把它扩展成完整排行榜系统。

from bisect import insort

# 列表里的元素保留完整对象，score 只是排序依据。
records = [
    {"name": "小林", "score": 72},
    {"name": "阿青", "score": 86},
    {"name": "木子", "score": 95},
]

# key 提取比较字段；insort 会把新对象放进正确位置。
key_by_score = lambda item: item["score"]
new_record = {"name": "安然", "score": 88}
insort(records, new_record, key=key_by_score)

# 结果仍是完整对象列表，分数保持升序。
print([(item["name"], item["score"]) for item in records])

[('小林', 72), ('阿青', 86), ('安然', 88), ('木子', 95)]

这段代码的重点不是省掉了一次排序，而是把“对象内容”和“比较字段”分开了。后续要增加 source、created_at 等字段时，仍然可以沿用同一个列表结构。

key 参数到底参与了哪一步

insort() 可以理解为两个连续动作：先用二分查找定位插入点，再调用列表的 insert() 把元素放进去。key 只作用于查找阶段：函数用它比较已有元素和待插入对象的排序键；确定位置后，插入的是原来的完整对象。

因此，下面两种列表的设计目的不同：

• records 保存完整对象，适合直接展示、更新和读取其他字段。
• keys 只保存已经计算好的分数，适合排序键计算昂贵、且需要高频查找的场景。

常见误解是把 key 写成“把对象转换成另一个对象再插入”。实际上，key 是比较函数式的提取器，不会改变列表元素的类型，也不会替换传入的 new_record。

重复分数该用 insort 还是 insort_left

insort() 等价于向右侧寻找插入边界：如果列表中已经有相同的排序键，新对象会放在这些对象之后。若需要放在相同键的最前面，可以使用 insort_left()。

from bisect import insort, insort_left

# 两个列表都按 score 升序；复制对象避免两个实验互相影响。
base = [
    {"name": "甲", "score": 80},
    {"name": "乙", "score": 90},
    {"name": "丙", "score": 90},
]
key_by_score = lambda item: item["score"]

# insort 把相同 score 的新对象放到已有 90 分记录之后。
right_list = base.copy()
insort(right_list, {"name": "新", "score": 90}, key=key_by_score)

# insort_left 把相同 score 的新对象放到已有 90 分记录之前。
left_list = base.copy()
insort_left(left_list, {"name": "新", "score": 90}, key=key_by_score)

# 只打印顺序，便于观察重复键的边界选择。
print([item["name"] for item in right_list])
print([item["name"] for item in left_list])

['甲', '乙', '丙', '新']
['甲', '新', '乙', '丙']

如果记录还需要“先到先得”或“后到先得”的业务规则，应该明确选择边界函数，并在对象中保留一个可解释的次级字段。不要把相同分数的相对顺序交给读者猜测。

把插入逻辑封装成可复用函数

小项目里可以把排序字段提取器和插入入口封装起来，让调用方只传入对象。这样既能集中处理字段缺失，也能避免在多个模块里重复拼接 key 参数。

from bisect import insort

def add_record(records, name, score):
    # 先把外部输入规范成稳定的对象结构。
    if not isinstance(score, int):
        raise TypeError("score 必须是整数")

    item = {"name": name, "score": score}

    # key 只读取排序字段，不会丢掉 name 等对象信息。
    insort(records, item, key=lambda record: record["score"])

records = []
add_record(records, "小林", 72)
add_record(records, "安然", 88)
add_record(records, "阿青", 86)
print(records)

这里的输入检查属于业务层，而不是 bisect 自动提供的能力。若对象缺少 score，key 读取时会抛出异常；如果排序字段是字符串、日期或复合元组，也要保证所有元素之间可以稳定比较。

性能边界：查找快，移动元素仍然要花时间

二分查找本身是 O(log n)，但列表中间插入元素需要移动后面的元素，整体插入成本仍然由 O(n) 主导。官方文档也特别提醒，insort() 的线性插入步骤通常会压过前面的二分查找。

所以这个方案适合数量不大、需要随时保持顺序、读取频率高于插入频率的列表，例如小型榜单、待处理窗口或按时间排列的记录。若每秒有大量中间位置插入，或者列表达到很大规模，就应该重新评估数据结构，而不是只优化 key 函数。

另一个边界是昂贵的键计算。搜索函数不会永久缓存每个元素的 key 结果，循环调用时可能反复计算同一字段。此时可以维护一个并行的预计算键列表，但必须同步更新对象列表和键列表，避免两个序列错位。

一张表记住选择

常见问题

key 参数为什么在旧版本 Python 报错？

key 是 Python 3.10 为 bisect 系列函数增加的参数。旧版本只能先维护比较值列表，或先把对象转换成可直接比较的结构。

能不能用 key=lambda x: -x["score"] 实现高分在前？

可以，但要保证已有列表和新对象始终使用同一个键规则。更容易维护的做法是明确记录“列表按负分升序排列”，并为重复分数写一段测试。

insort 会自动去重吗？

不会。它只负责找到有序插入位置；相同键的对象仍会被插入。去重需要根据业务主键在调用前另行处理。

总结

bisect.insort 的 key 参数适合“对象完整保留、某个字段负责排序”的小型有序列表。记住三点就够了：key 只参与位置查找，插入的是原对象；insort 和 insort_left 的差别在重复键的左右边界；二分查找很快，但列表移动仍然是线性成本。