Python 的 sort()函数是否保证稳定？

文件并不保证这一点。还有其他地方记录在案吗？

我猜测它可能是稳定的，因为列表上的 sort 方法是 保证稳定(注意第9点: “从 Python 2.3开始，sort ()方法保证是稳定的”) ，并且 sort 在功能上是相似的。然而，我无法找到任何明确的来源，这样说。

Purpose: I need to sort based on a primary key and also a secondary key in cases where the primary key is equal in both records. If sorted() is guaranteed to be stable, I can sort on the secondary key, then sort on the primary key and get the result I need.

PS: 为了避免任何混淆，我使用了稳定性，意思是“如果排序保证不改变比较相等的元素的相对顺序，那么排序就是稳定的”。

43744 次浏览
小开
最佳答案

是的，手册的意图确实是保证 sorted是稳定的，并且确实使用与 sort方法完全相同的算法。我确实意识到文档并不是100% 清楚这个身份; 文档补丁总是被愉快地接受！

小开

"What's New" docs for Python 2.4有效地指出，sort ()首先创建一个列表，然后对其调用 sort () ，为您提供所需的保证，尽管这种保证不在“正式”文档中。如果你真的担心的话，你也可以查查源头。

小开

他们是 稳定。

顺便说一下: 通过将多次排序合并为单次排序，有时可以忽略排序和排序是否稳定。

例如，如果希望根据对象的 last_name、 first_name属性对它们进行排序，可以一次完成:

sorted_list= sorted(
your_sequence_of_items,
key= lambda item: (item.last_name, item.first_name))

利用元组比较。

这个答案涵盖了最初的问题。对于进一步排序相关的问题，有 Python 排序指南。

小开

与此同时，文档发生了变化(相关的承诺) ，而且 sorted的当前文档明确保证了这一点:

内置的 sorted()函数保证是稳定的。如果排序保证不改变比较相等的元素的相对顺序，那么排序就是稳定的ーー这有助于多次排序(例如，按部门排序，然后按工资级别排序)。

这部分文档是在 Python 2.7和 Python 3.4(+)中添加的，因此该语言版本的任何 compliant实现都应该为 有提供一个稳定的 sorted。

注意，对于 CPython，list.sort自 Python 2.3以来一直是稳定的

  • Tim Peters 重写了他的 list.sort()实现——这是一个“稳定排序”(输出中以相同的顺序出现相同的输入) ，并且比以前更快。

我不是100% 肯定的 sorted，现在它简单地使用 list.sort，但我还没有检查的历史。但它很可能“总是”使用 list.sort。

小开

关于排序的 Python 3.6文档现在指出

排序保证是稳定的

此外，在该文档中，还有一个到稳定 Timsort的链接，其中声明

自2.3版以来，Timsort 一直是 Python 的标准排序算法


提交答案