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

Question

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

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

目的：如果主键在两条记录中相等，我需要根据主键和辅助键进行排序。如果 sorted() 保证稳定，我可以先按次键排序，再按主键排序，得到我需要的结果。

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

score 144 · Accepted Answer

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

score 35 · Accepted Answer

他们是稳定的。

顺便说一句：通过将多遍排序组合在单遍排序中，您有时可以忽略知道 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。

score 4 · Accepted Answer

同时更改的文档（相关提交）和当前的文档sorted明确保证：

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

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

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

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

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

score 2 · Accepted Answer

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

保证排序是稳定的

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

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

score 0 · Accepted Answer

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

5 回答 5