python 的 sorted() 函数保证稳定吗？

问题描述：

文档没有保证这一点。还有其他地方有记录吗？

我猜它可能是稳定的，因为列表上的 sort 方法保证是稳定的（注意第 9 点：“从 Python 2.3 开始，sort() 方法保证是稳定的”），并且 sorted 在功能上是相似的。但是，我找不到任何确切的来源这么说。

目的：我需要根据主键和辅助键进行排序，以防两个记录的主键相等。如果 sorted() 保证稳定，我可以按辅助键排序，然后按主键排序并获得所需的结果。

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

解决方案 1：

是的，手册的目的确实是保证其sorted稳定性，并且确实使用与方法完全相同的算法sort。我确实意识到文档并没有 100% 清楚地说明这一身份；文档补丁总是被愉快地接受！

解决方案 2：

他们很稳定。

顺便说一句：有时，您可以通过将多遍排序与单遍排序相结合来忽略了解排序和已排序是否稳定。

例如，如果您想根据对象的last_name属性对其进行排序first_name，您可以一次性完成：

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

利用元组比较。

这个答案按原样涵盖了原始问题。 有关进一步的排序相关问题，请参阅Python 排序方法。

解决方案 3：

在此期间，文档发生了变化（相关提交），并且当前文档sorted明确保证了这一点：

内置sorted()函数保证稳定。如果排序保证不改变比较相等的元素的相对顺序，则排序是稳定的 — 这有助于多次排序（例如，先按部门排序，然后按薪资等级排序）。

该部分文档已添加到 Python 2.7 和 Python 3.4(+)，因此该语言版本的任何兼容实现都应该具有稳定的sorted。

请注意，对于 CPython 来说，自Python 2.3list.sort以来一直很稳定

• 蒂姆·彼得斯重写了他的list.sort()实现——这是一个“稳定排序”（相同的输入以相同的顺序出现在输出中）并且比以前更快。

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

解决方案 4：

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

排序保证稳定

此外，在该文档中，有一个指向稳定的Timsort的链接，其中指出

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

解决方案 5：

Python 2.4 的“新功能”文档有效地指出 sorted() 首先创建一个列表，然后对其调用 sort()，为您提供所需的保证，尽管“官方”文档中没有提到。如果您真的担心，也可以查看源代码。