python是否有一个sorting列表？
我的意思是一个结构：
- O（log n）
x.push()操作的复杂性 - O（log n）复杂度来查找元素
- 计算将被sorting的
list(x)O（n）复杂度
我也有一个相关的问题关于list(...).insert(...) ，现在在这里 。
标准的Python列表没有以任何formssorting。 标准的heapq模块可以用来追加O（log n），并删除O（log n）中最小的一个，但不是定义中的sorting列表。
Python的平衡树的各种实现可以满足你的需求，例如rbtree ， RBTree或pyavl 。
您的大O要求有特别的原因吗？ 或者你只是想要它快？ sortedcontainers模块是纯Python和快速的（就像blist和rbtree那样快速的C实现）。
性能比较显示它的基准更快或与blist的sorting列表types相当。 还要注意，rbtree，RBTree和PyAVL提供了sorting字典和集合types，但没有sorting列表types。
如果性能是一个要求，一定要记住基准。 一个模块，certificate快速与大O符号的要求应该怀疑，直到它也显示基准比较。
免责声明：我是Python sortedcontainers模块的作者。
安装：
pip install sortedcontainers
用法：
>>> from sortedcontainers import SortedList >>> l = SortedList() >>> l.update([0, 4, 1, 3, 2]) >>> l.index(3) 3 >>> l.add(5) >>> l[-1] 5
虽然我从来没有检查过基本的Python列表操作的“大O”速度，但在这种情况下，对bisect标准模块可能也值得一提：
import bisect L = [0, 100] bisect.insort(L, 50) bisect.insort(L, 20) bisect.insort(L, 21) print L ## [0, 20, 21, 50, 100] i = bisect.bisect(L, 20) print L[i-1], L[i] ## 20, 21
PS。 啊，对不起，在引用的问题中提到了对bisect 。 不过，我认为如果这方面的信息会在这里也不会有多大的伤害）
PPS。 CPython列表实际上是数组 （不是说，跳过列表等）。 那么，我想他们必须是简单的，但对我来说，这个名字有点误导。
所以，如果我没有弄错，那么对分/列表速度可能是：
- 推（）：O（n）为最坏的情况;
- 对于search：如果我们认为数组索引的速度是O（1），search应该是O（log（n））操作;
- 对于列表创build：O（n）应该是列表复制的速度，否则对于同一个列表是O（1））
UPD。 在评论的讨论之后，让我们在这里链接这些SO问题： Python的List是如何实现的 ？python list函数的运行时复杂度是多less
虽然它还没有提供自定义searchfunction，但heapq模块可能适合您的需求。 它使用常规列表实现一个堆队列。 你必须编写自己的高效的成员testing，利用队列的内部结构（可以在O（log n）中完成 ，我会说…）。 有一个缺点：提取sorting列表的复杂度为O（n log n） 。
import bisect class sortedlist(list): '''just a list but with an insort (insert into sorted position)''' def insort(self, x): bisect.insort(self, x)
我会使用biscect或sortedcontainers模块。 我真的没有经验，但我认为heapq模块工作。 它包含一个Heap Queue
在Python上实现自己的sorting列表可能并不困难。 以下是一个概念certificate：
import bisect class sortlist: def __init__(self, list): self.list = list self.sort() def sort(self): l = [] for i in range(len(self.list)): bisect.insort(l, self.list[i]) self.list = l self.len = i def insert(self, value): bisect.insort(self.list, value) self.len += 1 def show(self): print self.list def search(self,value): left = bisect.bisect_left(self.list, value) if abs(self.list[min([left,self.len-1])] - value) >= abs(self.list[left-1] - value): return self.list[left-1] else: return self.list[left] list = [101, 3, 10, 14, 23, 86, 44, 45, 45, 50, 66, 95, 17, 77, 79, 84, 85, 91, 73] slist = sortlist(list) slist.show() slist.insert(99) slist.show() print slist.search(100000000) print slist.search(0) print slist.search(56.7)
=========结果============
[3，10，14，17，23，44，45，45，50，66，73，77，79，84，85，86，91，95，101]
[3,10,14,17,23,44,45,45,50,66,73,77,79,84,85,86,91,95,99,101]条的规定，
101
3
50
