第3章 查找与排序.pptVIP

* * * * * * * 3.2 排序 冒泡排序 基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。小的浮起，大的沉底。从左端开始比较 优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。 前提：顺序存储结构 3.2 排序 冒泡排序 16， 08， 16， 08， 21， 08， 16， 08， 21， 21， 21， 25， 25， 08， 16， 16， 25*， 08， 25， 08， 08， 16， 25*， 25*， 25*， 16， 25*， 49， 16， 49， 25*， 例3：关键字序列 T=(21，25，49，25*，16，08），请写出冒泡排序的具体实现过程。 21，25，49， 25*，16， 08 初态： 第1趟 第2趟 第3趟 第4趟 第5趟 演示 25， 16， 08 21， 49， 08， 49 25， 49 21， 25， 49 21， 25*， 16， 49 25， 25*， 49 排序完成 3.2 排序 快速排序 冒泡排序中，由于扫描过程中只对相邻的两个元素进行比较，因此在互换两个相邻元素时只能消除一个逆序。 快速排序就是想通过一次交换而消除多个逆序的一种方法。 基本思想： 从待排序记录序列中选取一个记录（通常选第一个记录）作为枢轴（也称支点），其关键字设为K1 将其余记录的关键字与K1进行比较，小于K1的记录移到前面，而大于K1的记录移到后面，结果将待排序记录序列分成两个子序列，最后将关键字为K1的记录插到两个子序列中间 上述过程称作一趟快速排序。 对分割后的子序列继续按上述原则进行划分，直到所有子序列的表长不超过1为止 快速排序是目前内部排序方法中最快的一种排序，在平均情况下耗费的时间最小。 若初始记录序列按关键字有序或基本有序时，快速排序将蜕变为冒泡排序，其时间耗费与冒泡排序相同。 快速排序是不稳定排序。 3.2 排序 选择排序 基本思想 每一趟在n-i+1(i=1,2,…,n-1)个记录中选出关键字最小（或最大）的记录作为有序序列的第i个记录 方法 简单选择排序（亦称直接选择排序） 堆排序 3.2 排序 简单选择排序 基本思想 首先从1~n个元素中选出关键字最小的记录交换到第一个位置上；然后再从第2 ~n个元素中选出最小的记录交换到第二个位置上，依次类推。 适用于待排序元素较少的情况 初态 8 3 9 1 6 8 3 9 1 6 8 3 9 1 6 8 3 9 1 6 i j k i j k i j k i j k 1 3 9 8 6 互换 i j k 1 3 9 8 6 i k j 1 3 9 8 6 i k j 第一趟 第二趟 1 3 9 8 6 i k j 第三趟 * * * * * * * * * * * * * * * * * * * * * * * * * * * 数据库技术与应用 第3章 查找与排序 教 学 史令 刘江 编著 数据库技术与应用 珠海市斗门区广播电视大学 何康乐 第3章 查找与排序 目 录 查找 3.1 排序 3.2 3.1 查找 3.1.1查找的基本概念 1.查找 就是在给定的DS中找出满足某种条件的结点；若存在这样的结点，查找成功；否则，查找失败。（找） 2.查找表 是一组待查数据元素的集合。（待找） 3.静态查找 是仅仅进行查询和检索操作，不改变查找表中数据元素间的逻辑关系的查找。（不改变元素关系） 4.动态查找 是除了进行查询和检索操作外，还对查找表进行插入、删除操作的查找，动态地改变查找表中数据元素之间的逻辑关系。（改变元素关系） 3.1.2静态查找表 查找算法主要有： 顺序查找（线性查找） 折半查找（二分查找） 分块查找（索引顺序查找） 主要结构： 顺序表 有序顺序表 索引顺序表 3.1 查找 顺序查找（线性查找） 查找过程 对给定的一关键字K，从线性表的