第11章 查找与排序.ppt

1、,第十一章 查找和排序,本章内容,查找 顺序查找 二分查找 二叉排序树查找 哈希查找 平均查找长度的计算,排序 直接插入排序 直接选择排序 冒泡排序,查找的基本概念,查找：在数据元素集合(查找表)中查找关键字与给定值相等的数据元素。 关键字：数据元素中的一个或多个数据项值，它可以惟一标识一个数据元素。 平均查找长度(ASL)：,式中，n为查找表的长度；pi为查找第i个元素的概率，在等概率情况下pi等于1/n； Ci为找到第i个元素时的比较次数,顺序查找,要求： 查找表必须采用线性表。 基本思想：用给定值依次与线性表中每个元素的关键字进行比较。如果某个元素的关键字与给定值相同，则查找成功；如果找

2、遍全表也没有发现满足条件的元素，则查找失败。 算法实现： 顺序表类和单链表类中的search函数。, 实现一：顺序表类中实现顺序查找的成员函数,/查找元素x并返回其下标，若元素不存在，则返回-1 /被查找的数存放在一个数组中，从数组的第一个元素开始，依次往下比较，直到找到要找的元素为止。 int Seqlist:Search ( char x ) int i = 0; for( i = 0; i length; i+ ) if (elementi = x ) return i + 1; return -1; , 实现二：单链表类中实现顺序查找的成员函数,/查找元素x并返回其地址，若元素不存在，

3、则返回空 Node * LinkedList:Search ( int x ) Node *p = head - next; while( p != NULL ) if( p - data = x ) break; p = p - next; return p; ,顺序查找的平均查找长度 评价：在用顺序查找方法完成查找时，每进行一次成功查找需要的平均比较次数约为表长度的一半，因此，它的效率较低。适用于在查找表较小的情况下进行查找。,二分查找（折半查找）,要求： 必须以顺序方式存储线性表 线性表中所有数据元素必须按照关键字有序排列 基本思想：将给定值与处于顺序表“中间位置”上的元素的关键字进行比

4、较，若相等则查找成功；若给定值大于关键字则在表的后半部分继续进行二分查找，否则在表的前半部分继续进行二分查找。如此进行下去直至找到满足条件的元素，或当前查找区为空，此时查找失败。,1.设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点，k为给定值。2.初始时，令 low = 0，high = n - 1，mid= (low+high)/2让 k 与 mid 指向的记录比较 若 k = rmid ，查找成功 若 k rmid ，则low = mid + 13.重复上述操作，直至low high时，查找失败。,二分查找算法实现,二分查找过程,找21,例如 key = 2

5、1 的查找过程,low 指示查找区间的下界 high 指示查找区间的上界 mid = (low+high)/2,例key = 70 的查找过程,low,high,mid,找70,5 13 19 21 37 56 64 75 80 88 92,low,high,mid,5 13 19 21 37 56 64 75 80 88 92,low,high,mid,5 13 19 21 37 56 64 75 80 88 92,low,high,mid,0 1 2 3 4 5 6 7 8 9 10,0 1 2 3 4 5 6 7 8 9 10,0 1 2 3 4 5 6 7 8 9 10,0 1 2 3

6、 4 5 6 7 8 9 10,5 13 19 21 37 56 64 75 80 88 92,5 13 19 21 37 56 64 75 80 88 92,low,high,5 13 19 21 37 56 64 75 80 88 92,当下界low大于上界high时，则说明表中没有关键字等于key的元素，查找不成功。,0 1 2 3 4 5 6 7 8 9 10,0 1 2 3 4 5 6 7 8 9 10,例：二分查找函数模板及其测试程序,例：用递归方法实现二分查找函数模板,二分查找,在二分查找中，比较的次数取决于所要查找的元素在数组中的位置。对于n个元素的数组，在最坏的情况下所要查找

7、的元素必须查到查找区间只剩下一个元素时才能找到或者能确定该元素根本不在数组中。,二分查找优缺点,优点： 查找效率高 平均查找长度 缺点： 查找前要将表中元素按关键字有序排列 只适用于线性表的顺序存储。适用于那种一经建立就很少改动而又经常需要查找的线性表。,搜索算法的效率,顺序搜索的平均时间性能 （1 + 2 + 3 + + n ) / n = ( n + 1 ) / 2 二分查找的最坏情况的时间性能 n / 2 / 2 / 2 / 2 = 1 n=2k 使用二分查找算法最多只需要k=log2n次比较即可,平均查找长度：,平均查找长度：,N和log2N的值,二叉排序树查找,将数据集合中的数据元素

8、存储为一颗二叉排序树， 然后按给定方法进行查找。 二叉排序树的定义： 二叉排序树或者是一棵空二叉树，或者 是具有以下性质的二叉树： 若它的左子树非空，则左子树上所有结点的值均小于根结点的值； 若它的右子树非空，则右子树上所有结点的值均不小于根结点的值； 左、右子树本身又各是一棵二叉排序树。,二叉排序树,二叉排序树：一种特殊的二叉树，其特点是：左子树上所有结点的值均小于其双亲结点的值，右子树上所有结点的值均大于或等于其双亲结点的值。,不是二叉排序树。, 插入操作：,若二叉排序树为空，则新结点为二叉排序树的根结点；否则将新结点的关键字值和根结点的关键字值进行比较，若小于根结点的值，则将新结点插入到

9、左子树中去，否则，插入到右子树中去。此插入过程是递归进行的。, 设有整数序列47,23,56,15,26,89,将其中的值依次插入二叉排序树,56,89,47,23,15,26,15,23,26,47,56,89,中序遍历结果：,对二叉排序树进行中序遍历可以得到一个数据元素由小到大的有序序列。构造二叉排序树的过程即为对无序序列进行排序的过程。, 删除操作：,一个结点被删除后，必须保证余下的结点仍然构成一棵二叉排序树。下面分三种情况讨论：,情况二：被删除的结点至少有一棵空子树，则用那棵非空子 树的根成为其双亲结点的相应子女,情况一：若被删除的是叶结点，则将对应双亲结点指针域置空,情况三：被删除的

10、结点有两棵非空的子树,方法一：找到被删除结点在中序遍历序列中的直接后继结点（它一定在被删除结点的右子树中），用此后继结点的值取代被删除结点的值，然后删除此后继结点，由于被删除的后继结点的左子树一定是空子树，所以删除后继结点的过程同情况二。,方法二：用被删除结点在中序遍历序列中的直接前驱结点（该结点的右子树也一定为空）代替被删除的结点，然后删除这个前驱结点。,后继结点,前驱结点, 将结点50删除,中序遍历结点序列：10 15 30 33 35 37 50 53 55 62,用中序遍历该二叉树得到的直接后继结点代替该结点，删除直接后继结点,用中序遍历该二叉树得到的直接前驱结点代替该结点，删除直接前

11、驱结点, 查找操作：,查找思路：,当二叉排序树不为空时，将给定值与根结点的值进行比较，若相等则查找成功。如果给定值小于根结点的值，则在根结点的左子树中继续查找，否则在根结点的右子树中继续查找。当待查找的二叉排序树为空时，查找失败。,平均查找长度：,在二叉排序树中查找成功时走过的是一条从根结点到所寻找结点的一条路径，因此，二叉排序树查找的平均查找长度取决于二叉排序树的深度。,在二叉排序树中查找关键字值等于50,35,90,95,平均查找长度：, 二叉排序树的蜕变：,例如，由整数序列15,23,26,47,56,89 生成的二叉排序树,47,56,89,15,23,26,平均查找长度与顺序查找相同

12、,当把一组有序值依次插入到一棵二叉排序树时，生成的二叉排序树将蜕变成一棵单支树。,哈希查找,U,K,T,0 1 2 . . . m-1,哈希方法：使用函数将U映射到表T0m-1 的下标上 哈希函数: h(关键值) 元素存储地址,所有可能出现的关键字集合U,实际存储关键字集合K,哈希表,如果哈希函数是一一映射的，那么增、删、改、查的复杂度都是O(1)的。 如果关键字的可能值太多，而数组长度是有限的，那么哈希函数就只能是多对一的，就会产生碰撞。,哈希存储(哈希表),哈希存储(哈希表)： 以数据元素的关键字k为自变量，通过一定的函数关系计算出对应的函数值h(k)，把这个值解释为数据元素的存储地址并把

13、数据元素存储到相应的存储单元内（这个过程称为哈希）。h(k)称为哈希地址。 例：设有一组关键字值85, 72, 49, 58, 15, 70, 90, 38， 哈希函数 h(k) = k mod 12。则对应的哈希地址为： 1, 0, 1, 10, 3, 10, 6, 2 冲突： 若有两个不同的关键字ki和kj，即ki kj（i j）。 但h(ki) = h(kj)，这种情况称为冲突。 ki与kj 称为同义词。, 采用哈希技术要解决的两个主要问题：,构造一个好的哈希函数，使出现冲突的机会尽可能少些；,设计一个有效的解决冲突的办法,哈希表,碰撞的解决方法： 开放地址法：如果一个元素该在的位置已经

14、有其他元素，就另安排一个空闲位置。 链地址法：映射到同一位置的元素被串成链表。,解决冲突的方法：开放地址法和链地址法,开放地址法：处理用数组存储哈希表时出现的冲突,发生冲突时按某种规则形成一个地址探查序列 按序列顺序逐个检查各地址单元，直至找到一个未被占用的单元为止 将发生冲突的数据元素存入该地址单元中。,线性探查序列,平方探查序列,设哈希表的长度是m，发生冲突的地址是d,d+1, d+2, , m-1, 0, 1, , d-1,(d+12)%m, (d-12)%m, (d+22)%m, (d-22)%m, ,两种常用的地址探查方法：,设哈希表的长度11，哈希函数是h(k) = k % 11，

15、将整数序列54,77,94,89,14,45,76存入哈希表。按线性探查法处理冲突,例1,0,1,2,3,4,6,7,8,9,10,54,77,94,89,54 % 11 = 10,77 % 11 = 0,94 % 11 = 6,89 % 11 = 1,14 % 11 = 3,45 % 11 = 1 (冲突),76 % 11 = 10 (冲突),14,45,76,线性探查法建立哈希表,5,线性探查地址序列,d+1, d+2, , m-1, 0, 1, , d-1,等概率时查找成功的平均查找长度： ASL=（1+1+1+1+1+2+6）/ 7=13/7,设哈希表的长度11，哈希函数是h(k) =

16、 k % 11，将整数序列54,77,94,89,14,45,76存入哈希表。按平方探查法处理冲突,例2,0,1,2,3,4,5,6,7,8,9,10,54,77,94,89,54 % 11 = 10,77 % 11 = 0,94 % 11 = 6,89 % 11 = 1,14 % 11 = 3,45 % 11 = 1 (冲突),76 % 11 = 10 (冲突),14,45,76,平方探查法建立哈希表,(d+12)%m, (d-12)%m, (d+22)%m, (d-22)%m, ,平方探查地址序列：,将所有哈希地址相同的记录都链接在同一单链表中。 哈希表中的每个存储单元中不再存放数据元素而

17、是存放相应单链表的头指针. 例:给定关键字19, 1, 23, 14, 55, 68, 11, 82, 36 哈希函数为 H(key) = key % 7,链地址法,例:给定关键字 19, 1, 23, 14, 55, 68, 11, 82, 36 哈希函数为 H(key) = key % 7,链地址法,哈希查找,哈希表的查找过程和建表的过程相似，按哈希存储 的方法进行查找。 假设给定的关键字为k: 根据建表时构造的哈希函数h，计算出哈希地址h(k)，如果哈希表中该地址单元为空，则查找失败。 否则，将该地址中记录的关键字与给定值比较，如果相等，则查找成功；如果不等，则按建表时设定的处理冲突方法

18、查找下一个地址。如此反复下去，直到某个地址单元为空（查找失败）或者关键字比较相等（查找成功）为止。,排序的基本概念,排序：将文件中的记录按排序码非递减(或非递增)的顺序重新排列。 排序码：数据元素中的一个或多个数据项。排序码可以是关键字，也可以是其他若干数据项的组合。 排序算法的稳定性：如果在待排序的元素序列中，存在着多个排序码相同的元素，按照某种排序算法排序后，这些元素的相对位置仍保持不变，则称该排序算法是稳定的，否则就是不稳定的。 待排序数据：18 12 10 12 30 16 排序后数据：10 12 12 16 18 30 稳定 排序后数据：10 12 12 16 18 30 不稳定,插

19、入排序,基本思想：把元素ei(0in) 依次插入到由S中前i个元素组成的已经排好序的序列e0, e1, ,ei-1的适当位置上，插入后S的前i+1个元素仍为有序。,直接插入排序,以顺序查找的办法找到要插入的元素在已排好序的元素序列中应处的位置。 所有元素分成两个集合：已排序记录集和待排序记录集。初始时，已排序记录集只有一个元素，即e0，待排序记录集是所有剩余元素。然后每次从待排序记录集中选取一个元素，使用顺序查找的方法，找到其在已排序记录集中的位置，将其插入到该位置，直到待排序记录集为空。,直接插入排序,把n个元素的序列划分为两个子序列：一个为有序；另一个为无序 将无序子序列中的元素依次取出插

20、入到有序子序列中，直到无序子 序列为空，整个排序结束。 若待排序数据元素的排序码序列是（18，12，10，12，30，16）,直接插入排序,例：,待排序记录为50,20,75,34,40,34,40,75,20,50,直接插入排序, 直接插入排序的函数模板示例：,template void InsertionSort(T A, int n)/对A0An-1排序 int i , j; T temp; for( i = 1 ; i 0 ,算法分析,时间复杂度与元素的初始状态有关 初态为正序时（最好情形）复杂度为O(n) 初态为逆序时（最坏情形）复杂度是O(n2) 直接插入排序的平均时间复杂度是O(

21、n2) 直接插入排序是稳定的排序算法 适用于一个长度较短、接近有序的序列,34,40,75,20,50,50,40,20,75,34,二分插入排序,在插入ei时，e0, e1, , ei-1是一个有序序 列，所以可以用二分查找法寻找ei的插入 位置，从而减少比较次数。 二分插入排序是稳定的排序算法，其平均 时间复杂度仍是O(n2), 二分插入排序的函数模板示例：,选择排序,基本思想：每次从待排序的元素序列中选择一个最小的元素将其附加到已排好序的元素序列的后面，直至全部元素排好序为止。 在初始时，已排好序的元素序列为空，待排序的元素序列中包括了需要排序的所有元素。,直接选择排序,基本思想：用逐个

22、比较的办法从待排序的元素序列中选出最小的元素。依次对i=0, 1, 2, ,n-2分别执行如下的选择和交换步骤：在元素序列ei, ei+1, , en-1中选择出最小的元素ek；当ki时，交换ei与ek的值。经上述n-1次的选择和交换后，排序工作即已完成。,直接选择排序,用逐个比较的办法从待排序的元素序列中选出最小的元素。,直接选择排序,第1步：在n个数据元素中找出排序码最小的数据 元素，与第1个元素交换 第2步：在n-1个数据元素中找出排序码最小的数 据元素，与第2个元素交换 第i步：在n-i+1个数据元素中找出排序码最小的 数据元素，与第i元素交换,未排序,已排序,直接选择排序,直接选择排

23、序函数模板：,直接选择排序算法是不稳定算法，其平均时间复杂度为O(n2)，时间复杂度与元素的初态无关,冒泡排序,基本思想： 从待排序记录集的一端（这里假定为低端）对相邻的两个元素（e0和e1，e1和e2，en-2和en-1）依次比较它们的排序码，若不符合排序的顺序要求，就将相应的两个元素互换，此过程称为一趟冒泡排序，最多经过n-1趟冒泡排序，排序工作即可完成。 每趟排序的结果是将待排序记录集中排序码最大的元素交换到待排序记录集最后一个元素的位置。假设在一趟冒泡排序时，从ej+1以后没有发生元素的互换，则说明ej+1以后的元素是已经排好序的，下面只需要在e0到ej范围内进行新一趟的冒泡排序，即待

24、排序记录集是从e0到ej，下一趟只需从e0到ej范围内进行。,冒泡排序（交换排序）,冒泡排序,第一趟,第三趟,第四趟,第二趟,第五趟,第六趟,初始状态,#include void main() int a10; for(int i= 0 ; i ai; int temp; for(i = 0 ; i aj+1) temp = aj; aj = aj+1; aj+1= temp; ,#include void main() int a10; for(int i = 0; i ai; bool change = true; int temp; for(i = 0 ; i aj+1) temp =

25、aj; aj = aj+1; aj+1 = temp; change = true; /标志置为真,有交换 ,算法分析,时间复杂度与元素的初始状态有关。 最好情况下的时间复杂度为O(n)。若待排序元素序列已经有序，则排序工作经一趟处理就可结束。此时，对元素排序码的比较次数为最小值n-1，且没有元素的互换。 最坏情况下的时间复杂度为O(n2)。若待排序元素序列为逆序，则需要进行n-1趟冒泡。每趟要进行n-i-1次排序码的比较和n-i-1次元素的互换。 平均时间复杂度为O(n2)。 冒泡排序算法是稳定的。,第一趟排序结束,第二趟排序结束,第三趟排序结束,LastExchangeIndex,冒泡排序函数模板：,快速排序,基本思想： 从待排序的个元素中任取一个元素，以该元素为基准，用交换的方法将剩下的元