python的sorted（）函数是否保证稳定？

Question

documentation不能保证这一点。有没有其他地方记录在案？

我猜它可能是稳定的，因为列表上的sort方法是guaranteed to be stable（注意第9点：“从Python 2.3开始，sort（）方法保证是稳定的”），而sorted在功能上是类似的。但是，我找不到任何确切的消息来源。

目的：如果两个记录中的主键相等，我需要根据主键和次键进行排序。如果sorted（）被保证是稳定的，我可以对次键进行排序，然后对主键进行排序，得到所需的结果。

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

Answer 1

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

Answer 2

他们是stable。

顺便说一句：有时可以忽略sort和sorted是否稳定，方法是将一个多通道排序合并到一个单通道排序中。

例如，如果要根据对象的last_name，first_name属性对对象进行排序，可以在一次过程中完成：

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

利用元组比较。

这个答案，原封不动地涵盖了最初的问题。对于进一步排序相关问题，可以使用Python Sorting How-To。

Answer 3

同时更改的文档（relevant commit）和当前的文档^{}明确地保证：

The built-in sorted() function is guaranteed to be stable. A sort is stable if it guarantees not to change the relative order of elements that compare equal — this is helpful for sorting in multiple passes (for example, sort by department, then by salary grade).

这部分文档被添加到Python2.7和Python3.4（+）中，因此该语言版本的任何符合的实现都应该有一个稳定的sorted。

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

• Tim Peters rewrote his list.sort() implementation - this one is a "stable sort" (equal inputs appear in the same order in the output) and faster than before.

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