list排序(list排序方法根据某个字段排序)

3.3.1　最小值搜索

Python的min函数将会返回列表里的最小值或最小元素。为了研究这个算法的复杂度，我们将会开发一个替代版本，使之返回最小元素的索引（index）。这个算法假定列表不为空，并且元素是按照任意顺序存放在列表里的。它首先把第一个位置作为存放最小元素的位置；然后向右侧搜索更小的元素，如果找到，那么把最小元素的位置重置为当前位置；当算法到达列表末尾时，它将返回最小元素的位置。如下所示为函数indexOfMin里实现这个算法的代码。

的列表进行

次比较，也就是说，它的复杂度为

。

3.3.2　顺序搜索列表

Python的in运算符在list类里被实现为叫作__contains__的方法，这个方法会在任意的元素列表里搜索特定的元素，即目标元素（target item）。在这个列表里，找到目标元素的唯一方法是从位于第一个位置的元素开始，并把它和目标元素进行比较。如果两个元素相等，那么这个方法返回True；否则，这个方法将移动到下一个位置，并把它和目标元素进行比较。如果这个方法到了最后一个位置仍然找不到目标，那么返回False。这种搜索称为顺序搜索（sequential search）或线性搜索（linear search）。好用的顺序搜索函数会在找到目标时返回元素的索引，否则返回?1。下面是顺序搜索函数的Python实现。

3.3.3　最好情况、最坏情况以及平均情况下的性能

有些算法的性能取决于需要处理的数据所在的位置。若顺序搜索算法在列表开头就找到目标元素，那么这时的工作量明显会比在列表末尾找到的工作量要少。对于这类算法，我们可以确定最好情况下的性能、最坏情况下的性能以及平均性能。一般来说，你应该把重点放在平均情况和最坏情况下的性能，而不用过于关心最好情况。

对顺序搜索的分析需要考虑下面3种情况。

在最坏情况下，目标元素位于列表的末尾或者根本就不在列表里。这时，这个算法就必须访问每一个元素，对大小为的列表需要执行次迭代。因此，顺序搜索的最坏情况的复杂度为。

在最好情况下，只需要O(1)的复杂度，因为这个算法在一次迭代之后就会在第一个位置找到目标元素。

要确定平均情况，就需要把每个可能位置找到目标所需要的迭代次数相加，然后再将它们的总和除以。因此，这个算法会执行 ( + ?1 + ?2+…+1)/或( + 1)/2次迭代。对于非常大的来说，常数系数2是可以忽略的，因此，平均情况的复杂度仍然是。

显然，最好情况下顺序搜索的性能和其他两种情况比起来小很多，而其他两种情况下的性能是差不多的。

3.3.4　基于有序列表的二分搜索

对于没有按照任何特定顺序排列的数据来说，只能使用顺序搜索来找到目标元素。在数据有序的情况下，就可以使用二分搜索了。

下面是二分搜索函数的代码。

的列表来说，也就是你需要执行

/2/2…/2次，直到结果为1。假设

是这个

可以除以2的次数，那么求解

会有

，即

，于是

。因此，二分搜索在最坏情况下的复杂度为

。

图3-7展示了在包含9个元素的列表里，通过二分搜索查找并不在列表里的目标元素10时，对列表进行的分解。在图3-7中，与目标元素进行比较的元素会被加上阴影。可以看到，原始列表左半部分中的任何元素都不会被访问。

对目标元素10的二分搜索需要4次比较，而顺序搜索将会需要10次比较。当问题规模变得更大时，很明显这个算法会表现得更好。对于包含9个元素的列表来说，它最多需要进行4次比较，而对于包含1000000个元素的列表最多需要进行20次比较就能完成搜索！

二分搜索肯定要比顺序搜索更有效。但是，只能基于列表里数据的组织结构来选择合适的搜索算法类型。为了让列表能够有序，二分搜索需要付出额外的成本。稍后，我们会了解一些对列表进行排序的策略并分析它们的复杂度。现在，让我们来了解一些关于比较数据元素的细节。

图3-7　二分搜索10时所访问的列表元素

3.3.5　比较数据元素

def __lt__(self, other):

如果self小于other，那么这个方法将返回True；否则，返回False。比较对象的标准取决于它们的内部结构以及所应该满足的顺序。

比如，SavingsAccount对象可能包含3个数据字段：名称、PIN（密码）以及余额。假定这个账户对象应该按照名称的字母顺序对它进行排序，那么就需要按照下面的方式来实现__lt__方法。

下面的代码将显示对若干个账户对象进行比较的结果。

本文摘自：数据结构 Python语言描述 第2版

本书用 Python 语言来讲解数据结构及实现方法。全书首先概述 Python 编程的功能—这些功能是实际编程和解决问题时所必需的；其次介绍抽象数据类型的规范、实现和应用，多项集类型，以及接口和实现之间的重要差异；随后介绍线性多项集、栈、队列和列表；最后介绍树、图等内容。本书附有大量的复习题和编程项目，旨在帮助读者巩固所学知识。

本书不仅适合高等院校计算机专业师生阅读，也适合对 Python 感兴趣的读者和程序员阅读。