查找与排序课件

《查找与排序课件》由会员分享，可在线阅读，更多相关《查找与排序课件（55页珍藏版）》请在金锄头文库上搜索。

1、1.4 查找和排序,居太亮，2007年9月 电子科技大学通信学院,查找与排序,查找：,从大量数据中找出所需要的数据。,排序：,将一组记录根据要求按递增或者递减顺序排列，以方便我们对数据进行处理。,一、查找,关键字：元素的标志，唯一标识一个数据元素。 查找：查找一个关键字等于给定值的数据元素，即按关键字查找。 查找表：待查数据元素的集合。 查找方法：顺序查找、折半查找、分块查找、哈希查找等。 查找效率：与查找表中数据元素的组织形式以及使用的查找方法密切相关。 评价依据：最多、最少和平均比较次数。,基本思想：从线性表的第一个数据元素开始查找，依次将线性表中的元素与被查找元素进行比较，若相等则查找成

2、功；若直到线性表结束都未找到被查找元素则查找失败。 应用：无序表，无论顺序存储还是链接存储，都只能用顺序查找；有序表链接存储也只能用顺序查找。 比较次数：最少1次；最多n次。,1、顺序查找,/*在长度为length的顺序表中顺序查找关键字等于key的元素，若找到，返回元素索引号，否则，返回-1*/,int seq_search(int table , int length, int key) int i = 0; while(tablei != key ,顺序查找的平均查找长度：,基本思想：在有序表中查找！ 1）先确定待查记录所在的范围 2）逐步缩小范围直到查找成功或失败,给定的key与km比

3、较：keykm,取mid+1, high依此类推,mid = (low+high) / 2,2、折半查找（二分查找）,mid = ( low + high ) / 2; if ( 中间值 key ) high = mid - 1; else if (中间值 = key ) 找到; else low = mid + 1;,重复此过程，直到找到或找不到为止,int binary_search( int list, int length, int key ) int low, high, mid; low = 0;high = length 1; while ( low key) high = mi

4、d-1; else low = mid + 1; return(-1); ,/*在长度为length的顺序表中折半查找关键字等于key的元素，若找到，返回元素索引号，否则，返回-1*/,折半查找的平均查找长度：,优点： 比较次数少、查找速度快 适用场合： 顺序存储结构的有序查找表,又称索引表的顺序查找索引顺序查找 基本思想： 1）对数据元素分块，块内无序，块间有序 2）建立一个索引表，为每个块建立一个索引项，指出该块内的最大（或最小）关键字以及该块中第一个数据元素在表中的位置 索引表按关键字有序 3）查找时，先查索引表确定待查元素所在的块，再在块内顺序查找。,3、分块查找,例： 17, 23,

5、 15, 9, 21, 28, 34, 40, 54, 25, 90, 60, 72, 58, 86,4、树表查找（动态查找）,用二叉排序树存储查找表中的数据元素 基本思想：利用二叉排序树查找 1）将给定的key先与根结点比较，若相等则查找成功； 2）若给定的key根结点，则与左子树根结点比较，反之与右子树根结点比较。递归进行直到查找成功或失败。 平均查找长度取决于二叉排序树的深度 最好 log2n1 最坏 (n + 1)/2,又称散列查找 根据关键字，进行运算，直接取得元素存储位置,关键字空间,地址空间,不需任何比较就可直接取得所查元素,平均查找效率：1,5、哈希查找,哈希造表（散列）要解决

6、的关键问题： 构造一个哈希函数。 进行冲突处理，使不同的关键字对应不同的存储位置。,哈希函数常用的构造方法： 直接定址法：取关键字或取关键字的某个线性函数值为哈希地址。 即：hashk= k 或 hashk= ak+b,地址集合等于关键字集合，不会发生冲突 实际中很少应用,截段法：从关键字中截取一段作为哈希地址 例：关键字为学号，可从关键字中截取后三位作为元素在表格中的存放位置（哈希地址）。,平方取中法： 关键字平方后取中间几位为哈希地址。取的位数由表长决定。,例：关键字key: 11052501 11052502 01110525 02110525 表长m = 1000 则：11052501

7、 平方后等于122157778355001，取中间三位778为哈希地址。,除留余数法： 选择数n哈希表长m，取关键字被数 n 除后所得余数为哈希地址， hashk = k mod n, n m 最简单、最常用,折叠法： 将关键字分割成位数相同的几部分（最后一部分位数可不同），然后取这几部分的叠加和为哈希地址。,冲突处理： 冲突：指不同的关键字映射到同一地址，即： hash(key1)=hash(key2) 冲突处理：为发生冲突的关键字找到另一个空闲的哈希地址。,地址冲突,hash(k1)=hash(k2),hash(k3)=hash(k6)=hash(k8),常用的冲突处理方法： 链地址法：（

8、链表结构） 将所有哈希地址相同的元素用链表连接起来,ASL = (5+2*2+3)/8 = 1.5,开放地址法： 当哈希地址冲突时，按某个序列改变地址，直到在哈希表中找到一个空闲地址为止。 hashi(k)=(hash(k) + di) mod m,关键字k的直接哈希地址,探测时的地址增量,哈希表的长度,di可有不同的取法，如： di= 1，2，3，4，5，di= -1，-2，-3，-4，-5，,哈希查找时，当发现当前hash地址里存放的不是所需元素，就按照构造哈希表时选取的序列改变地址，逐个探测，直到找到所需元素。,例：对di=1，2，3，4， 序列,存放过程： index = hash(k

9、ey); while ( table-dataindex != empty ) index +；,查找过程： index = hash(key); while( table-dataindex-key != key) index +;,例：一组关键字与其对应的哈希地址如下所示：key:ab cd ef de hi gh mlhash(key): 4 6 1 4 7 6 5选取序列di= -1，-2，-3，-4， 构造哈希表,构造过程：,de与ab冲突，地址减一，探测,gh与cd冲突，地址减一，探测,ASL = (4+2*2+4)/7 = 12/7,二、排 序,排序：又称分类，是将一组元素按照它

10、们的排序码大小进行递增或递减排列的运算方法。,排序码：排序的依据，不一定是关键字，是元素中的一个或多个字段，不同元素排序码可以相同。,排序算法的稳定性： 对具有相同排序码的元素，若排序后元素的相对位置保持不变，则算法是稳定的。否则，算法不稳定。 算法是否稳定有时与具体实现有关！,内部排序：整个排序过程在计算机内存中进行； 外部排序：既使用内存，同时又使用外存的排序。,衡量排序算法的效率： 对内部排序：开销在元素的比较和移动上； 对外部排序：开销不仅在元素的比较和移动上，更多的开销在对外存的访问上。,基本思想：不断在待排序序列（无序区）中按排序码递增（或递减）依次选择记录，放入有序区中，逐渐扩大

11、有序区，直到整个记录均有序为止。,过程： 直接在原表中操作：从表中选出最小的元素与表首元素互换，再从剩下的表中选出最小的元素与第二个元素互换，依此类推。,1、简单选择排序,设有序列： 5, 4, 12, 20, 27, 3, 1 排序过程为：,结果： 1，3，4，5，12，20，27 ,算法描述： 先在无序表中找到最小元素最小元素与无序表表首元素交换位置无序表：i+1， ，n 有序表：1， ，i,/*在无序表中找最小元素的算法：*/ small=i;j=i+1;while(jlistj) small=j;j+; ,/*small为最小元素的下标*/,void straight_select_s

12、ort(int list, int n) int i, j, small; for(i=0; ilistj) small=j; if(small!=i)temp=listsmall; listsmall=listi; listi=temp; ,/*需n-1趟选择排序*/,/*最小元素与无序表中第一个元素互换位置*/,算法分析,算法由两层循环构成，外层循环表示共需进行n-1趟排序，内层循环表示每进行一趟排序需要进行的记录排序字间的比较。 比较次数：n(n-1)/2 移动次数：最坏情况下为3(n-1) 所以总的时间复杂度为：O(n2) 空间复杂度为：O(1) 交换记录用,稳定性：不稳定,基本思想：

13、从原表中取一个元素插入到已排好序的表中，得到一个新的、元素个数增1的有序表。,算法描述： 将原表分为已排序表和未排序表： 已排序表：R1 R2 Ri-1未排序表：Ri Ri+1 Rn 每次从未排序表中取出表头元素按排序关系插入到排序表中；当未排序表为空时，排序结束。 需进行（n-1）趟插入排序,2、直接插入排序,插入运算为从后向前比较：先取Ri与Ri-1比较，若RiRi-1，则Ri-1后移一个位置，再取下一个元素Ri-2与Ri比较，依此类推，直到找到 插入位置，就在该位置插入元素。,void linear_insert_sort(int list, int n) int i, j, temp;

14、 for(i=1; i= 0) listj+1=listj; j-; listj+1=temp; ,/*从第二个元素开始，每循环一次插入一个元素*/,例：待排序列： 54 34 17 28 63 92 48 82 75,n-1趟排序依次为：,初始状态：54 34 17 28 63 92 48 82 75,(i=1,34) 34 54 17 28 63 92 48 82 75,(i=2,17)17 34 54 28 63 92 48 82 75,(i=3,28)17 28 34 54 63 92 48 82 75,(i=4,63)17 28 34 54 63 92 48 82 75,(i=5,9

15、2)17 28 34 54 63 92 48 82 75,(i=6,48)17 28 34 48 54 63 92 82 75,(i=7,82)17 28 34 48 54 63 82 92 75,(i=8,75)17 28 34 48 54 63 75 82 92,算法特点： 简单，容易实现，适于待排元素n 很少或基本有序的情况。,排序效率： 共进行n-1次循环排序，每次可能搬移多个元素。 最好情况：比较次数n-1；移动次数2(n-1) 最坏情况：比较n(n-1)/2；移动 平均：约n2/4 O(n2),稳定性：稳定,基本思想： 从表首元素开始，两两比较，若 RiRi+1 ，则两个元素交换。

16、经过一趟冒泡排序后，具有最大排序码的数据元素就移到了最后，而具有小排序码的数据元素则像气泡一样逐渐上浮； 再对前n-1个数据元素冒泡排序，依此类推，直到在一趟冒泡排序过程中没有进行过交换元素的操作，整个排序过程结束。,3、冒泡排序（bubble sort）,冒泡排序例： 初始状态65 97 76 13 27 49 58 第1趟(j=1 6)65 76 13 27 49 58 97 第2趟(j=1 5)65 13 27 49 58 76 97 第3趟(j=1 4)13 27 49 58 65 76 97 第4趟(j=1 3)13 27 49 58 65 76 97 第5趟(j=1 2)13 27 49 58 65 76 97 第6趟(j=1)13 27 49 58 65 76 97,算法描述： 1）逐个比