什么是insort？

Python的bisect.insort()函数用于将元素插入到已排序的列表中，同时保持列表的排序状态。它使用高效的二分查找算法确定插入位置，时间复杂度为O(log n)，比每次插入后重新排序(O(n log n))高效得多。

基本使用方法

1. 导入模块

import bisect

2. 准备已排序列表

sorted_list = [1, 3, 4, 7, 10]

3. 插入新元素

# 插入元素5
bisect.insort(sorted_list, 5)
print(sorted_list)  # 输出: [1, 3, 4, 5, 7, 10]

# 插入元素2
bisect.insort(sorted_list, 2)
print(sorted_list)  # 输出: [1, 2, 3, 4, 5, 7, 10]

lst = [1, 2, 2, 3]
bisect.insort_left(lst, 2)  # 插入在第一个2的位置
print(lst)  # [1, 2, 2, 2, 3]

bisect.insort(sorted_list, 0)   # 插入开头 → [0, 1, 2, 3, 4, 5, 7, 10]
bisect.insort(sorted_list, 15)  # 插入末尾 → [0, 1, 2, 3, 4, 5, 7, 10, 15]

处理自定义对象

当处理自定义对象时，可以通过以下两种方法使用insort：

方法1：实现__lt__方法

class Product:
    def __init__(self, name, price):
        self.name = name
        self.price = price
        
    def __lt__(self, other):
        return self.price < other.price  # 按价格排序
    
    def __repr__(self):
        return f"{self.name}(${self.price})"

# 创建产品列表
products = [
    Product("Keyboard", 50),
    Product("Monitor", 200),
    Product("Mouse", 25)
]
products.sort()  # 按价格排序

# 插入新产品
new_product = Product("Headphones", 80)
bisect.insort(products, new_product)

# 输出: [Mouse($25), Keyboard($50), Headphones($80), Monitor($200)]
print(products)

方法2：使用key函数

# 当无法修改类时，可以使用key参数
students = [
    {"name": "Alice", "grade": 85},
    {"name": "Bob", "grade": 92},
    {"name": "Charlie", "grade": 78}
]
students.sort(key=lambda s: s["grade"])

# 插入新学生
new_student = {"name": "Diana", "grade": 88}

# 使用bisect.insort和key参数
bisect.insort(students, new_student, key=lambda s: s["grade"])

# 输出按成绩排序的学生
# [{'name': 'Charlie', 'grade': 78}, 
#  {'name': 'Alice', 'grade': 85}, 
#  {'name': 'Diana', 'grade': 88}, 
#  {'name': 'Bob', 'grade': 92}]
print(students)

性能对比

下面展示insort与普通插入后排序的性能差异：

import bisect
import time

sorted_list = []
for i in range(10000):
    # 生成随机数
    num = random.randint(0, 100000)
    # 使用insort插入
    bisect.insort(sorted_list, num)

import time

sorted_list = []
for i in range(10000):
    # 生成随机数
    num = random.randint(0, 100000)
    # 普通插入后排序
    sorted_list.append(num)
    sorted_list.sort()

实际应用场景

temperature_readings = []

def add_reading(temp):
    bisect.insort(temperature_readings, temp)
    # 实时计算中位数
    n = len(temperature_readings)
    median = (temperature_readings[n//2] + temperature_readings[-(n//2+1)])/2

high_scores = [('Alice', 1200), ('Bob', 950), ('Charlie', 800)]

def add_score(name, score):
    # 按分数排序（降序）
    bisect.insort(high_scores, (name, score), 
                  key=lambda x: -x[1])
    # 只保留前10名
    if len(high_scores) > 10:
        high_scores.pop()

from datetime import datetime

schedule = [
    (datetime(2023, 10, 15, 9, 0), '会议'),
    (datetime(2023, 10, 15, 14, 0), '电话')
]

new_event = (datetime(2023, 10, 15, 11, 30), '午餐')
bisect.insort(schedule, new_event, key=lambda x: x[0])

总结

Python的bisect.insort()是维护有序列表的强大工具：

• 使用二分查找确定插入位置，高效可靠
• 保持列表始终有序，无需手动排序
• 支持基本类型和自定义对象（通过__lt__或key参数）
• 比append+sort方法性能更好
• 适用于实时数据流、排行榜、调度系统等场景

合理使用insort可以显著提高涉及有序列表操作的代码效率！