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

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

    推荐阅读