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

Question

该文档不保证.是否还有其他记录的地方？

我猜它可能是稳定的,因为列表上的排序方法保证是稳定的(注意第9点:"从Python 2.3开始,sort()方法保证稳定"),并且排序在功能上类似.但是,我无法找到任何明确的消息来源.

目的:在两个记录中主键相等的情况下,我需要根据主键和辅助键进行排序.如果sorted()保证稳定,我可以对辅助键进行排序,然后对主键进行排序并获得我需要的结果.

PS:为了避免任何混淆,我使用稳定的意思是"如果它保证不改变比较相等的元素的相对顺序,则排序是稳定的".

Answer 1

是的,本手册的目的确实是为了保证sorted稳定,并且确实使用与该sort方法完全相同的算法.我确实意识到文档并不是100%清楚这个身份; doc补丁总是被高兴地接受!

在这种情况下,这不是预期的吗？Python默认会比较所有元素的元组,而不仅仅是第一个"主要"元素.如果您只想对第一个元素进行排序,则可以显式传递`key`参数. (7认同)
我发现如果我正在排序元组或列表,只要"主"排序键相等,它就会以"辅助"键排序.例如,`sorted([(1,2),(1,1)])`返回`[(1,1),(1,2)]`而不是以相同的顺序/顺序返回原始输入.不应该保证稳定意味着它应该返回原始的`[(1,2),(1,1)]`输入？在这种情况下,你是明确的并且说`sorted([(1,2),(1,1)],key = lambda t:t [0])` (2认同)
@code_dredd 这是预期的行为。稳定排序的要点是使用“排序键”进行排序，但具有相同排序键的两个不同元素将具有相同的顺序。元组的默认排序键是元组的所有元素。 (2认同)

Answer 2

他们很稳定.

顺便说一句:你有时可以通过在单遍传递中组合多次传递排序来忽略排序和排序是否稳定.

例如,如果你想根据自己对对象进行排序last_name,first_name属性,你可以做一个合格:

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

利用元组比较.

这个答案原样涵盖了原始问题.有关进一步排序相关的问题,有Python排序方法.

@tzot我想提一下,总有这样的稳定排序要求.例如,我有一个元组列表(速率,注释),注释按照它们的生成顺序保存,我想按速率排序并保持时间顺序,但是,我没有保存列表中的时间戳.简单地说,我只想按比率对列表进行排序,并保持评论的顺序相同. (8认同)
如果要反转排序,这可能会产生不良影响.例如,在对产品进行排序时,您可能希望首先对评级(升序)进行排序,然后对价格进行排序(也是按升序排序).如果您反过来,您希望按降序排序评级,但按价格按升序排序.这不适用于此解决方案. (4认同)
事实上，这不是一个要求，但想在其他人阅读本文并在您的解决方案或使用 Python 的稳定排序功能之间做出选择时指出这种微妙的差异。 (3认同)
@RemcoWendt:没有要求你描述的内容.在任何情况下,请考虑`key = lambda item:( - item.rating,item.price)`或提供`cmp`而不是`key`参数.不过,我仍然不确定你评论的目的. (2认同)

Answer 3

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

\n\n

\n
保证内置sorted()功能稳定。如果保证不更改比较相等 \xe2\x80\x94 的元素的相对顺序，则排序是稳定的，这有助于多次排序（例如，按部门排序，然后按工资等级排序）。
\n

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n