数据库三级第六讲.ppt

第六讲 查找与排序,查找：查找是在一个给定的数据结构中，根据给定的条件查找满足条件的结点。不同的数据结构采用不同的查找方法。查找的效率直接影响数据处理的效率。查找的结果：查找成功：找到满足条件的结点查找失败：找不到满足条件的结点。,可以采用从前向后查，也可采用从后向前查的方法。在平均情况下，大约要与表中一半以上元素进行比较，效率较低。平均查找长度较大。,查找过程：对给定的一关键字K，从线性表的一端开始，逐个进行记录的关键字和K的比较，直到找到关键字等于K的记录或到达表的另一端。,6.1 顺序查找,监视哨,使用了监视哨，在查找过程中，不用每一步都去判断是否查找结束。找到：返回元素在线性表中的存储位置；未找到：返回0。,思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。前提：必须在具有顺序存储结构的有序表中进行。,分三种情况：1）若中间项的值等于x,则说明已查到。2）若x小于中间项的值，则在线性表的前半部分查找；3）若x大于中间项的值，则在线性表的后半部分查找。,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),(08,14,23,37,46,55,68,79,91),(08,14,23,37,46,55,68,79,91),(08,14,23,37,46,55,68,79,91),(08,14,23,37,46,55,68,79,91),(08,14,23,37,46,55,68,79,91),基本思想:首先在所有记录中选出关键字最小的记录，把它与第1个记录交换，然后在其余的记录中再选出关键字次最小的记录与第2个记录交换，以次类推，直到所有记录排序完成。,6.3 选择排序,选择排序示例,49,38,65,97,76,13,27,49*,13,38,65,97,76,49,27,49*,13,27,65,97,76,49,38,49*,13,27,38,97,76,49,65,49*,13,27,38,49,76,97,65,49*,13,27,38,49,49*,97,65,76,13,27,38,49,49*,65,97,76,13,27,38,49,49*,65,76,97,6.4 冒泡排序,基本思想:两两相邻元素依次进行比较,让值较大的结点往下移(下沉)，让值较小的结点往上移(上冒)。,冒泡排序示例,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*49,6.5 插入排序,基本思想:（1）将数据序列分为2个部分,前面已排序,后面未排序。（2）依次考察未排序的每个数据，将其按其关键字大小，插入到前面已经排好序的适当位置上。,插入排序举例：,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 归并排序,基本思想:通过对两个有序数据序列的归并来实现排序。所谓归并是指将若干个已排好序的部分合并成一个有序的部分。归并分类：二路归并、三路归并、多路归并,归并排序示例,(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 快速排序,基本思想:取待排序列中某个元素的值作为基准值，将待排序列划分为两个部分，左边部分的所有元素都小于等于这个基准值，而右边部分的所有元素都大于等于这个基准值。然后，对左右两个子表用同样的方法(递归)进行划分.,快速排序示例(第一趟划分),49,38,65,97,76,13,27,49*,38,65,97,76,13,27,49*,27,38,65,97,76,13,49*,27,38,97,76,13,65,49*,27,38,13,97,76,65,49*,27,38,13,76,97,65,49*,27,38,13,49,76,49,65,49*,49,temp,6.8 堆排序,基本思想:在排序过程中，将r1到rn看成是一个完全二叉树顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小元素。,10,15,56,25,30,70,10,15,56,25,30,70,小顶堆示例,70,56,30,25,15,10,70,56,30,25,15,10,大顶堆示例,堆排序的过程：,（1）将无序序列建成一个堆。（2）输出堆顶元素，将剩余元素调整为一个新堆。,例子：关键字序列为 42，13，91，23，24，16，05，88，n=8，故从第四个结点开始调整,42,13,91,23,24,16,05,88,42,13,91,23,24,16,05,88,42,13,91,88,24,16,05,23,42,13,91,88,24,16,05,23,不调整,42,13,91,88,24,16,05,23,42,13,91,88,24,16,05,23,42,88,91,23,24,16,05,13,42,88,91,23,24,16,05,13,91,88,42,23,24,16,05,13,91,88,42,23,24,16,05,13,建成的堆,91,88,42,23,24,16,05,13,91,88,42,23,24,16,05,13,（1）初始堆R1到R8,13,88,42,23,24,16,05,91,13,88,42,23,24,16,05,91,（2）第一趟排序之后,（3）重建的堆r1到r7,88,24,42,23,13,16,05,91,88,24,42,23,13,16,05,91,05,24,42,23,13,16,88,91,05,24,42,23,13,16,88,91,（4）第二趟排序之后,（5）重建的堆r1到r6,42,24,16,23,13,05,88,91,42,24,16,23,13,05,88,91,（6）第三趟排序之后,05,24,16,23,13,42,88,91,05,24,16,23,13,42,88,91,（7）重建的堆r1到r5,24,23,16,05,13,42,88,91,24,23,16,05,13,42,88,91,（8）第四趟排序之后,13,23,16,05,24,42,88,91,13,23,16,05,24,42,88,91,（9）重建的堆r1到r4,23,13,16,05,24,42,88,91,23,13,16,05,24,42,88,91,（10）第五趟排序之后,05,13,16,23,24,42,88,91,05,13,16,23,24,42,88,91,（11）重建的堆r1到r3,16,13,05,23,24,42,88,91,16,13,05,23,24,42,88,91,（12）第六趟排序之后,05,13,16,23,24,42,88,91,05,13,16,23,24,42,88,91,（13）重建的堆r1到r2,13,05,16,23,24,42,88,91,13,05,16,23,24,42,88,91,（14）第七趟排序之后,05,13,16,23,24,42,88,91,05,13,16,23,24,42,88,91,