在Python中将元素插入排序列表

Question

我正在创建一个类，其中有一个方法可以把新项目插入到一个已经排好序的列表中。这个新项目会被放在正确的（已经排序好的）位置。不过，我不能使用任何内置的列表函数或方法，除了 []、[:]、+ 和 len 这几个。这让我感到很困惑。

那么，处理这个问题的最佳方法是什么呢？

Answer 1

你应该使用 bisect 模块。而且，在使用 bisect.insort_left 之前，列表需要先排好序。

这两者之间的区别很大。

>>> l = [0, 2, 4, 5, 9]
>>> bisect.insort_left(l,8)
>>> l
[0, 2, 4, 5, 8, 9]

timeit.timeit("l.append(8); l = sorted(l)",setup="l = [4,2,0,9,5]; import bisect; l = sorted(l)",number=10000)
    1.2235019207000732

timeit.timeit("bisect.insort_left(l,8)",setup="l = [4,2,0,9,5]; import bisect; l=sorted(l)",number=10000)
    0.041441917419433594

Answer 2

提示1：你可以看看Python中的bisect模块里的代码，了解一下。

提示2：切片可以用来在列表中插入元素：

>>> s = ['a', 'b', 'd', 'e']
>>> s[2:2] = ['c']
>>> s
['a', 'b', 'c', 'd', 'e']

Answer 3

使用 insort 函数，它属于 bisect 模块：

import bisect 
a = [1, 2, 4, 5] 
bisect.insort(a, 3) 
print(a)

输出结果

[1, 2, 3, 4, 5] 

如果你想要更复杂的用法，可以查看 insort 方法的 key 参数

import bisect
a = [{"key": 1}, {"key": 3}]
bisect.insort(a, {"key": 2}, key=lambda x: x["key"])
print(a)

输出结果

[{"key": 1}, {"key": 2}, {"key": 3}]