Python bisect.insort_left 怎样把元素插入有序列表

如果你已经有一个升序列表，只想把新值放进正确位置，bisect.insort_left() 比“追加后再整体排序”更直接：它先找到插入点，再调用列表的插入操作；当列表里已有相等值时，新值会放在它们的最左侧。需要注意的是，二分查找很快并不代表整次插入都是对数复杂度，真正搬移元素仍然可能是线性的。

本文围绕一个具体任务展开：维护一组始终升序的分数或记录，处理重复值和 key，再判断这个方案是否适合当前数据规模。

先用 insort_left 维护普通数值

最小用法是把列表和待插入值传给 insort_left。前提是传入的列表已经有序；它不会替你检查整个列表是否乱序。

from bisect import insort_left

scores = [60, 75, 75, 90]

# 把 75 放入升序列表；相等值会插到已有 75 的左侧
insort_left(scores, 75)

# 结果仍然有序，新的 75 位于原有相等值之前
print(scores)  # [60, 75, 75, 75, 90]

这里无法仅凭打印结果分辨三个 75 的对象身份，但插入点语义是确定的：insort_left 使用的是 bisect_left 的位置，而 insort_right 才会把新值放到相等值的右侧。若相等元素有业务顺序，左右选择就是数据结构的一部分，而不是写法偏好。

记录对象要用 key 表达排序字段

列表元素不一定是数字，也可以是字典、元组或自定义对象。此时用 key 告诉模块“按哪个字段比较”。key 参与寻找位置，但插入列表的仍是原始对象，不会把对象替换成 key 的返回值。

from bisect import insort_left

tasks = [
    {"name": "编译", "priority": 10},
    {"name": "测试", "priority": 30},
]
new_task = {"name": "打包", "priority": 20}

# 只按 priority 找位置，保留完整任务字典
insort_left(tasks, new_task, key=lambda item: item["priority"])

for task in tasks:
    # 读取对象本身，确认插入的不是一个孤立的整数 key
    print(task["name"], task["priority"])

这里要特别留意一个容易误解的边界：搜索时会对待插入对象计算 key，但真正执行列表插入时不会把对象改写成 key。若比较函数很重，重复调用 insort_left 可能反复计算已有元素的 key，可以预先维护 key 列表，或缓存昂贵的计算。

不要把二分查找速度等同于插入速度

insort_left 的定位阶段使用二分查找，查找位置近似为 O(log n)；但 Python 列表在中间插入时，需要把后面的元素向右移动，因此完整插入通常由 O(n) 的搬移成本主导。列表较短、插入不频繁时，这种写法简单而实用；如果数据持续增长且中间插入很多次，就应评估专门的有序容器、数据库索引或批量排序方案。

还要区分“维护有序”与“查找是否存在”。insort_left 只负责找位置并插入，不负责去重。若业务要求唯一值，应先用 bisect_left 找位置，再比较该位置的元素是否相等，确认不存在时才插入。

lo、hi 与并发修改是最后两道边界

lo 和 hi 可以把搜索限制在列表的一个已排序区间内，但区间外的数据不会被重新整理。传入局部范围时，调用方必须自己保证这段范围满足排序前提。

from bisect import insort_left

values = [10, 20, 30, 100, 200]

# 只在前 3 个元素组成的有序区间中寻找位置
insort_left(values, 25, lo=0, hi=3)

# 结果的前缀仍有序；hi 之外的 100、200 不参与比较
print(values)

官方文档还明确提醒，bisect 函数不是线程安全的。多个线程同时修改同一个列表，可能让列表失去有序性；如果列表由并发任务共享，应在外部加锁，或把排序维护放到单线程所有者、队列或数据库中。

速查：什么时候选 insort_left

相关问题

insort_left 和 insort_right 有什么区别？前者把新值放在相等值左侧，后者放在相等值右侧。

列表无序时还能直接调用吗？不建议。函数只在给定范围已排序时有意义，不会先替你排序。

key 返回值会替代原列表元素吗？不会。key 只帮助寻找位置，列表中保存的仍是传入的完整对象。