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