如何将tuple基于第三个元素插入已排序tuple列表并保持有序，无需整体重排

需求：现有已按照每个tuple的第3个数值排序的列表A，向其中插入tuple B得到列表C，插入后仍需保持按照tuple第3个值排序的顺序，不可使用全列表重排的低效率方案。

核心思路 #

使用Python标准库内置的bisect模块，通过二分查找快速定位插入位置，无需对全列表重新排序，性能满足大数据量场景要求。

实现代码 #

Python 3.10+ 版本（支持key参数直接比较） #

import bisect

A = [(1, 2, 1), (1, 2, 2), (1, 2, 3), (1, 2, 5)]
B = (1, 2, 4)

# 按tuple第三个值定位插入位置
insert_pos = bisect.bisect_left(A, B, key=lambda x: x[2])
# 生成新列表，如需保留原列表A可使用该方式
C = A.copy()
C.insert(insert_pos, B)

# 输出结果符合预期：[(1, 2, 1), (1, 2, 2), (1, 2, 3), (1, 2, 4), (1, 2, 5)]
print(C)

Python 3.10 以下兼容版本 #

低版本Python的bisect模块不支持key参数，可提前提取所有元素的排序键后再查找位置：

import bisect

A = [(1, 2, 1), (1, 2, 2), (1, 2, 3), (1, 2, 5)]
B = (1, 2, 4)

# 提取所有tuple的第三个值作为键列表
sort_keys = [item[2] for item in A]
insert_pos = bisect.bisect_left(sort_keys, B[2])

# 如需直接修改原列表A，可直接执行 A.insert(insert_pos, B)
C = A.copy()
C.insert(insert_pos, B)

注意事项 #

• 效率对比：二分查找定位位置的时间复杂度为O(log n)，列表插入操作复杂度为O(n)，整体性能远高于全列表排序的O(n log n)，数据量越大优势越明显
• 重复值处理：bisect_left会将新元素插入到所有相同值元素的左侧，bisect_right则会插入到右侧，可根据实际业务对相同值的排序要求选择对应方法
• 内存优化：如果不需要保留原始列表A，可直接在原列表上执行插入操作，无需拷贝生成新列表，节省内存开销

内容的提问来源于stack exchange，提问作者Greg W.F.R