问题:python的sorted()函数是否保证稳定?

文档不能保证。还有其他记录在案的地方吗?

我猜想它可能是稳定的,因为可以保证列表上的sort方法是稳定的(注9:“从Python 2.3开始,保证sort()方法是稳定的”),并且sorted在功能上相似。但是,我找不到任何明确的说法。

目的:如果两个记录中的主键相等,则需要基于主键和辅助键进行排序。如果保证sorted()是稳定的,那么我可以对辅助键进行排序,然后对主键进行排序,并获得所需的结果。

PS:为避免任何混乱,我使用“稳定”的含义是“排序是稳定的,如果它保证不更改比较相等的元素的相对顺序”。

The documentation doesn’t guarantee that. Is there any other place that it is documented?

I’m guessing it might be stable since the sort method on lists is guaranteed to be stable (Notes 9th point: “Starting with Python 2.3, the sort() method is guaranteed to be stable”), and sorted is functionally similar. However, I’m not able to find any definitive source that says so.

Purpose: I need to sort based on a primary key and also a secondary key in cases where the primary key is equal in both records. If sorted() is guaranteed to be stable, I can sort on the secondary key, then sort on the primary key and get the result I need.

PS: To avoid any confusion, I’m using stable in the sense of “a sort is stable if it guarantees not to change the relative order of elements that compare equal”.


回答 0

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

Yes, the intention of the manual is indeed to guarantee that sorted is stable and indeed that it uses exactly the same algorithm as the sort method. I do realize that the docs aren’t 100% clear about this identity; doc patches are always happily accepted!


回答 1

他们是稳定的

顺便说一句:您有时可以通过将多遍排序组合到单遍排序中而忽略了解排序和排序是否稳定。

例如,如果要排序基于它们的对象last_namefirst_name属性,你可以做一个合格:

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

利用元组比较。

此答案按原样涵盖了原始问题。对于与排序有关的其他问题,有Python排序方法

They are stable.

By the way: you sometimes can ignore knowing whether sort and sorted are stable, by combining a multi-pass sort in a single-pass one.

For example, if you want to sort objects based on their last_name, first_name attributes, you can do it in one pass:

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

taking advantage of tuple comparison.

This answer, as-is, covers the original question. For further sorting-related questions, there is the Python Sorting How-To.


回答 2

同时更改了文档(相关的commit),并且的当前文档sorted明确保证:

内置sorted()功能保证稳定。如果可以保证不更改比较相等的元素的相对顺序,则排序是稳定的-这有助于多次通过排序(例如,按部门排序,然后按薪级等级排序)。

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

请注意,对于CPython,list.sortPython 2.3起一直保持稳定

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

我目前尚不确定100%的sorted使用率list.sort,但现在还可以查看历史记录。但是很可能“总是”使用了它list.sort

The documentation changed in the meantime (relevant commit) and the current documentation of sorted explicitly guarantees it:

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).

This part of the documentation was added to Python 2.7 and Python 3.4(+) so any compliant implementation of that language version should have a stable sorted.

Note that for CPython the list.sort has been stable since 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.

I’m not 100% sure on sorted, nowadays it simple uses list.sort, but I haven’t checked the history for that. But it’s likely that it “always” used list.sort.


回答 3

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

The “What’s New” docs for Python 2.4 effectively make the point that sorted() first creates a list, then calls sort() on it, providing you with the guarantee you need though not in the “official” docs. You could also just check the source, if you’re really concerned.


回答 4

现在,有关排序的Python 3.6文档指出:

排序保证稳定

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

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

The Python 3.6 doc on sorting now states that

Sorts are guaranteed to be stable

Furthermore, in that document, there is a link to the stable Timsort, which states that

Timsort has been Python’s standard sorting algorithm since version 2.3


声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。