Python中sorted()内置函数与list insert()方法的效率比较

Question

虽然我对它不陌生，但我并不经常使用Python，我的知识面比较广泛，而且对这门语言的了解也不是很深入。也许在这里有更加熟悉的人可以回答我的问题。我发现自己需要将项目添加到列表中，并保持项目添加时的排序。一种快速的方法是：

list.append(item)                  // O(1)
list.sort()                        // ??

我想如果这是向列表添加项的唯一方法，我希望排序会相当高效，因为在每次添加时都会对列表进行排序。但是还有另一种方法也可以实现同样的功能：

inserted = False
for i in range(len(list)):         // O(N)
    if (item < list[i]): 
        list.insert(i, item)       // ??
        inserted = True
        break
if not inserted: list.append(item)

有人能告诉我哪个更有效率吗？虽然我倾向于第二组语句，但实际上我并不确定。

- Cory Gross

---

http://wiki.python.org/moin/TimeComplexity 显示.insert()的时间复杂度为O(N)，而.sort()的时间复杂度为O(N log N)。 - Wooble

请注意，您提出的第二种情况根本无法添加比列表中已有的所有内容都少的项目。 - Wooble

@Wooble，这种情况下.sort()的时间复杂度是O(N)，因为除了新项之外，列表已经排序好了。 - John La Rooy

根据您的需求，heapq 可能是更好的选择。 - John La Rooy

如果您需要在允许频繁插入的同时保持数据排序，那么树可能比列表更好。不幸的是，Python没有自带的排序树类型。幸运的是，有几个库可供使用。有关更多信息，请参见@Princess Of the Universe的答案中的链接。 - jimhark

Answer 1

你需要的是二分模块，很可能还需要 insort_left。

因此，你的表达式可以等价地写成：

from

some_list.append(item)                  // O(1)
some_list.sort()                        // ??

to

bisect.insort_left(some_list, item)

- Abhijit

Answer 2

除了靠近末尾的位置之外，插入任何位置都需要O(n)的时间，因为它必须移动（复制）插入点后面的所有元素。但另一方面，所有基于比较的排序算法在平均情况下必须进行Ω(n log n)次比较。许多排序算法（包括Python使用的timsort）在许多输入上表现得更好，可能包括您的输入（“几乎排序”的情况）。它们仍然必须移动至少与立即插入正确位置相同数量的元素。它们还必须做很多额外的工作（检查所有元素以确保它们的顺序正确，以及更复杂的逻辑，通常可以提高性能，但在您的情况下不能）。由于这些原因，对于大型列表来说，它可能会更慢。

由于它是用C编写的（在CPython中；但对其他Python也适用类似的推理），因此它可能仍然比你用Python线性扫描写的更快。这就引出了如何找到插入点的问题。二分查找可以在O（log n）时间内完成此部分，因此在这里非常有用（当然，插入仍然是O（n），但如果您想要排序列表，则无法避免这一步骤）。不幸的是，二分查找实现起来相当棘手。幸运的是，它已经在标准库中实现了：bisect。

- user395760

---

排序需要O(n log n)的时间。你是指最优情况下的复杂度吗？ - Abhijit

@Abhijit我认为那不是正确的术语（对于许多排序算法，最佳情况是已排序的输入，并且它们可以在O（n）时间内处理）。但你说得对，我的措辞不太理想。我将看看如何改进这一部分。 - user395760

@Abhijit：timsort在平均和最坏情况下的时间复杂度为O(N log N)，在最好情况下为O(N)。 - Wooble