《数据库三级第六讲课件》由会员分享，可在线阅读，更多相关《数据库三级第六讲课件（39页珍藏版）》请在金锄头文库上搜索。
1、第六讲第六讲 查找与排序查找与排序数据库三级第六讲查找：查找是在一个给定的数据结构中，查找：查找是在一个给定的数据结构中，根据根据给定的条件查找满足条件的结点给定的条件查找满足条件的结点。不同。不同的数据结构采用不同的查找方法。查找的数据结构采用不同的查找方法。查找的效率直接影响数据处理的效率。的效率直接影响数据处理的效率。查找的结果：查找的结果：查找成功：查找成功：找到满足条件的结点找到满足条件的结点查找失败：查找失败：找不到满足条件的结点。找不到满足条件的结点。可以采用从前向后查，也可采用从后向前查的方法。可以采用从前向后查，也可采用从后向前查的方法。在在平平均均情情况况下下，大大约约要要
2、与与表表中中一一半半以以上上元元素素进进行行比比较较，效率较低。平均查找长度较大。效率较低。平均查找长度较大。查找过程：查找过程： 对对给给定定的的一一关关键键字字K，从从线线性性表表的的一一端端开开始始，逐逐个个进进行行记记录录的的关关键键字字和和K的的比比较较，直直到到找找到到关关键键字字等等于于K的记录或到达表的另一端。的记录或到达表的另一端。6.1 6.1 顺序查找顺序查找0 1 2 3 4 5 6 7（a） 初态初态40803060102025(b) K=80(return i=4)80408030601020250 1 2 3 4 5 6 7(c) K=90(return i=0
3、)0 1 2 3 4 5 6 79040803060102025监视哨监视哨使使用用了了监监视视哨哨，在在查查找找过过程程中中，不不用用每每一一步步都都去去判判断断是是否否查查找找结结束。束。找找到到：返返回回元元素素在在线线性性表表中中的的存存储位置；储位置；未找到：返回未找到：返回0。思思想想：先先确确定定待待查查找找记记录录所所在在的的范范围围，然然后后逐逐步步缩缩小小范围，直到找到或确认找不到该记录为止。范围，直到找到或确认找不到该记录为止。前提：必须在前提：必须在具有顺序存储结构的具有顺序存储结构的有序表中进行有序表中进行。分三种情况：分三种情况：1 1）若中间项的值等于）若中间项的
4、值等于x,x,则说明已查到。则说明已查到。2 2）若）若x x小于中间项的值，则在线性表的前半部分查找；小于中间项的值，则在线性表的前半部分查找；3 3）若）若x x大于中间项的值，则在线性表的后半部分查找。大于中间项的值，则在线性表的后半部分查找。6.2 6.2 折半查找（二分法查找）折半查找（二分法查找）查找查找23和和79的过程如下图：的过程如下图：mid=(low+high)/2不进位取整不进位取整( 08, 14, 23, 37, 46, 55, 68, 79, 91 )( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid( 08, 14,
5、 23, 37, 46, 55, 68, 79, 91 )lowhigh=mid-1mid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )low=mid+1highmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid 基本思想基本思想: 首先在所有记录中选出关键字最小的首先在所有记录中选出关键字最小的记录，把它与第记录，把它与第
6、1个记录交换，然后在个记录交换，然后在其余的记录中再选出关键字次最小的其余的记录中再选出关键字次最小的记录与第记录与第2个记录交换，以次类推，直个记录交换，以次类推，直到所有记录排序完成。到所有记录排序完成。 6.3 6.3 选择排序选择排序选选择择排排序序示示例例4938659776132749*1338659776492749*1327659776493849*1327389776496549*1327384976976549*1327384949*9765761327384949*6597761327384949*6576976. .4 冒泡排序冒泡排序 基本思想基本思想: 两两相邻元素
7、依次进行比较两两相邻元素依次进行比较, 让值较大的结点往下移让值较大的结点往下移(下沉下沉)，让值较，让值较小的结点往上移小的结点往上移(上冒上冒)。冒泡排序示例冒泡排序示例 21 25 49 25* 16 08 21 25 25* 16 08 49 21 25 16 08 25* 49 21 16 08 25 25* 49 16 08 21 25 25* 49 08 16 21 25 25* 496. .5 插入排序插入排序 基本思想基本思想: n n（1） 将数据序列分为将数据序列分为2个部分个部分, 前面已前面已排序排序, 后面未排序。后面未排序。n n（2）依次考察未排序的每个数据，将
8、其）依次考察未排序的每个数据，将其按其关键字大小，插入到前面已经排好按其关键字大小，插入到前面已经排好序的适当位置上。序的适当位置上。插入排序举例：插入排序举例： 21 25 49 25* 16 08 21 25 49 25* 16 08 21 25 49 25* 16 08 21 25 25* 49 16 08 16 21 25 25* 49 08 08 16 21 25 25* 49 6. .6 归并排序归并排序 基本思想基本思想: 通过对两个有序数据序列的归并来实现通过对两个有序数据序列的归并来实现排序。排序。 所谓所谓归并归并是指将若干个已排好序的部分是指将若干个已排好序的部分合并成一
9、个有序的部分。合并成一个有序的部分。 归并分类：归并分类： 二路归并、三路归并、多路归并二路归并、三路归并、多路归并归并排序示例归并排序示例(25) (57) (48) (37) (12) (92) (86)(25 57) (37 48) (12 92) (86)(25 37 48 57) (12 86 92)(12 25 37 48 57 86 92)6. .7 快速排序快速排序 基本思想基本思想: 取待排序列中取待排序列中某个元素某个元素的值作为基准值，的值作为基准值，将待排序列将待排序列划分划分为两个部分，左边部分为两个部分，左边部分的所有元素都小于等于这个基准值，而的所有元素都小于等于
10、这个基准值，而右边部分的所有元素都大于等于这个基右边部分的所有元素都大于等于这个基准值。然后，对左右两个子表用同样的准值。然后，对左右两个子表用同样的方法方法(递归递归)进行划分进行划分.快速排序示例快速排序示例(第一趟划分第一趟划分)4938659776132749* 38659776132749*273865977613 49*2738 9776136549*2738139776 6549*273813 76976549*273813 49 76 49 6549*49temp6. .8 堆排序堆排序 基本思想基本思想: 在排序过程中，将在排序过程中，将r1到到rn看成是一个看成是一个完全二
11、叉树完全二叉树顺序存储结构，利用完全二顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在叉树中双亲结点和孩子结点之间的内在关系来选择最小元素。关系来选择最小元素。10155625307010 15 56 25 30 70小顶堆示例小顶堆示例70563025151070 56 30 25 15 10大顶堆示例大顶堆示例堆排序的过程：堆排序的过程：n（1）将无序序列建成一个堆。）将无序序列建成一个堆。n（2）输出堆顶元素，将剩余元素调整为）输出堆顶元素，将剩余元素调整为一个新堆。一个新堆。例子：例子：关键字序列为关键字序列为 42，13，91，23， 24， 16，05，88，n=8，故从
12、第四个结点开始调整，故从第四个结点开始调整424213139191232324241616050588884213912324160588424213139191888824241616050523234213918824160523不调整不调整424213139191888824241616050523234213918824160523424288889191232324241616050513134288912324160513919188884242232324241616050513139188422324160513建成的堆建成的堆9191888842422323242416160
13、50513139188422324160513（1 1）初始堆）初始堆R1R1到到R8R8131388884242232324241616050591911388422324160591（2 2）第一趟排序之后）第一趟排序之后（3 3）重建的堆）重建的堆r1r1到到r7r7888824244242232313131616050591918824422313160591050524244242232313131616888891910524422313168891（4 4）第二趟排序之后）第二趟排序之后（5 5）重建的堆）重建的堆r1r1到到r6r642422424161623231313050
14、5888891914224162313058891（6 6）第三趟排序之后）第三趟排序之后050524241616232313134242888891910524162313428891（7 7）重建的堆）重建的堆r1r1到到r5r5242423231616050513134242888891912423160513428891（8 8）第四趟排序之后）第四趟排序之后131323231616050524244242888891911323160524428891（9 9）重建的堆）重建的堆r1r1到到r4r42323131316160505242442428888919123131605244
15、28891（1010）第五趟排序之后）第五趟排序之后050513131616232324244242888891910513162324428891（1111）重建的堆）重建的堆r1r1到到r3r3161613130505232324244242888891911613052324428891（1212）第六趟排序之后）第六趟排序之后050513131616232324244242888891910513162324428891（1313）重建的堆）重建的堆r1r1到到r2r2131305051616232324244242888891911305162324428891（1414）第七趟排序之后）第七趟排序之后050513131616232324244242888891910513162324428891
