清华大学（8）ppt课件

第 9章 排序及查找算法及其实现 1清华大学 黄维通 设计制作 本章主要内容 排序概述 冒泡排序法的设计及其实现 选择排序法的设计及其实现 插入排序法的设计及其实现 SHELL排序法的设计及其实现 字符串数组的排序设计及其实现 查找概述 顺序查找及其应用 折半查找及其应用 2清华大学 黄维通 设计制作 在工程领域的计算机程序设计中， 使用最广泛的，也是研究最充分的 课题就是排序和查找算法了。有关 排序和查找的算法遍布在千千万万 的程序中，无论是数据库程序，还 是各种编译程序、各种游戏，无一 不用到排序和查找算法的 9.1 排序概述 3清华大学 黄维通 设计制作 所谓排序，就是将一个数据元素 （或记录）的任意序列，按照指定的 关键字，重新排成一个有序的序列 一般来说，排序处理时要指定排 序所基于的关键字，排序算法就是根 据关键字来比较的。当排序过程中需 要交换的时候，则是对含有关键字的 整条信息进行交换。 9.1.1排序的概念 4清华大学 黄维通 设计制作 假设含 n个记录的序列为 ： 其相应的关键字序列为 排序的目的是为了确定一 个新的序列 对应的关键字满足如下的 非递减 (或非递增 )关系 9.1.2序的定义 5清华大学 黄维通 设计制作 交换法 9.1.3 排序的方法 每次只看相邻的两张牌，若不 符合顺序则交换，多次交换直 到符合要求 先把牌都抓到手里，先选最大 /小的一张放到一边，然后在 剩下的里面选最大 /小的，依 此类推，直到最后 抓牌过程每摸到一张，将它插 入合适的位置，直到最后 选择法 插入法 以扑克排 序为例 6清华大学 黄维通 设计制作 9.1.4排序效率 7清华大学 黄维通 设计制作 9.2 冒泡排序法的 设计及其实现 8清华大学 黄维通 设计制作 冒泡排序（ Bubble Sort） 算法是最 简单、最常见的也是效率最差的算法， 适用于 小数据 量的排 序。 9.2.1 冒泡算法设计思想 9清华大学 黄维通 设计制作 【例】有一组序列，顺序为 5、 4、 3、 2 、 1，用冒泡算法，对此序列按从小到大 顺序排列 #include #include void PrintArray(int * a, int n) /输 出排序每一步 结 果的函数 int i; for(i=0; i aj+1) tmp = aj; aj = aj+1; aj+1 = tmp; flag = 1; /若 发 生交 换 ， flag变为 1 count+; /记录 已 经发 生的排序次数 printf(“after %d sorting:“,count); PrintArray(a,n); /第 count次的排序 结 果 if(flag = 0) /每排序一次， flag都清 0 /若交 换 不再 发 生， 则 排序完 成 return; 12清华大学 黄维通 设计制作 void main() /主函数 int *a,n=5,i; a=(int *)malloc(n*sizeof(int); /为 5个待排序整型数开辟存 储 空 间 for(i=0; i=0) j=j-gap) aj+gap=aj; aj+gap=x; if (gap=0) break; printf(“gap=%d:n“,gap); PrintArray(a,count);/输 出 结 果 26清华大学 黄维通 设计制作 9.6 字符串数组的排序设计及其实现 27清华大学 黄维通 设计制作 如：文件夹中的排列，电子词典中的排列 采用前面描述的方法，即发现当 两个元素需要交换的时候，交换 整个字符串，或者移动整个字符 串，那么将会非常浪费时间 9.6.1字符串数组的排序算法 设计思想 28清华大学 黄维通 设计制作 快速排序也不是稳定排序。快速排序 算法的效率与基准对象的合理选取有 关，最好每次每个子序列中的对象数 尽量接近，可以加速快速排序速度 29清华大学 黄维通 设计制作 下面几种典型的情况可以供参考： 对于元素关键码为数值对象的情况，当 关键码分布比较均匀的时候，通过简单 的算术运算得到关键码的中值即可。 对于元素关键码分布不均匀的情况，会 出现在某些值附近相对比较集中的情况 ，这时可能随机选取基准会更好一些。 还有一种常用的有效的方法是，从序列 中随机选取三个元素，选其中关键码为 中值的那个作为基准。 30清华大学 黄维通 设计制作 【例】有任意 5个字符串如 “abc“,“ccc“,“bca“,“acb“,“bbb“， 请按 ASCII顺序排序输出。 下面给出字符串数组排序算法的实现 ，该算法用到递归。 9.6.2 字符串数组排序算法的 实现 31清华大学 黄维通 设计制作 void QuickSort(char *a, int left, int right) int min,max; char *norm, *tmp; min = left; / 本子序列最左端 max = right; / 本子序列最右端 norm=a(left+right)/2;/取中 间为 基准 do while(strcmp(amin,norm)0 / 退出 while条件 为 找到一个 /小于等于基准的，或者 max=left if(min min) QuickSort(a,min,right); 33清华大学 黄维通 设计制作 查找是数据处理中最常见的一种 运算。所谓查找就是在数据集合中寻 找满足某种条件的对象。 9.7 查找概述 顺序查找 折半查找 34清华大学 黄维通 设计制作 9.8 顺序查找及其应用 35清华大学 黄维通 设计制作 顺序查找算法的思想很简单：就是 在有序集合中从头按照指定的关键 码来查找，直到找到符合要求的元 素或者没有找到符合要求的元素 9.8.1顺序查找算法的设计思想 36清华大学 黄维通 设计制作 【例】在给定的序列 1,3,5,7,9,11,13,15 中查找 指定 的数据。 本例 给 定指定序列 ,在此序列中 查 找 1 、 4、 9、 10这 4个数据所在的位置。 由于我 们 用数 组 存 储 指定的序列，那 么， 查 找的数据所在的位置也是相 对 于 数 组 下 标 的位置。 9.8.2顺序查找算法的实现 37清华大学 黄维通 设计制作 #include int Search(int a, int n, int key) int i; for(i=0; i=0)/若 找到相 应 的元素 printf(“find %d pos at %dn“,bi,pos); /输 出找到的元素 else printf(“cant find %dn“,bi); /没有找到 39清华大学 黄维通 设计制作 折半查找算法是另一种查找算法 ，它在效率上比顺序查找要高，这也 是目前经常使用的查找方法之一 ,但 折半查找要求查找的数据集合是有序 的 9.9 折半查找及其应用 40清华大学 黄维通 设计制作 折半查找算法的思想是：逐渐缩 小目标对象可能存在的范围。首先测 试集合中间那个元素的值，然后确定 目标对象是在中间元素的左半区还是 右半区，然后再到可能的半区重复上 述过程，直到找到指定目标或者查找 失败 9.9.1折半查找算法的设计思想 41清华大学 黄维通 设计制作 【例】折半查找法的实现 #include int BinarySearch(int a, int n, int key) /折半 查 找函数 int top; /序列的首元素 标识 int bottom; /序列的尾元素 标识 int mid; /序列 的 中 间 元素 标识 top = n-1; bottom = 0; 9.9.2折半查找算法的实现 42清华大学 黄维通 设计制作 while(bottom=top) mi