清华大学（8）ppt课件

《清华大学（8）ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第9章排序及查找算法及其实现1清华大学黄维通设计制作本章主要内容排序概述冒泡排序法的设计及其实现选择排序法的设计及其实现插入排序法的设计及其实现SHELL排序法的设计及其实现字符串数组的排序设计及其实现查找概述顺序查找及其应用折半查找及其应用2清华大学黄维通设计制作在工程领域的计算机程序设计中，使用最广泛的，也是研究最充分的课题就是排序和查找算法了。有关排序和查找的算法遍布在千千万万的程序中，无论是数据库程序，还是各种编译程序、各种游戏，无一不用到排序和查找算法的9.1排序概述3清华大学黄维通设计制作所谓排序，就是将一个数据元素（或记录）的任意序列

2、，按照指定的关键字，重新排成一个有序的序列一般来说，排序处理时要指定排序所基于的关键字，排序算法就是根据关键字来比较的。当排序过程中需要交换的时候，则是对含有关键字的整条信息进行交换。9.1.1排序的概念4清华大学黄维通设计制作假设含n个记录的序列为：其相应的关键字序列为排序的目的是为了确定一个新的序列对应的关键字满足如下的非递减(或非递增)关系9.1.2序的定义5清华大学黄维通设计制作交换法9.1.3排序的方法每次只看相邻的两张牌，若不符合顺序则交换，多次交换直到符合要求先把牌都抓到手里，先选最大/小的一张放到一边，然后在剩下的里面选最大/小的，

3、依此类推，直到最后抓牌过程每摸到一张，将它插入合适的位置，直到最后选择法插入法以扑克排序为例6清华大学黄维通设计制作9.1.4排序效率7清华大学黄维通设计制作9.2冒泡排序法的设计及其实现8清华大学黄维通设计制作冒泡排序（BubbleSort）算法是最简单、最常见的也是效率最差的算法，适用于小数据量的排序。9.2.1冒泡算法设计思想9清华大学黄维通设计制作【例】有一组序列，顺序为5、4、3、2、1，用冒泡算法，对此序列按从小到大顺序排列#include#includevoidPrintArray(int*a,i

4、ntn)//输出排序每一步结果的函数{inti;for(i=0;i

5、-1;i++)//开始排序{flag=0;//标志初值为011清华大学黄维通设计制作for(j=0;ja[j+1]){tmp=a[j];a[j]=a[j+1];a[j+1]=tmp;flag=1;//若发生交换，flag变为1}}count++;//记录已经发生的排序次数printf("after%dsorting:",count);PrintArray(a,n);//第count次的排序结果if(flag==0)//每排序一次，flag都清0//若交换不再发生，则排序完成return;}}12清华大学黄维通

6、设计制作voidmain()//主函数{int*a,n=5,i;a=(int*)malloc(n*sizeof(int));//为5个待排序整型数开辟存储空间for(i=0;i

7、9.3选择排序法的设计及其实现14清华大学黄维通设计制作选择排序法的过程很简单。首次扫描的时候选择出最小的一个元素，将它和第一个位置(也称为当前的基准元素位置)的元素交换。然后从剩下的n-1个元素中选择次小的元素，再和第二个位置(变成当前新的基准元素位置了)的元素交换。不断重复这一过程，直到最后一次从最后两个元素里面选择比较小的一个，然后交换。9.3.1选择排序法设计思想15清华大学黄维通设计制作【例】选择排序法9.3.2选择排序法设计的实现16清华大学黄维通设计制作voidSelectSort(inta[],intn)//选择排序法的函数实现{i

8、nti,j,tmp;//tmp为中间变量intmin;//保存序列中的最小值intcount=0;//记录交换次数prin