Python 教程

Python 教程 Python 简介 Python 历史 Python 下载安装 Python 入门 Python 语法 Python 注释 Python 变量 Python 数据类型 Python 数值类型 Python 类型转换 Python 字符串 Python 布尔值 Python 运算符 Python 列表 Python 元组 Python 集合 Python 字典 Python If...Else Python While 循环 Python For 循环 Python 函数 Python Lambda Python 数组 Python 类和对象 Python 继承 Python 迭代 Python 作用域 Python 模块 Python 日期时间 Python 数学运算 Python JSON Python 正则表达式 Python PIP Python Try...Except Python 用户输入 Python 字符串格式化

Python 文件处理

Python 文件处理 Python 打开文件 Python 创建/写入文件 Python 删除文件

Python NumPy

NumPy 简介 NumPy 入门 NumPy 创建数组 NumPy 数组索引 NumPy 数组裁切 NumPy 数据类型 NumPy 副本 vs 视图 NumPy 数组形状 NumPy 数组重塑 NumPy 数组迭代 NumPy 数组连接 NumPy 数组拆分 NumPy 数组搜索 NumPy 数组排序 NumPy 数组过滤 NumPy 随机数 NumPy ufunc 通用函数

Python SciPy

SciPy 简介 SciPy 入门 SciPy 常量 SciPy 优化器 SciPy 稀疏数据 SciPy 图表 SciPy 空间数据 SciPy Matlab 数组 SciPy 插值 SciPy 统计显着性检验

Python 机器学习

Machine 机器学习入门 Machine 平均中位数模式 Machine 标准差 Machine 百分位数 Machine 数据分布 Machine 正态数据分布 Machine 散点图 Machine 线性回归 Machine 多项式回归 Machine 多元回归 Machine 缩放 Machine 训练/测试 Machine 决策树

Python MySQL

MySQL 入门 MySQL Create Database MySQL Create Table MySQL Insert MySQL Select MySQL Where MySQL Order By MySQL Delete MySQL Drop Table MySQL Update MySQL Limit MySQL Join

Python MongoDB

MongoDB 入门 MongoDB 创建数据库 MongoDB 创建集合 MongoDB 插入 MongoDB 查找 MongoDB 查询 MongoDB 排序 MongoDB 删除 MongoDB 删除集合 MongoDB 更新 MongoDB 限制

Python 参考手册

Python 参考手册 Python 内置函数 Python 字符串方法 Python 列表/数组方法 Python 字典方法 Python 元组方法 Python 集合方法 Python 文件方法 Python 关键字 Python 内置异常 Python 词汇表

Python 模块参考

Python 随机模块 Python 请求模块 Python 统计模块 Python 数学模块 Python cMath模块

Python 如何使用

Python 删除列表重复项 Python 反转字符串 Python 添加两个数字

Python 高级教程

Python 常用指引 将Python2代码迁移到Python3 将扩展模块移植到 Python3 Curses 编程 描述器使用指南 函数式编程指引 日志常用指引 日志操作手册 正则表达式使用指南 套接字编程指南 排序指南 Unicode 指南 如何利用urllib包获取网络资源 Argparse 教程 ipaddress 模块介绍 Argument Clinic 的用法 使用DTrace和SystemTap检测CPython 对象注解属性的最佳实践

Python 实例

Python 实例 Python 编译器 Python 练习 Python 测验 NumPy 测验 SciPy 测验

Python 排序指南

作者

Andrew Dalke 和 Raymond Hettinger

发布版本

0.1

摘要

Python 列表有一个内置的 list.sort() 方法可以直接修改列表。还有一个 sorted() 内置函数,它会从一个可迭代对象构建一个新的排序列表。

在本文档中,我们将探索使用Python对数据进行排序的各种技术。


基本排序

简单的升序排序非常简单:只需调用 sorted() 函数。它返回一个新的排序后列表:

>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]

你也可以使用 list.sort() 方法,它会直接修改原列表(并返回 None 以避免混淆),通常来说它不如 sorted() 方便 ——— 但如果你不需要原列表,它会更有效率。

>>> a = [5, 2, 3, 1, 4]
>>> a.sort()
>>> a
[1, 2, 3, 4, 5]

另外一个区别是, list.sort() 方法只是为列表定义的,而 sorted() 函数可以接受任何可迭代对象。

>>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})
[1, 2, 3, 4, 5]

关键函数

list.sort()sorted() 都有一个 key 形参用来指定在进行比较前要在每个列表元素上调用的函数(或其他可调用对象)。

例如,下面是一个不区分大小写的字符串比较:

>>> sorted("This is a test string from Andrew".split(), key=str.lower)
['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']

key 形参的值应该是个函数(或其他可调用对象),它接受一个参数并返回一个用于排序的键。 这种机制速度很快,因为对于每个输入记录只会调用一次键函数。

一种常见的模式是使用对象的一些索引作为键对复杂对象进行排序。例如:

>>> student_tuples = [
...     ('john', 'A', 15),
...     ('jane', 'B', 12),
...     ('dave', 'B', 10),
... ]
>>> sorted(student_tuples, key=lambda student: student[2])   # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

同样的技术也适用于具有命名属性的对象。例如:

>>> class Student:
...     def __init__(self, name, grade, age):
...         self.name = name
...         self.grade = grade
...         self.age = age
...     def __repr__(self):
...         return repr((self.name, self.grade, self.age))

>>> student_objects = [
...     Student('john', 'A', 15),
...     Student('jane', 'B', 12),
...     Student('dave', 'B', 10),
... ]
>>> sorted(student_objects, key=lambda student: student.age)   # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Operator 模块函数

上面显示的键函数模式非常常见,因此 Python 提供了便利功能,使访问器功能更容易,更快捷。 operator 模块有 itemgetter()attrgetter()methodcaller() 函数。

使用这些函数,上述示例变得更简单,更快捷:

>>> from operator import itemgetter, attrgetter

>>> sorted(student_tuples, key=itemgetter(2))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

>>> sorted(student_objects, key=attrgetter('age'))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Operator 模块功能允许多级排序。 例如,按 grade 排序,然后按 age 排序:

>>> sorted(student_tuples, key=itemgetter(1,2))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

>>> sorted(student_objects, key=attrgetter('grade', 'age'))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

升序和降序

list.sort()sorted() 接受布尔值的 reverse 参数。这用于标记降序排序。 例如,要以反向 age 顺序获取学生数据:

>>> sorted(student_tuples, key=itemgetter(2), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

>>> sorted(student_objects, key=attrgetter('age'), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

排序稳定性和排序复杂度

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

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

这可以被抽象为一个包装函数,该函数能接受一个列表以及字段和顺序的元组,以对它们进行多重排序。

>>> def multisort(xs, specs):
...     for key, reverse in reversed(specs):
...         xs.sort(key=attrgetter(key), reverse=reverse)
...     return xs

>>> multisort(list(student_objects), (('grade', True), ('age', False)))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

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


Decorate-Sort-Undecorate

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

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

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

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

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

>>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)]
>>> decorated.sort()
>>> [student for grade, i, student in decorated]               # undecorate
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

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

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

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

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

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

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


比较函数

与返回排序绝对值的键函数不同,比较函数计算两个输入的相对顺序。

例如,天平比较两个样本,给出相对顺序:更轻,相等,或更重。 同样,cmp(a, b) 之类的比较函数将在小于时返回负值,在输入相等时返回零,或在大于时返回正值。

从其他语言翻译算法时,经常会遇到比较函数。 此外,一些库提供比较功能作为其 API 的一部分。 例如,locale.strcoll() 是一个比较函数。

为了适应这些情况,Python 提供了 functools.cmp_to_key 来包装比较函数,使其可以用作键函数:

sorted(words, key=cmp_to_key(strcoll))  # locale-aware sort order

Odds 和 Ends

  • 对于区域感知排序,将 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))))
    >>> assert standard_way == double_reversed
    >>> standard_way
    [('red', 1), ('red', 2), ('blue', 1), ('blue', 2)]
    
  • 在对两个对象进行比较时,排序例程使用 < 。因此,通过定义一个 __lt__() 方法,很容易为一个类添加一个标准的排序顺序。

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

    然而,请注意,如果 __gt__() 没有实现,< 可以退回到使用 __lt__() (见 object.__lt__() )。

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

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