第三章查找与排序技术.ppt

1、1,第三章 查找与排序技术,3.1 基本查找技术 查找：在一个给定的数据结构中查找某个指定的元素。 通常，根据不同的数据结构，应该采用不同的查找方法： 顺序查找； 有序表的对分查找； 分块查找。,2,3.1.1 顺序查找,顺序查找（顺序搜索）：在线性表中顺序查找指定的元素。 顺序查找的基本方法：从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若有相等则表示找到（查找成功）；若线性表中的所有元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找到的元素（查找失败）。,3,举例说明,举例：设A是n个元素的一维数组。对于指定的输入x，如果x在数组中，则顺序找到它第一次出现处的

2、下标； 如果x在数组中，则以下标作为查找结果。否则以-1作为结果,4,#define n 5 /* n为查找表中元素个数的最大可能值*/ #define MAXLEN n+1 int seqsearch(int A,int k) int i; i=0; AMAXLEN-1=k; while (Ai!=k) i+; if(iMAXLEN-1) return i; /*查找成功，返回被查元素在表中的相对位置*/ else return -1; /*查找失败，返回-1*/ ,使用了监视哨，在查找过程中，不用每一步都去判断是否查找结束。 找到：返回元素在线性表中的存储位置； 未找到：返回-1。,5,#

3、include stdio.h void main() int j,a=11,21,2,45,90,h=8; j=seqsearch(a,h); printf(%d,j); ,6,顺序查找的效率,如果线性表中的第一个元素就是被查找元素，只需要做一次比较就查找成功； 如果被查的元素是线性表中的最后一个元素，或者被查元素根本不在线性表中，则需要与线性表中的所有元素进行比较（最坏情况）； 平均情况：利用顺序查找法在线性表中查找一个元素，大约要与线性表中一半的元素进行比较。,7,结论,对于大的线性表来说，顺序查找的效率是很低的。但在下列两种情况下也只能采用顺序查找： 如果线性表为无序表（表中元素的排列

4、是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找表； 即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。,8,3.1.2 有序表的对分查找,有序表：线性表中的元素按值非递减或者非递增排列。 对分查找的过程：将被查找关键字与线性表中间的项目进行比较，有三种可能： 若被查关键字与表中间的项目相等，则查到，过程结束； 若被查关键字大于表中间的项目，则取表的后半部分作为新表再去查找； 若被查关键字小于表中间的项目，则取表的前半部分作为新表再去查找。,查找成功！,在后半部分查找！,在前半部分查找！,减半递推！,9,时间效率分析,对分查找是根据每次试探的结果将线性表的规模减半，并

5、有规则地括出可能包含被查项目的部分。 最坏情况：对查找需要的比较次数为 n为线性表的长度。 局限性：只适用于有序表，且只限于顺序存储结构。,10,#define n 6 /* n为查找表中元素个数的最大可能值*/ #define MAXLEN n int binsearch(int A, int k) int low,mid,high; low=0;high=MAXLEN-1; while (lowAmid) low=mid+1; else high=mid-1; return -1;/*查找失败，返回-1*/ ,11,#include stdio.h void main() int j,a=

6、2,11,21,45,77,90,h=90; j=binsearch(a,h); printf(%d,j); ,12,3.1.3 分块查找,分块查找又称索引查找，是顺序查找的一种改进方法，用于在“分块有序”表中进行查找。 “分块有序”表：将长度为n的线性表L分成m个子表（各子表的长度可以不等，也可以相等），且后一个子表中的每一项均大于前一个子表中的所有项。,13,分块有序表,分块有序表的结构可以分为两部分： (1)线性表本身采用顺序存储结构也可以采用链式存储结构。 (2)再建立一个索引表。在索引表中，对线性表的每个子表建立一个索引结点，每个结点包括两个域：一是数据域，用于存放对应子表中的最大元

7、素值；二是指针域，用于指示对应子表的第一个元素在整个线性表中的序号或者地址。,14,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18,15,分析,根据分块有序表的结构，其查找过程可以分以下两步进行： (1)首先查找索引表，以便确定被查元素所在的子表。由于索引表数据域中的数据是有序的且顺序存储，因此可以采用对分查找。 (2)然后在相应的子表中用顺序查找法进行具体的查找。 结论：分块查找的效率介于对分查找和顺序查找之间。,16,3.2 哈希表技术,17,传统的查找方法,查找：50,比较,思考：有没有不需要比较就可以找到的方法？,理想的查找是不经过任何比较，一

8、次存取便能得到所查记录,18,一种新的想法,查找：50 A【5】 查找：40 A【4】,需要一种函数，使得 F（50）5 该函数为： F（x）x div 10,当我们需要查找30时， 先计算：f（30)3 再直接从A【3中取出该记录,哈希 函数,哈希 表,19,哈希查找，也称为散列查找。 它既是一种查找方法，又是一种存贮方法，称为散列存贮。散列存贮的内存存放形式也称为哈希表或散列表。,20,哈希查找是通过构造哈希函数来得到待查关键字的地址，从理论上来说是一种不需要用到比较的一种查找方法。,21,3.2.1 哈希表的基本概念,1. 直接查找技术 设表的长度为n。如果存在一个函数ii(k)，对于表

9、中的任意一个元素的关键字k，满足以下条件：(1)函数值i的范围为：1in；(2)对于任意的元素关键字k1k2，恒存在i(k1)i(k2)。 则称此表为直接查找表。 其中函数ii(k)称为关键字k的映象函数。,22,直接查找技术,直接查找表中各元素的关键字k与表项序号i之间存在着一一对应的关系； 对直接查找表的查找，只需要根据映像函数i=i(k)计算出待查关键字项目在表中的序号i即可。,23,2. Hash表,Hash表技术是直接查找技术的推广，其主要目标是提高查找效率。 直接查找技术要求映像函数能使得表中任意两个不同的关键字其映像函数值也不同（不允许元素冲突的存在）；但在实际应用中，这一条件很

10、难满足。 对于两个不同的关键字k1 k2有i(k1)=i(k2)，发生了元素冲突，即两个不同元素需要存在在同一个存储单元中。,24,举例,例3.2 将关键字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入长度为n12的表中。映象函数为iINT(k/3)1。,25,分析,显然，当有元素发生冲突时，是无法进行直接查找的。所以引入Hash表的概念： 设表的长度为n。若存在一个映象函数i=i(k)，对于表中任一元素的关键字k，满足1 i(k) n ，则称此表为Hash表。并称i(k)为关键字k的Hash码。 Hash表中允许冲突存在。如果在Hash表中没有冲突存在

11、，则Hash表就成为直接查找表。,26,处理表中元素的主要工作：(1)构造合适的Hash码，以便尽量减少表中元素冲突的次数。(2)当表中元素发生冲突时，要进行适当的处理。,3. Hash码的构造 查找关键字为k的元素时，计算Hash码i(k)的工作量是影响效率的重要因素。 在实际构造Hash码时，要考虑如下两方面的因素： (1)使各关键字尽可能均匀地分布在Hash表中，即Hash码的均匀性要好，以便减少冲突发生的机会。 (2)Hash码的计算要尽量简单。,27,一些简单的Hash码构造方法,截段法 分段叠加法 除法 乘法,28, 截段法 截取法：选取与关键字对应的数字串中的一段（一般选取低位数

12、）作为关键字的Hash码。 分段叠加法 将关键字的编码串分割成若干段，然后把它们叠加后再进行截段。两种叠加处理的方法： 移位叠加：将分割后的几部分低位对齐相加； 间界叠加：从一端沿分割界来回折送，然后对齐相加。 此法适于关键字的数字位数特别多的情况。,29,有80个记录，关键字为8位十进制数，哈希地址为2位十进制数。,分析： 只取8 只取1 只取3、4 只取2、7、5 数字分布近乎随机 所以：取任意两位或两位 与另两位的叠加作哈希地址, 截段法：选取与关键字对应的数字串中的一段（一般选取低位数）作为关键字的Hash码。,30,举例: 关键字为 0442205864，哈希地址位数为4, 分段叠加

13、法 将关键字分割成若干段，然后把它们叠加后再进行截段。两种叠加处理的方法： 移位叠加：将分割后的几部分低位对齐相加； 间界叠加：从一端沿分割界来回折送，然后对齐相加。,31, 除法 imod(k，n) 其中k为关键字，n为Hash表的长度，而mod为求余运算符； 当mod(k，n)=0时，取i=n（本节规定）。 乘法 imod(k*，n)一般取0.618033988747，或0.6125423371，或0.6161616161。,32,3.2.2 几种常用的Hash表,1. 线性Hash表 线性表是一种最简单的Hash表。 设线性Hash表的长度为m，则对线性Hash表的查找过程如下：,33,

14、线性Hash表的填入 将关键字k及有关信息填入线性Hash表的步骤如下： 1)计算关键字k的Hash码ii(k)。 2)检查表中第i项的内容： 若第i项为空，则将关键字k及有关信息填入该项； 若第i项不空，则令imod(i1，n)，转2)继续检查。 只要Hash表尚未填满，最终总可以找到一个空项，将关键字k及有关信息填入到Hash表中。,34, 线性Hash表的取出 要在线性Hash表中取出关键字k的元素，其步骤如下： 1)计算关键字k的Hash码ii(k)。 2)检查表中第i项的内容： 若第i项登记着关键字k，则取出该项元素即可； 若第i项为空，则表示在Hash表中没有该关键字的信息； 若第

15、i项不空，且登记的不是关键字k，则令imod(i1，n)转2)继续检查。,35,例3.3 将关键字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入长度为n12的线性Hash表中。 设Hash码为iINT(k/3)1。,表3.2 线性Hash表,36,分析,线性表的优点：简单。 线性Hash表的缺点： 在线性Hash表填入的过程中，当发生冲突时，首先考虑的是下一项，因此，当Hash码的冲突较多时，在线性Hash表中会存在“堆聚”现象，即许多关键字被连续登记在一起，从而会降低查找效率。 在线性Hash表的填入过程中，处理冲突时会带来新的冲突。线性Hash表的填

16、入方法是不顾后效的。,37,在Hash表填入过程中不顾后效，从而在填入过程中其冲突的机会在不断增多； 当Hash表填满时，不能正常地进行查找。 解决方法：将冲突的元素安排在另外的空间内，而不占用Hash表本身的空间，则就不会产生新的冲突。,38,3. 溢出Hash表,溢出Hash表包括Hash表和溢出表两部分。 在Hash表的填入过程中，将冲突的元素顺序填入溢出表，而当查找过程中发现冲突时，就在溢出表中进行顺序查找。 溢出表是一个顺序查找表。,39,溢出Hash表的填入,将关键字k及有关信息填入溢出Hash表的步骤如下： 1)计算关键字k的Hash码ii(k)。 2)检查表中第i项的内容：若第

17、i项为空，则将关键字k及有关信息填入该项；若第i项不空，则将关键字k及有关信息依次填入溢出表中的自由项。,40,溢出Hash表的取出,要在溢出Hash表中取出关键字k的元素，其步骤如下： 1)计算关键字k的Hash码ii(k)。 2)检查表中第i项的内容：若第i项登记着关键字k，则取出该项元素即可；若第i项为空，则表示在Hash表中没有该关键字信息；若第i项不空，且登记的不是关键字k，则转入在溢出表中进行顺序查找。,41,例3.5 将关键字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入长度为n12的溢出Hash表中。 设Hash码为iINT(k/3)1。

18、,表3.4 Hash表和其溢出表,42,3.3 基本排序技术,排序：将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。,43,3.3.1 冒泡排序与快速排序（互换排序）,定义：所谓互换排序是指借助数据元素之间的互换进行排序的一种方法。 冒泡排序（Bubble Sort）是一种最简单的互换排序，它是通过相邻两项目的比较，按一定次序互换，使表格逐步达到有序化。 快速排序（Quick Sort）是对冒泡排序的一种改进。,44,1. 冒泡排序,基本思想： 首先对具有n个项目的无序表进行扫描，比较相邻两个元素的大小，若发现逆序则进行互换，由此可以使n个项目中的最大者沉到表的最后； 然

19、后对剩下的未排序好的项目再进行扫描，使它们之中的最大者又沉到表的最后； 以此类推，直到将表全部排序好为止。,45,将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r1.keyr2.key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上,冒泡排序,46,对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置 重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止,冒泡排序,47,#include ”stdio.h” void main( ) in

20、t a10,i,j,temp; printf(”Input l0 integer numbers:”); for(i=0;iaj+1) temp=aj; aj=aj+1; aj+1=temp; for(i=0;i10;i+) printf(”%d”,ai); ,48,2. 快速排序,在冒泡排序中，每经过一次数据元素的互换只能移掉一个逆序。 如果在排序过程中，每经过一次比较，使元素移动不止一个位置，这就有可能同时移掉多个逆序，达到加速排序的目的。 基本思想：通过一趟分割将线性表分成两部分，其中前一部分的所有元素值均不大于后一部分中的每一个元素值；然后对每一部分再进行分割，直到整个线性表有序为止。

21、,49,具体做法,从线性表中选取一个元素，设为T。然后将线性表后面小于T的元素移到前面，而前面大于T的元素移动到后面，结果就将线性表分成了两部分（两个子表），而T插入到其分界线的位置处。该过程被称为线性表的分割。 对分割后的各子表再按上述原则进行分割，直到所有子表为空为止，则此时的线性表就变成了有序表。,50,首先，在表的第一个、中间一个与最后一个元素中选取中项，设为L(k)，并将L(k)赋给T，再将表中的第一个元素与L(k)交换。 然后设置两个指针i和j分别指向表的起始与最后的位置。反复作以下两步： (1)将j逐渐减小，并逐次比较L(j)与T，直到发现一个L(j)T为止，将L(j)移到L(i

22、)的位置上。 (2)将i逐渐增大，并逐次比较L(i)与T，直到发现一个L(i)T为止，将L(i)移到L(j)的位置上。 上述两个操作交替进行，直到指针i与j指向同一个位置（即ij）为止。,51,快速排序的过程,52,完成一趟排序： ( 27 38 13) 49 (76 97 65 50),分别进行快速排序： ( 13) 27 （38) 49 (50 65) 76 (97),快速排序结束： 13 27 38 49 50 65 76 97,49,27,49,65,13,49,49,97,53,3.3.2 简单插入排序与希尔排序,基本思想：依次将线性表中的每一个元素插入到一个已经有序的子表中。 方法

23、： 将线性表中，只包含第1个元素的子表显然可以看成是有序表； 从线性表的第2个元素开始直到最后一个元素，逐次将其中的每一个元素插入到前面已经有序的子表中； 一般来说，假设线性表中前j-1个元素已经有序，现在要将线性表中第j个元素插入到前面的有序子表中。,54,有序,1. 简单插入排序,55,演示,有序,56,例,49 38 65 97 76 13 27,i=2 38 (38 49) 65 97 76 13 27,i=3 65 (38 49 65) 97 76 13 27,i=4 97 (38 49 65 97) 76 13 27,i=5 76 (38 49 65 76 97) 13 27,i=6 13 (13 38 49 65 76 97) 27,i=1 ( ),i=7 (13 38 49 65 76 97) 27,27,97,76,65,49,38,27,57,void insort(