清华大学_(8)备课讲稿.ppt

第第9章章排序及查找算法及其实现排序及查找算法及其实现1清华大学清华大学 黄维通黄维通 设计制作设计制作本章主要内容本章主要内容 排序概述排序概述 冒泡排序法的设计及其实现冒泡排序法的设计及其实现 选择排序法的设计及其实现选择排序法的设计及其实现 插入排序法的设计及其实现插入排序法的设计及其实现 SHELLSHELL排序法的设计及其实现排序法的设计及其实现 字符串数组的排序设计及其实现字符串数组的排序设计及其实现 查找概述查找概述 顺序查找及其应用顺序查找及其应用 折半查找及其应用折半查找及其应用2清华大学清华大学 黄维通黄维通 设计制作设计制作在工程领域的计算机程序设计中，在工程领域的计算机程序设计中，使用最广泛的，也是研究最充分的使用最广泛的，也是研究最充分的课题就是排序和查找算法了有关课题就是排序和查找算法了有关排序和查找的算法遍布在千千万万排序和查找的算法遍布在千千万万的程序中，无论是数据库程序，还的程序中，无论是数据库程序，还是各种编译程序、各种游戏，无一是各种编译程序、各种游戏，无一不用到排序和查找算法的不用到排序和查找算法的9.1排序概述排序概述3清华大学清华大学 黄维通黄维通 设计制作设计制作假设含假设含n个记录的序列为：个记录的序列为：其相应的关键字序列为其相应的关键字序列为排序的目的是为了确定一排序的目的是为了确定一个新的序列个新的序列对应的关键字满足如下的对应的关键字满足如下的非递减非递减(或非递增或非递增)关系关系9.1.2序的定义序的定义5清华大学清华大学 黄维通黄维通 设计制作设计制作交换法交换法9.1.3 9.1.3 排序的方法排序的方法 每次只看相邻的两张牌，若不每次只看相邻的两张牌，若不符合顺序则交换，多次交换直符合顺序则交换，多次交换直到符合要求到符合要求先把牌都抓到手里，先选最大先把牌都抓到手里，先选最大/小的一张放到一边，然后在小的一张放到一边，然后在剩下的里面选最大剩下的里面选最大/小的，依小的，依此类推，直到最后此类推，直到最后抓牌过程每摸到一张，将它插抓牌过程每摸到一张，将它插入合适的位置，直到最后入合适的位置，直到最后选择法选择法插入法插入法以扑克排以扑克排序为例序为例6清华大学清华大学 黄维通黄维通 设计制作设计制作9.1.4排序效率排序效率7清华大学清华大学 黄维通黄维通 设计制作设计制作9.2 9.2 冒泡排序法的冒泡排序法的设计及其实现设计及其实现 8清华大学清华大学 黄维通黄维通 设计制作设计制作冒泡排序（冒泡排序（Bubble Sort）算法是最）算法是最简单、最常见的也是效率最差的算法，简单、最常见的也是效率最差的算法，适用于适用于小数据小数据量的排量的排序。

序9.2.1 冒泡算法设计思想冒泡算法设计思想9清华大学清华大学 黄维通黄维通 设计制作设计制作【例】有一组序列，顺序为【例】有一组序列，顺序为5、4、3、2、1，用冒泡算法，对此序列按从小到大顺，用冒泡算法，对此序列按从小到大顺序排列序排列#include#includevoidPrintArray(int*a,intn)/输输出排序每一步出排序每一步结结果的函数果的函数inti;for(i=0;in;i+)/输输出元素出元素printf(%4d,ai);printf(n);9.2.2冒泡算法的实现冒泡算法的实现10清华大学清华大学 黄维通黄维通 设计制作设计制作voidBubbleSort(inta,intn)/排序函数排序函数inti,j,tmp;/tmp存存储储交交换换数据数据intflag;/标标志志变变量，如果量，如果为为0，/说说明不再交明不再交换顺换顺序，排序序，排序结结束束intcount=0;/计录计录交交换换次数次数printf(initialsorting:);PrintArray(a,n);/输输出排序前的序列出排序前的序列for(i=0;in-1;i+)/开始排序开始排序flag=0;/标标志初志初值为值为011清华大学清华大学 黄维通黄维通 设计制作设计制作for(j=0;jaj+1)tmp=aj;aj=aj+1;aj+1=tmp;flag=1;/若若发发生交生交换换，flag变为变为1count+;/记录记录已已经发经发生的排序次数生的排序次数printf(after%dsorting:,count);PrintArray(a,n);/第第count次的排序次的排序结结果果if(flag=0)/每排序一次，每排序一次，flag都清都清0/若交若交换换不再不再发发生，生，则则排序完成排序完成return;12清华大学清华大学 黄维通黄维通 设计制作设计制作voidmain()/主函数主函数int*a,n=5,i;a=(int*)malloc(n*sizeof(int);/为为5个待排序整型数开辟存个待排序整型数开辟存储储空空间间for(i=0;in;i+)scanf(%d,&ai);/输输入待排序数据入待排序数据BubbleSort(a,n);/调调用排序函数用排序函数free(a);/排序排序结结束，束，释释放存放存储储空空间间initialsorting:54321after1sorting:43215after2sorting:32145after3sorting:21345after4sorting:1234513清华大学清华大学 黄维通黄维通 设计制作设计制作9.3 选择排序法的设计及其实现选择排序法的设计及其实现14清华大学清华大学 黄维通黄维通 设计制作设计制作选择排序法的过程很简单。

首次扫描的时选择排序法的过程很简单首次扫描的时候选择出最小的一个元素，将它和第一个候选择出最小的一个元素，将它和第一个位置位置(也称为当前的基准元素位置也称为当前的基准元素位置)的元素的元素交换然后从剩下的交换然后从剩下的n-1个元素中选择次个元素中选择次小的元素，再和第二个位置小的元素，再和第二个位置(变成当前新变成当前新的基准元素位置了的基准元素位置了)的元素交换不断重的元素交换不断重复这一过程，直到最后一次从最后两个元复这一过程，直到最后一次从最后两个元素里面选择比较小的一个，然后交换素里面选择比较小的一个，然后交换9.3.1 选择排序法设计思想选择排序法设计思想15清华大学清华大学 黄维通黄维通 设计制作设计制作【例】选择排序法【例】选择排序法9.3.2 选择排序法设计的实现选择排序法设计的实现16清华大学清华大学 黄维通黄维通 设计制作设计制作voidSelectSort(inta,intn)/选择选择排序法的函数排序法的函数实现实现inti,j,tmp;/tmp为为中中间变间变量量intmin;/保存序列中的最小保存序列中的最小值值intcount=0;/记录记录交交换换次数次数printf(initialsorting:);PrintArray(a,n); /输输出当前出当前结结果果for(i=0;in-1;i+)/开始排序开始排序min=i;/基准元素的下基准元素的下标标/其他元素与其他元素与该该下下标标下的元素比下的元素比较较17清华大学清华大学 黄维通黄维通 设计制作设计制作for(j=i;jn;j+)if(ajamin)/若若小小于于基准元素，基准元素，则则交交换换min=j;/把要交把要交换换的位置告的位置告诉诉minif(min!=i)/若若min的的值值非非原来的原来的i，则则要交要交换换tmp=ai;/与基准元素与基准元素进进行位置交行位置交换换ai=amin;amin=tmp;count+;printf(after%dsorting:,count);PrintArray(a,n);18清华大学清华大学 黄维通黄维通 设计制作设计制作9.4 插入排序法的设计及其实现插入排序法的设计及其实现19清华大学清华大学 黄维通黄维通 设计制作设计制作 插入排序法的思想是：当插入第插入排序法的思想是：当插入第i i个元素个元素的时候，前面的时候，前面i-1i-1个元素已经排好了，这时只个元素已经排好了，这时只需要用第需要用第i i个的关键码从最后开始与其他的进个的关键码从最后开始与其他的进行比较，找到合适的位置，将后面的对象依行比较，找到合适的位置，将后面的对象依次后移，然后将新的对象插入。

次后移，然后将新的对象插入 9.4.1 插入排序法设计思想插入排序法设计思想20清华大学清华大学 黄维通黄维通 设计制作设计制作【例】用插入排序法实现排序【例】用插入排序法实现排序voidInsertSort(inta,intn)inti,j,tmp;for(i=1;i=0)&(tmpaj);j-)aj+1=aj; /其余元素后移其余元素后移aj+1=tmp;/ai就插在就插在这这个位置个位置printf(after%dsorting:,i);PrintArray(a,i+1);/输输出当前出当前结结果果9.4.2 插入排序法的实现插入排序法的实现若若当当前前元元素素比比前前面面已已经经排排序序过过的的元元素素序序列列的某个元素大的某个元素大21清华大学清华大学 黄维通黄维通 设计制作设计制作前面介绍的几种排序算前面介绍的几种排序算法都有一个共同的缺点，法都有一个共同的缺点，当序列中元素比较多的当序列中元素比较多的时候，排序时间会非常时候，排序时间会非常长，甚至长得不可忍受长，甚至长得不可忍受22清华大学清华大学 黄维通黄维通 设计制作设计制作9.5SHELL排序法的设计及其实现排序法的设计及其实现23清华大学清华大学 黄维通黄维通 设计制作设计制作9.5.1 SHELL排序法设计思想排序法设计思想24清华大学清华大学 黄维通黄维通 设计制作设计制作【例】对既有序列【例】对既有序列8，7，6，5，4，3，2，1，用，用SHELL排序法从小到大排序排序法从小到大排序voidshell(intcount,inta)/SHELL算法排序函数模算法排序函数模块块inti,j,gap=count,k,x;for(k=0;kcount;k+)/控制循控制循环环次数次数gap=gap/2;9.5.2 SHELL排序法的实现排序法的实现25清华大学清华大学 黄维通黄维通 设计制作设计制作for(i=gap;icount;+i)/进进行排序行排序x=ai;for(j=i-gap;(x=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清华大学清华大学 黄维通黄维通 设计制作设计制作下面几种典型的情况可以供参考：下面几种典型的情况可以供参考：对于元素关键码为数值对象的情况，当对于元素关键码为数值对象的情况，当关键码分布比较均匀的时候，通过简单关键码分布比较均匀的时候，通过简单的算术运算得到关键码的中值即可的算术运算得到关键码的中值即可对于元素关键码分布不均匀的情况，会对于元素关键码分布不均匀的情况，会出现在某些。