Python：插入新元素到排序的字典列表中

Question

我有一个已经按键id排序的字典列表。

y = [{'id': 0, 'name': 'Frank'}, 
    {'id': 5, 'name': 'Hank'}, 
    {'id': 8, 'name': 'Fred'}, 
    {'id': 30, 'name': 'Jill'}] 

我想插入一个新元素到列表中。

y.append({'id': 6, 'name': 'Jenkins'}) 

如何避免在添加新元素后按如下方式重新排序列表？

y = sorted(y, key=lambda x: x['id']) 

理想的结果是：

y = [{'id': 0, 'name': 'Frank'}, 
    {'id': 5, 'name': 'Hank'}, 
    {'id': 6, 'name': 'Jenkins'}, 
    {'id': 8, 'name': 'Fred'}, 
    {'id': 30, 'name': 'Jill'}] 

编辑：

使用bisect.insort(y, {'id': 6, 'name': 'Jenkins'})将工作只为第一项中，如果字典是按名称排序，它将会失败。

Answer 1

既然a insertion in a list is in O(n)无论如何，任何聪明的二分法算法都没有那么有用，所以你可以简单地循环列表来找到它应该插入的位置，然后插入它。类似于：

new_value = {'id': 6, 'name': 'Jenkins'} 

for index, value in enumerate(y): 
    # Assuming y is in increasing order. 
    if value['id'] > new_value['id']: 
     y.insert(index, new_value) 
     break