数据结构：几种对列表进行搜索和排序的算法

3.3.1　最小值搜索

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

def indexOfMin(lyst):
    """Returns the index of the minimum item."""
    minIndex = 0
    currentIndex = 1
    while currentIndex < len(lyst):
        if lyst[currentIndex] < lyst[minIndex]:
            minIndex = currentIndex
        currentIndex += 1
    return minIndex

可以看到，无论列表的大小如何，循环外的3条指令都会执行相同的次数，因此，可以忽略它们。循环里还有3条指令，其中if语句里的比较和currentIndex的自增会在每次循环时都执行，而且这些指令里也没有嵌套或隐藏的循环。这个算法必须要访问列表里的每个元素，从而保证它能够找到最小元素的位置，而这个工作实际上是在if语句的比较操作里完成的。因此，这个算法必须对大小为

的列表进行

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

。

3.3.2　顺序搜索列表

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

def sequentialSearch(target, lyst):
    """Returns the position of the target item if found,
    or -1 otherwise."""
    position = 0
    while position < len(lyst):
        if target == lyst[position]:
             return position
        position += 1
    return -1

顺序搜索的分析和最小值搜索的分析有些不同，你将在后面看到。

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

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

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

• 在最坏情况下，目标元素位于列表的末尾或者根本就不在列表里。这时，这个算法就必须访问每一个元素，对大小为的列表需要执行次迭代。因此，顺序搜索的最坏情况的复杂度为。
• 在最好情况下，只需要O(1)的复杂度，因为这个算法在一次迭代之后就会在第一个位置找到目标元素。
• 要确定平均情况，就需要把每个可能位置找到目标所需要的迭代次数相加，然后再将它们的总和除以。因此，这个算法会执行 ( + −1 + −2+…+1)/或( + 1)/2次迭代。对于非常大的来说，常数系数2是可以忽略的，因此，平均情况的复杂度仍然是。

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

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

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

要了解二分搜索的工作原理，可以想想如果要在20世纪那种纸质电话簿里找某个人的电话号码，你会怎么做。电话簿里的数据已经是有序的，因此不需要通过顺序搜索进行查找。你可以根据姓名的字母来估计它在电话簿里所处的位置，然后尽可能地在接近这个位置的地方打开它。打开电话簿之后，你就可以知道按照字母顺序目标姓名会在前面还是后面，然后根据需要再向前或向后翻页。不断重复这个过程，直至找到这个姓名，或知道电话簿里并没有包含这个姓名。

接下来想一想用Python进行二分搜索的情况。在开始之前，假设列表里的元素都以升序排序（和电话簿一样）。搜索算法首先到列表的中间位置，并把这个位置的元素与目标元素进行比较，如果匹配，那么算法就返回当前位置。如果目标元素小于当前元素，那么算法将会搜索中间位置之前的部分；如果目标元素大于当前元素，则搜索中间位置之后的部分。在找到了目标元素或者当前开始位置大于当前结束位置时，停止搜索过程。

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

def binarySearch(target, sortedLyst):
     left = 0
     right = len(sortedLyst) - 1
     while left <= right:
        midpoint = (left + right) // 2
        if target == sortedLyst[midpoint]:
            return midpoint
        elif target < sortedLyst[midpoint]:
            right = midpoint - 1
        else:
            left = midpoint + 1
     return -1

算法里只有一个循环，并且没有嵌套或隐藏的循环。和前面类似，如果目标不在列表里，就会得到最坏情况。在这个算法里，循环在最坏情况下会运行多少次？它等于列表的大小不断除以2直到商为1的次数。对于大小为

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

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

是这个

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

会有

，即

，于是

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

。

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

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

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

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

3.3.5　比较数据元素

二分搜索和最小值搜索都有一个假设，那就是“列表里的元素彼此之间是可以比较的”。在Python里，这也意味着这些元素属于同一个类型，并且它们可以识别比较运算符==、<和>。几种Python内置的类型对象，如数字、字符串和列表，均支持使用这些运算符进行比较。

为了能够让算法对新的类对象使用比较运算符==、<和>，程序员应在这个类里定义__eq__、__lt__和__gt__方法。在定义了这些方法之后，其他比较运算符的方法将自动生成。__lt__的定义如下。

def __lt__(self, other):

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

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

class SavingsAccount(object):
    """This class represents a savings account
    with the owner’s name, PIN, and balance."""

    def __init__(self, name, pin, balance = 0.0):
        self.name = name
        self.pin = pin
        self.balance = balance

    def __lt__(self, other):
        return self.name < other.name

    # Other methods, including __eq__

可以看到，__lt__方法会为两个账户对象的name字段调用运算符<。名称字段是字符串，字符串类型已经包含在__lt__方法里。因此，在使用运算符<时，Python会自动运行字符串的__lt__方法，这个状况与调用str函数时自动运行__str__方法是类似的。

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

>>> s1 = SavingsAccount("Ken", "1001", 0)
>>> s2 = SavingsAccount("Bill", "1001", 30)
>>> s1 < s2
False
>>> s2 < s1
True
>>> s1 > s2
True
>>> s2 > s1
False
>>> s2 == s1
False
>>> s3 = SavingsAccount("Ken", "1000", 0)
>>> s1 == s3
True
>>> s4 = s1
>>> s4 == s1
True

现在，可以把账户放在列表中，并按照名称对它进行排序了。

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

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

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