数据库三级第六讲.pptVIP

第六讲 查找与排序 6.1 顺序查找 6.2 折半查找（二分法查找） 6.3 选择排序 基本思想: 首先在所有记录中选出关键字最小的记录，把它与第1个记录交换，然后在其余的记录中再选出关键字次最小的记录与第2个记录交换，以次类推，直到所有记录排序完成。 选择排序示例 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 插入排序举例： [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] 快速排序示例(第一趟划分) 堆排序的过程： （1）将无序序列建成一个堆。 （2）输出堆顶元素，将剩余元素调整为一个新堆。 （6）第三趟排序之后 05 24 16 23 13 42 88 91 05 24 16 23 13 42 88 91 （7）重建的堆r[1]到r[5] 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 * 查找：查找是在一个给定的数据结构中，根据给定的条件查找满足条件的结点。不同的数据结构采用不同的查找方法。查找的效率直接影响数据处理的效率。 查找的结果： 查找成功：找到满足条件的结点 查找失败：找不到满足条件的结点。 可以采用从前向后查，也可采用从后向前查的方法。 在平均情况下，大约要与表中一半以上元素进行比较，效率较低。平均查找长度较大。 查找过程： 对给定的一关键字K，从线性表的一端开始，逐个进行记录的关键字和K的比较，直到找到关键字等于K的记录或到达表的另一端。 0 1 2 3 4 5 6 7 （a） 初态 40 80 30 60 10 20 25 (b) K=80 (return i=4) 80 40 80 30 60 10 20 25 0 1 2 3 4 5 6 7 (c) K=90 (return i=0 ) 0 1 2 3 4 5 6 7 90 40 80 30 60 10 20 25 监视哨 使用了监视哨，在查找过程中，不用每一步都去判断是否查找结束。 找到：返回元素在线性表中的存储位置； 未找到：返回0。 思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。 前提：必须在具有顺序存储结构的有序表中进行。 分三种情况： 1）若中间项的值等于x,则说明已查到。 2）若x小于中间项的值，则在线性表的前半部分查找； 3）若x大于中间项的值，则在线性表的后半部分查找。 查找23和79的过程如下图： mid=(low+high)/2不进位取整 ( 08, 14, 23, 37, 46, 55,