《Python编程从0到1 视频教学版》_深入Python设计的本质_3.1.4 列表的排序

【摘要】 本书摘自《Python编程从0到1 视频教学版》一书中第3章，第1节，作者是张頔。

3.1.4 列表的排序

没有任何假设条件的情况下在列表中搜索，除了逐个扫描之外没有什么更好的办法， 这种查找的平均复杂度显然是 O(n)。 在数据有序的情况下，可以使用二分查找获得 0(log(n))的性能。因此排序是程序设计的基本手段。几乎各种语言都内建排序算法。在库 函数中实现排序算法，都要将算法本身与数据类型解耦，从而实现算法的泛型化以复用代 码。排序方法的接口往往能够体现出语言的本质特性。我们已经在2.1.6节中讲过 Python 是如何通过回调函数实现泛型的排序接口的。现在我们具备了对象的基本知识，再来完整 回顾一下排序接口：④

list.sort(key=none, reverse=false)

以及：

sorted(iterable, key=None, reverse=False)

前者直接修改原有列表(副作用),后者不修改原数据而返回新建列表(无副作 用)。从这两个方法的对比可以看到Python 接口设计的思路：在混合风格中，面向过 程的函数多被设计为无副作用的，需要对已有对象本身进行修改的操作则被设计为成 员方法。

解耦类型的核心是实现“两两比大小”的方法。 Python 通过传递 key()函数，把待排 序的对象转换为某种可比较大小的类型。这种类型可以是本就包含比较方法的内建类型， 如 int, 也可以是自定义的某种类型。对于自定义类型来说，排序的结果依赖于类型重载 的 t (比较运算符(<)。接口的最后一个参数reverse用来控制升序或降序。

【思考和扩展练习】

(1)查找其他主流编程语言的泛型排序算法的接口实现。

(2)为什么C 和 Java的泛型排序算法无须指定 reverse 参数。

(3)使用sort()和 sorted()对有理分数列表进行排序，应当如何设计key()方法。

(4)扩展2.5.3节中的有理分数类，增加 t ()成员方法，再直接使用默认比较行为

进行排序。

(5)编程语言内建的库排序算法的效率是O(log(n), 请编写测试程序验证这一点。

(6)设计有序列表的插入函数，在插入的同时保持列表有序。

3.1.5 有序列表的二分查找

在前两小节中分别讨论了列表的插入操作和排序操作。增加有序列表的数据时不能随 意将数据置于列表尾部，而是应当找到恰当位置进行插入操作。对于有序列表来说，使用 二分法确定插入位置，可以在O(log(n))时间内完成确定插入位置的工作。二分法确定插入 位置的示意图，如图3.8所示。

L.insert(?,100)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们 18664393530@aliyun.com 处理，核实后本网站将在24小时内删除侵权内容。