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

Question

文档没有保证这一点。是否有其他地方有记录呢？

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

目的：我需要根据主键和次要键进行排序，在主键相同时也要考虑次要键。如果sorted()保证是稳定的，则可以先按次要键排序，然后按主键排序，从而获得所需结果。

PS：为避免混淆，我在这里使用“稳定”一词是指“如果一个排序保证不改变比较相等的元素的相对顺序”。

- Sundar R

Answer 1

是的，本手册的目的确实是保证sorted稳定，并且确实使用与sort方法完全相同的算法。我确实意识到文档在这个内容上并不完全清晰，欢迎提交文档补丁！

- Alex Martelli

---

我发现如果我对元组或列表进行排序时，“主”排序键相等，则会按“次要”键进行排序。例如，sorted([(1, 2), (1, 1)]) 返回 [(1, 1), (1, 2)]，而不是按照原始顺序返回相同的输入。稳定性的保证不应该意味着它应该返回原始输入吗？在这种情况下，您需要显式说明并使用 key=lambda t: t[0] 来排序：sorted([(1, 2), (1, 1)], key=lambda t: t[0])。 - code_dredd

这不是在这种情况下所期望的吗？Python默认会比较元组的所有元素，而不仅仅是第一个“主要”的元素。如果您只想按第一个元素排序，可以明确传递“key”参数。 - Matias Grioni

@code_dredd 这是预期的行为。stable-sort 的目的是使用“排序键”进行排序，但是具有相同排序键的两个不同元素将按照相同的顺序排列。元组的默认排序键是元组的所有元素。 - Guy

Answer 2

它们是稳定的。

顺便说一下：有时候你可以通过将多次排序组合成一次单通道排序来忽略了解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。

- tzot

---

如果您想要反转排序，这可能会产生不良影响。例如，在对产品进行排序时，您可能希望先按评分（升序）排序，然后按价格（也是升序）排序。如果您反转此操作，则希望按评分降序排序，但按价格升序排序。使用这种解决方案无法实现该目标。 - Remco Wendt

@RemcoWendt说并没有需要你所描述的那样。无论如何，考虑使用key=lambda item: (-item.rating, item.price)或提供一个cmp而不是一个key参数。但我仍然不确定你的评论目的是什么。 - tzot

这确实不是必需的，但我想指出这种微妙的差别，让其他人在选择你的解决方案或使用Python的稳定排序功能时能够有所侧重。 - Remco Wendt

我明白了。换句话说，按对排序更清晰，因此更可取，除非您关心性能。我想两个稳定的排序比一个按对排序要快一些，尽管差异可能微不足道 - ? - Sergey Orshanskiy

@tzot 我想提一下，稳定排序总会有这样的要求。例如，我有一个元组列表 (rate, comment)，评论按照它们被创建的顺序保存，我想按照评分进行排序，并保持时间顺序，然而，我没有在列表中保存时间戳。简而言之，我只想按照评分对列表进行排序，并保留相同的评论顺序。 - wsysuper

3.6 版本的排序文档明确告诉你稳定性是一个很好的属性，并且给出了一个复杂排序的例子。因此，我不同意这个回答中“不需要知道”的观点。正如 @wsysuper 所提到的，将信息编码到索引顺序中也很常见，需要保持稳定性。 - Wolfgang Kuehn

Answer 3

文档在此期间发生了变化（相关提交），而sorted的当前文档明确保证：

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

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

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

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

我对sorted没有100％的把握，现在它只是简单地使用list.sort，但我还没有检查过历史记录。但很可能它“始终”使用list.sort。

- MSeifert

Answer 4

Python 3.6文档中关于排序的说明现在已经明确表示：

排序是稳定的

此外，在该文档中，还有一个链接到稳定的Timsort算法的页面，其中指出：

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

- Wolfgang Kuehn

Answer 5

"Python 2.4的新特性"文档有效地表明sorted()首先创建一个列表，然后对其进行排序，为您提供了所需的保证，尽管它并未在“官方”文档中说明。如果您真的担心，也可以直接查看源代码。

- Peter Hansen

---

你能指出它在哪里说了吗？它说sorted()“像原地list.sort()一样工作”，并且“一个新形成的副本被排序”，但我没有看到它说它内部使用sort()。 - Sundar R

形成的“副本”是一个列表（这就是返回值），并且在返回之前对该列表调用.sort()。QED。不，这不是无懈可击的证明，但在Python有官方标准之前，你不会得到那个。 - Peter Hansen