python数据结构与算法27 排序与查找 顺序查找

排序与查找

目标

理解并实现顺序查找和二分查找

理解并实现选择排序,冒泡排序,合并排序,快速排序,插入排序和shell排序

理解哈希表用于查找的技术

介绍映射的抽象数据类型

用哈希表实现映射的抽象数据类型


查找

现在我们转向排序与查找的内容,这一节研究查找,后半章研究排序。查找是在一个数据集里找到某个特定元素的算法过程。查找的结果可能是找到或没找到,所以返回值是TrueFalse。这里为简单起见,我们只涉及与列表成员相关的问题。

python里,有一个非常简单的方法查询某数据是否在列表里,使用in操作符:

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

False

>>> 3in [3,5,2,4,1]

True

>>> 

虽然这样写很简单,不过这个算法后面的处理过程我们还是要学习,查找有很多种方法,我们感兴趣的是算法以及算法之间的比较。

顺序查找

数据存储在数据集,象list一类的集合,我们说他们是线性的或者是顺序的。每个数据项都保存有相对的位置。在python的列表里,每个项的相对位置用index值表示。Index是有序的,这样就产生了第一种查找算法:顺序查找

如图1所示,从列表的第一个元素开始,一个接一个检查,直到找到或全部找完,如果找完全部项,可以判断这个项在列表中不存在。

python数据结构与算法27 排序与查找 顺序查找

以下是这种算法的实现。这个函数的参数有:列表,待查项,返回值是布尔值。布尔变量found初始值为False,如果找到就被赋值True.

 

1

def sequentialSearch(alist, item):

2

    pos = 0

3

    found = False

4

5

    while pos < len(alist) and not found:

6

        if alist[pos] == item:

7

            found = True

8

        else:

9

            pos = pos+1

10

11

    return found

12

13

testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]

14

print(sequentialSearch(testlist, 3))

15

print(sequentialSearch(testlist, 13))


顺序查找的性能分析

要分析查找算法,先要决定一个基本计算单位。记得一般是解决问题的每一次重复算做一步。对查找来说,应该就是比较是与不是的次数。另外的一个假设就是列表是无序的,数据项在列表里随机安放,换句话说,数据项可能在列表的任何一个位置。

如果数据项不在列表里,唯一的判定办法就是把全部项逐个比较一番。如果表中有n个数据,顺序查找就需要n次比较。但是分析没有这么简单,有三种情形可能发生,最好的情况下,第一个项就是我们要找的,只有1次比较。最差的情况下,需要n次比较,全部比较过之后才知道找不到。

平均情况如何呢?在平均情况下,我们会发现是列表的一半,即平均要比较n/2次。回想一下,不论系数多大,在我们这里无关紧要,也就是说顺序查找的性能是O(n)。表1是各种结构的汇总。

Table 1: Comparisons Used in a Sequential Search of an Unordered List

Case

Best Case

Worst Case

Average Case

item is present

1

n

n/2

item is not present

n

n

n

前面我们有一个假设,就是数据项在列表里面位置是随机的,所以之间没有相对顺序。但是假如表中数据项以某种方式排序了,怎样来查找呢?又怎样利用这个特性来获得更好的效率呢?

假如列表元素是升序排列的,即从低到高。如果数据项在列表中仍然是随机的,我们将仍然比较相同的次数来找到它。然而,如果元素不在列表里,在性能上会稍有提高。如图2所示的查找50的过程。注意数据项与列表元素逐个比较直到54,这里我们遇到个特殊情况,不但54不是我们要找的,而且54后面的元素也不是我们要找的,因为元素是有序的!这时算法就不必继续遍历所有元素后才报告找不到,它可以在找到54后立即终止查找。

python数据结构与算法27 排序与查找 顺序查找

2 有序整数列表的查找

1    def orderedSequentialSearch(alist, item):

2          pos = 0

3          found = False

4          stop = False

5          while pos < len(alist) and not found and not stop:

6              if alist[pos] == item:

7                  found = True

8              else:

9                  if alist[pos] > item:

10                     stop = True

11                 else:

12                     pos = pos+1

13    

14         return found

15    

16     testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]

17     print(orderedSequentialSearch(testlist, 3))

18 print(orderedSequentialSearch(testlist, 13))

2 是性能汇总,注意在最好的情况下,数据不在表中可以只找一个元素,平均情况下,要查找n/2次,但是这种技术仍然是O(n)。总的来说,顺序查找的性能提供只有在顺序列表中找不到的情况下存在。

Table 2: Comparisons Used in Sequential Search of an Ordered List

item is present

1

n

n/2

item not present

1

n

n/2



python数据结构与算法27 排序与查找 顺序查找,布布扣,bubuko.com

python数据结构与算法27 排序与查找 顺序查找

上一篇:spring junit--基础配置


下一篇:初识springMVC