数据结构|数据结构（几种对列表进行搜索和排序的算法） python|算法

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 = balancedef __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 感兴趣的读者和程序员阅读。