排序和搜索

排序和搜索

目标

  • 能够解释和实现顺序查找和二分查找。
  • 能够解释和实现选择排序,冒泡排序,归并排序,快速排序,插入排序和希尔排序。
  • 理解哈希作为搜索技术的思想。
  • 引入映射抽象数据类型。
  • 使用哈希实现 Map 抽象数据类型。

    搜索

    我们现在把注意力转向计算中经常出现的一些问题,即搜索和排序问题。在本节中,我们将研究搜索。我们将在本章后面的章节中介绍。搜索是在项集合中查找特定项的算法过程。搜索通常对于项是否存在返回TrueFalse。有时它可能返回项被找到的地方。我们在这里将仅关注成员是否存在这个问题。

在Python中,有一个非常简单的方法来询问一个项是否在一个项列表中。我们使用in运算符。

1
2
3
4
5
>>> 15 in [3, 5, 2, 4, 1]
False
>>> 3 in [3, 5, 2, 4, 1]
True
>>>

这很容易写,一个底层的操作替我们完成这个工作。事实证明,有很多不同的方法来搜索。我们在这里感兴趣的是这些算法如何工作以及它们如何相互比较。

顺序查找

当数据项存储在诸如列表的集合中时,我们说它们具有线性或顺序关系。每个数据项都存储在相对于其他数据项的位置。在Python列表中,这些相对位置是单个项的索引值。由于这些索引值是有序的,我们可以按顺序访问它们。这个过程产生我们的第一种搜索技术顺序查找

Figure 1展示了这种搜索的工作原理。从列表中的第一个项目开始,我们按照基本的顺序排序,简单地从一个项移动到另一个项,直到找到我们正在寻找的项或遍历完整个列表。如果我们遍历完整个列表,则说明正在搜索的项不存在。
Figure 1

该算法的Python实现见CodeLens 1。该函数需要一个列表和我们正在寻找的项作为参数,并返回一个是否存在的布尔值。found布尔变量初始化为False,如果我们发现列表中的项,则赋值为True

1
2
3
4
5
6
7
8
9
def sequentialSearch(alist, item):
for a in alist:
if a == item:
return True
return False

testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(sequentialSearch(testlist, 3))
print(sequentialSearch(testlist, 13))

顺序查找分析

为了分析搜索算法,我们需要定一个基本计算单位。回想一下,这通常是为了解决问题要重复的共同步骤。对于搜索,计算比较操作数是有意义的。每个比较都有可能找到我们正在寻找的项目。此外,我们在这里做另一个假设。项列表不以任何方式排序。项随机放置到列表中。换句话说,项在列表任何位置的概率是一样的。

如果项不在列表中,知道它的唯一方法是将其与存在的每个项进行比较。如果有n个项,则顺序查找需要n个比较来发现项不存在。在项在列表中的情况下,分析不是那么简单。实际上有三种不同的情况可能发生。在最好的情况下,我们在列表的开头找到所需的项,只需要一个比较。在最坏的情况下,我们直到最后的比较才找到项,第 n个比较。

平均情况怎么样?平均来说,我们会在列表的一半找到该项; 也就是说,我们将比较 n/2项。然而,回想一下,当n变大时,系数,无论它们是什么,在我们的近似中变得不重要,因此顺序查找的复杂度是O(n)。Table 1总结了这些结果。
Table 1

二分查找

有序列表对于我们的比较是很有用的。在顺序查找中,当我们与第一个项进行比较时,如果第一个项不是我们要查找的,则最多还有n-1个项目。 二分查找从中间项开始,而不是按顺序查找列表。如果该项是我们正在寻找的项,我们就完成了查找。如果它不是,我们可以使用列表的有序性质来消除剩余项的一半。如果我们正在查找的项大于中间项,就可以消除中间项以及比中间项小的一半元素。如果该项在列表中,肯定在大的那半部分。

然后我们可以用大的半部分重复这个过程。从中间项开始,将其与我们正在寻找的内容进行比较。再次,我们找到元素或将列表分成两半,消除可能的搜索空间的另一部分。Figure 3展示了该算法如何快速找到值54。完整的函数见CodeLens 3中。
Figure 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def binarySearch(alist, item):
first = 0
last = len(alist) - 1
found = False

while first <= last and not found:
midpoint = (first + last) // 2
if alist[midpoint] == item:
found = True
else:
if item < alist[midpoint]:
last = midpoint - 1
else:
first = midpoint + 1

return found

testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binarySearch(testlist, 3))
print(binarySearch(testlist, 13))

CodeLens 3