Python排序指南

排序稳定性和排序复杂度¶

排序保证是 稳定 的。 这意味着当多个记录具有相同的键值时，将保留其原始顺序。

>>> data=[('red',1),('blue',1),('red',2),('blue',2)]
>>> sorted(data,key=itemgetter(0))
[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]

注意 blue 的两个记录如何保留它们的原始顺序，以便 ('blue',1) 保证在 ('blue',2) 之前。

这个美妙的属性允许你在一系列排序步骤中构建复杂的排序。例如，要按 grade 降序然后 age 升序对学生数据进行排序，请先 age 排序，然后再使用 grade 排序：

>>> s=sorted(student_objects,key=attrgetter('age'))# sort on secondary key
>>> sorted(s,key=attrgetter('grade'),reverse=True)# now sort on primary key, descending
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Python 中使用的 Timsort 算法可以有效地进行多种排序，因为它可以利用数据集中已存在的任何排序。

使用装饰-排序-去装饰的旧方法¶

这个三个步骤被称为 Decorate-Sort-Undecorate ：

• 首先，初始列表使用控制排序顺序的新值进行修饰。

• 然后，装饰列表已排序。

• 最后，删除装饰，创建一个仅包含新排序中初始值的列表。

例如，要使用DSU方法按 grade 对学生数据进行排序：

>>> decorated=[(student.grade,i,student)fori,studentinenumerate(student_objects)]
>>> decorated.sort()
>>> [studentforgrade,i,studentindecorated]# undecorate
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

这方法语有效是因为元组按字典顺序进行比较，先比较第一项；如果它们相同则比较第二个项目，依此类推。

不一定在所有情况下都要在装饰列表中包含索引 i ，但包含它有两个好处：

• 排序是稳定的——如果两个项具有相同的键，它们的顺序将保留在排序列表中。

• 原始项目不必具有可比性，因为装饰元组的排序最多由前两项决定。 因此，例如原始列表可能包含无法直接排序的复数。

这个方法的另一个名字是 Randal L. Schwartz 在 Perl 程序员中推广的 Schwartzian transform。

既然 Python 排序提供了键函数，那么通常不需要这种技术。

使用 cmp 参数的旧方法¶

本 HOWTO 中给出的许多结构都假定为 Python 2.4 或更高版本。在此之前，没有内置 sorted() ， list.sort() 也没有关键字参数。相反，所有 Py2.x 版本都支持 cmp 参数来处理用户指定的比较函数。

在 Py3.0 中， cmp 参数被完全删除（作为简化和统一语言努力的一部分，消除了丰富的比较与 __cmp__() 魔术方法之间的冲突）。

在 Py2.x 中， sort 允许一个可选函数，可以调用它来进行比较。该函数应该采用两个参数进行比较，然后返回负值为小于，如果它们相等则返回零，或者返回大于大于的正值。例如，我们可以这样做：

>>> defnumeric_compare(x,y):
... returnx-y
>>> sorted([5,2,4,1,3],cmp=numeric_compare)
[1, 2, 3, 4, 5]

或者你可反转比较的顺序：

>>> defreverse_numeric(x,y):
... returny-x
>>> sorted([5,2,4,1,3],cmp=reverse_numeric)
[5, 4, 3, 2, 1]

将代码从 Python 2.x 移植到 3.x 时，如果用户提供比较功能并且需要将其转换为键函数，则会出现这种情况。 以下包装器使这很容易：

defcmp_to_key(mycmp):
'Convert a cmp= function into a key= function'
classK:
def__init__(self,obj,*args):
self.obj=obj
def__lt__(self,other):
returnmycmp(self.obj,other.obj)<0
def__gt__(self,other):
returnmycmp(self.obj,other.obj)>0
def__eq__(self,other):
returnmycmp(self.obj,other.obj)==0
def__le__(self,other):
returnmycmp(self.obj,other.obj)<=0
def__ge__(self,other):
returnmycmp(self.obj,other.obj)>=0
def__ne__(self,other):
returnmycmp(self.obj,other.obj)!=0
returnK

要转换为键函数，只需包装旧的比较函数：

>>> sorted([5,2,4,1,3],key=cmp_to_key(reverse_numeric))
[5, 4, 3, 2, 1]

在 Python 3.2 中， functools.cmp_to_key() 函数被添加到标准库中的 functools 模块中。

其它¶

• 对于区域相关的排序，请使用 locale.strxfrm() 作为键函数，或者 locale.strcoll() 作为比较函数。

• reverse 参数仍然保持排序稳定性（因此具有相等键的记录保留原始顺序）。 有趣的是，通过使用内置的 reversed() 函数两次，可以在没有参数的情况下模拟该效果：

  >>> data=[('red',1),('blue',1),('red',2),('blue',2)]
  >>> standard_way=sorted(data,key=itemgetter(0),reverse=True)
  >>> double_reversed=list(reversed(sorted(reversed(data),key=itemgetter(0))))
  >>> assertstandard_way==double_reversed
  >>> standard_way
  [('red', 1), ('red', 2), ('blue', 1), ('blue', 2)]
  

• 在两个对象之间进行比较时，保证排序例程使用 __lt__() 。 因此，通过定义 __lt__() 方法，可以很容易地为类添加标准排序顺序:

  >>> Student.__lt__=lambdaself,other:self.age<other.age
  >>> sorted(student_objects)
  [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
  

• 键函数不需要直接依赖于被排序的对象。键函数还可以访问外部资源。例如，如果学生成绩存储在字典中，则可以使用它们对单独的学生姓名列表进行排序：

  >>> students=['dave','john','jane']
  >>> newgrades={'john':'F','jane':'A','dave':'C'}
  >>> sorted(students,key=newgrades.__getitem__)
  ['jane', 'dave', 'john']