Python 列表的排序 - sort/sorted

Python 集合的遍历,推导及 filter/map/reduce 操作 中讲了对集合的 filter, map 和 reduce 操作，那还有 sort 排序呢？像 Java 一样，Python  也提供了 sort() 和 sorted() 方法。

sort() 是 list 的实例方法， sorted() 是一个内置函数。Python 中也是只有 list 才有顺序。

list.sort() 方法

查看 Python 3 中的 list.sort() 方法(help(list.sort))

Help on method_descriptor:

sort(self, /, *, key=None, reverse=False)
Stable sort *IN PLACE*.

Python 的 list.sort() 方法和 Java List.sort() 方法一样的，都是 IN PLACE 排序，没有返回值。实际看下各种排序场景

list.sort() 能直接对可比较比象进行排序，也就是两个对象间能用 < 号相比较，映射到函数就是 __lt__。数字字符串都能比，从前面看到两个 tuple 也可以比较，

如果两个元素之间不能进行比较的话，可以指定 key 参数来取出相关值进行比较，如上面的 key=lambda item: item[1], 取 tuple 的第二个元素进行 < 对较

再来看自定义对象的比较

users.sort() 不管 reverse 是 False 还是 True，始终是试图用 < 去比较两个对象。由于 User 没有定义 __lt__ 方法，所以不能直接对 User 进行排序，而必须指定 key=lambda user: user.get_name() 依照 get_name() 的返回值进行排序。

如何让对象是可比较的呢，或者直截说验证一下 Python 是否是调用了 __lt__ 方法来比较函数。接下来动态的给 User 类添加一个  __lt__ 方法，然后变 users.sort() 从不可能到可能

这时候发现不用指定 key 对 users 也可以排序了，比较时调用了 __lt__ 方法。

前面提到过只能对 list 进行排序，也就是只有 list 才有 sort() 方法，这也不难理解，set, tuple, dict 是不存在顺序观念的。但有意思的是，在对 set, tuple 转换成 list 后便自动立马有了顺序。

这也为接下来要看到的 sorted() 函数作了一个铺垫。前面只有 list 才有 sort() 方法，然而内置的 sorted() 函数除了对 list 进行排序，对 set 和 tuple 也能排序，效果上相当于转换为 list，再对 list 排序，所以最终 sorted() 后得到的都是一个 list。

内置的 sorted() 函数

同样，用 help(sorted) 看下它的原型

Help on built-in function sorted in module builtins:
sorted(iterable, /, *, key=None, reverse=False)
    Return a new list containing all items from the iterable in ascending order.
    A custom key function can be supplied to customize the sort order, and the
    reverse flag can be set to request the result in descending order.

之于 list.sort() 方法，我们只需记住 sorted() 的几个不同之处

1. 它是一个内置函数，所以第一个参数传入待排序的集合
2. 待排序的集合不受限于 list, 它是 iterable, 根据鸭子类型的规则，只要该类实现了 __iter__() 方法就是 iterable。具体说来就是能使用 for..in.. 进行遍历的都能排序，像 set, tuple, 或 dict.items() 等
3. 排序不再是 IN PLACE, 也就是它的排序不改变原集合，而是生成一个新的 list 并返回

其他的排序行为与list.sort() 函数是一致的。

看下执行效果，对 list, tuple 和  set 进行排序 

不用理会 Python 怎么显示 set 中的内容，因为 set 是不能用索引号访问的。无论是对 tuple 还是 set 排序后得到的结果都是 list，sorted() 对原集合是无副作用的。

对比一下 Java 的 sort()  与 sorted() 方法

先看一下 Java 的这两个方法, Java 的 Collections 的类提供了两个 sort 方法

它们接受的参数是 List, 所以也是只针对 List 进行排序，也是 IN PLACE 的, 也是无返回值的。sorted() 出现在 Java 的 Stream

它得到的结果还是 Stream，因此它也是无副作用的，最后需要 collect(tolist()) 得到一个新的集合。

关于排序算法

Python 和 Java 对 List 进行排序的算法都是 Timsort, 摘录一下中文维基百科中的内容

Timsort 是一种混合稳定的排序算法，源自合并排序和插入排序，旨在较好地处理真实世界中各种各样的数据。它使用了 Peter Mcllroy 的"乐观排序和信息理论上复杂性"中的技术，参见 第四届年度ACM-SIAM离散算法研讨会论文集，第467-474页，1993年。 它由 Tim Peters 在2002年实现，并应用于 Python编程语言。该算法通过查找已经排好序的数据子序列，在此基础上对剩余部分更有效地排序。 该算法通过不断地将特定子序列（称为一个 run ）与现有的 run 合并，直到满足某些条件为止来达成的更有效的排序。 从 2.3 版本起，Timsort 一直是 Python 的标准排序算法。 它还被 Java SE7^[4], Android platform^[5], GNU Octave,^[6] 谷歌浏览器,^[7] 和 Swift^[8] 用于对非原始类型的数组排序。