python的sorted()函数是否保证稳定性？

Question

这个文档并没有保证这一点。还有其他地方有说明吗？

我猜可能是稳定的，因为列表的排序方法是保证稳定的（第9点说明：“从Python 2.3开始，sort()方法是保证稳定的”），而sorted的功能上也很相似。不过，我找不到任何明确的来源来证实这一点。

目的：我需要根据一个主要的关键字来排序，如果两个记录的主要关键字相同，我还需要根据一个次要的关键字来排序。如果sorted()是保证稳定的，我可以先根据次要关键字排序，再根据主要关键字排序，这样就能得到我想要的结果。

附注：为了避免混淆，我这里说的稳定是指“如果排序保证不改变相等元素的相对顺序，那么这个排序就是稳定的”。

Answer 1

文档在这段时间内发生了变化（相关提交），现在的文档中明确说明了sorted的特性：

内置的sorted()函数是保证稳定的。一个排序是稳定的，如果它能保证在比较相等的元素之间不改变它们的相对顺序——这对于多次排序很有帮助（比如，先按部门排序，再按薪资等级排序）。

这部分内容是在Python 2.7和Python 3.4（及以上版本）中添加的，所以任何符合这些版本的实现都应该有一个稳定的sorted。

需要注意的是，对于CPython来说，list.sort从Python 2.3开始就是稳定的。

• Tim Peters重写了他的list.sort()实现——这个实现是“稳定排序”（相同的输入在输出中保持相同的顺序），而且比之前更快。

我对sorted不是百分之百确定，现在它简单地使用list.sort，但我没有查过这方面的历史。不过，很可能它“总是”使用list.sort。

Answer 2

它们是 稳定的。

顺便说一下：有时候你可以不必太在意排序方法是否稳定，通过将多次排序合并成一次排序来解决。

比如说，如果你想根据对象的 last_name 和 first_name 属性来排序，你可以在一次操作中完成：

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

这就是利用了元组比较的特点。

这个回答已经涵盖了原始问题。如果你还有其他关于排序的问题，可以参考 Python 排序指南。

Answer 3

是的，这份手册的目的是确保 sorted 是稳定的，也就是说它的排序方式不会改变相同元素的顺序。而且它确实使用和 sort 方法完全相同的算法。我知道文档没有百分之百清楚地说明这一点；如果有人能帮忙修改文档，我们都会很欢迎！