51058-00C语言程序设计课件-黄维通c_new_07

清华大学黄维通设计制作,1,第7章排序及查找算法及其实现,清华大学黄维通设计制作,2,本章主要内容,排序概述冒泡排序法的设计及其实现选择排序法的设计及其实现插入排序法的设计及其实现SHELL排序法的设计及其实现快速排序设计及其实现查找概述顺序查找及其应用折半查找及其应用,清华大学黄维通设计制作,3,在工程领域的计算机程序设计中，使用最广泛的，也是研究最充分的课题就是排序和查找算法了。有关排序和查找的算法遍布在千千万万的程序中，无论是数据库程序，还是各种编译程序、各种游戏，无一不用到排序和查找算法的,7.1排序概述,清华大学黄维通设计制作,4,所谓排序，就是将一个数据元素（或记录）的任意序列，按照指定的关键字，重新排成一个有序的序列,一般来说，排序处理时要指定排序所基于的关键字，排序算法就是根据关键字来比较的。当排序过程中需要交换的时候，则是对含有关键字的整条信息进行交换。,9.1.1排序的概念,清华大学黄维通设计制作,5,假设含n个记录的序列为：其相应的关键字序列为排序的目的是为了确定一个新的序列对应的关键字满足如下的非递减(或非递增)关系,7.1.2序的定义,清华大学黄维通设计制作,6,交换法,7.1.3排序的方法,每次只看相邻的两张牌，若不符合顺序则交换，多次交换直到符合要求,先把牌都抓到手里，先选最大/小的一张放到一边，然后在剩下的里面选最大/小的，依此类推，直到最后,抓牌过程每摸到一张，将它插入合适的位置，直到最后,选择法,插入法,以扑克排序为例,清华大学黄维通设计制作,7,7.2冒泡排序法的设计及其实现,清华大学黄维通设计制作,8,冒泡排序（BubbleSort）算法是最简单、最常见的也是效率最差的算法，适用于小数据量的排序。,7.2.1冒泡算法设计思想,清华大学黄维通设计制作,9,【例】有一组序列，顺序为5、4、3、2、1，用冒泡算法，对此序列按从小到大顺序排列#include#includevoidPrintArray(int*a,intn)/输出排序每一步结果的函数inti;for(i=0;in;i+)/输出元素printf(%4d,ai);printf(n);,7.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;/标志初值为0,清华大学黄维通设计制作,11,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,/排序结束，释放存储空间,initialsorting:54321after1sorting:43215after2sorting:32145after3sorting:21345after4sorting:12345,13,冒泡法实现字符串的降序排列。#include#includevoidmain()char*p_str8=Beijing,Shanghai,Tianjin,Changchun,Shenyang,Baoding,Hefei,Shenzhen,*temp;inti,j;for(i=0;i8;i+)/冒泡法排序for(j=0;j7-i;j+)if(strlen(p_strj)strlen(p_strj+1)temp=p_strj;p_strj=p_strj+1;p_strj+1=temp;,14,elseif(strlen(p_strj)=strlen(p_strj+1)if(strcmp(p_strj,p_strj+1)1)temp=p_strj;p_strj=p_strj+1;p_strj+1=temp;else;for(i=0;i8;i+)/输出字符串printf(%sn,p_stri);printf(n);,清华大学黄维通设计制作,15,7.3选择排序法的设计及其实现,清华大学黄维通设计制作,16,选择排序法的过程很简单。首次扫描的时候选择出最小的一个元素，将它和第一个位置(也称为当前的基准元素位置)的元素交换。然后从剩下的n-1个元素中选择次小的元素，再和第二个位置(变成当前新的基准元素位置了)的元素交换。不断重复这一过程，直到最后一次从最后两个元素里面选择比较小的一个，然后交换。,7.3.1选择排序法设计思想,清华大学黄维通设计制作,17,【例】选择排序法,7.3.2选择排序法设计的实现,18,voidSelectSort(inta,intn)inti,j,tmp;/tmp为中间变量intmin;/保存序列中的最小值printf(initialsorting:);PrintArray(a,n);/输出当前结果for(i=0;in-1;i+)/开始排序min=i;/基准元素的下标for(j=i;jn;j+)/其他元素与该下标下的元素比较if(ajamin)/若小于基准元素，则交换min=j;/把要交换的位置告诉minif(min!=i)/若min的值非原来的i，则要交换tmp=ai;/与基准元素进行位置交换ai=amin;amin=tmp;printf(after%dsorting:,i+1);PrintArray(a,n);,清华大学黄维通设计制作,19,7.4插入排序法的设计及其实现,清华大学黄维通设计制作,20,插入排序法的思想是：当插入第i个元素的时候，前面i-1个元素已经排好了，这时只需要用第i个的关键码从最后开始与其他的进行比较，找到合适的位置，将后面的对象依次后移，然后将新的对象插入。,7.4.1插入排序法设计思想,21,【例】用插入排序法实现排序voidInsertSort(int*a,intn)inti,j,tmp;if(n=0)printf(after%dsorting:,n);PrintArray(a,n);elseif(n=1)if(a1a0)tmp=a1;a1=a0;a0=tmp;printf(after%dsorting:,n);PrintArray(a,n);,7.4.2插入排序法的实现,22,elsetmp=an;if(tmp=a0)for(j=n;1=j;j-)aj=aj-1;/其余元素后移a0=tmp;/就插在a0位置elseif(an-1tmp)an=tmp;elsefor(i=0;in;i+)if(aitmp)/输出当前结果,清华大学黄维通设计制作,23,voidPrintArray(int*a,intn)/输出排序每一步结果的函数inti;for(i=0;i=n;i+)/输出元素printf(%4d,ai);printf(n);,清华大学黄维通设计制作,24,voidmain()/主函数int*a,n=10,i;a=(int*)malloc(n*sizeof(int);/为10个待排序整型数开辟存储空间for(i=0;iaj+gap)temp=aj;aj=aj+gap;aj+gap=temp;PrintArray(a,n);/输出结果,7.5.2SHELL排序法的实现,32,#includestdio.h#includestdlib.hvoidPrintArray(int*a,intn)/输出排序每一步结果的函数inti;for(i=0;i49,两者交换，此时i=3)进行第二次交换后：27384997761365,37,(按照算法的第五步将又一次执行算法的第三步从后开始向前找)进行第三次交换后：27381397764965(依算法的第四步从前面开始找大于key的值并进行两者交换，此时j=4)进行第四次交换后：27381349769765此时再执行第三步的时候就发现i=j，从而结束一趟快速排序，那么经过一趟快速排序之后的结果是：27381349769765，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。,38,快速排序就是递归调用上述过程。在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列。,初始状态：49386597761327进行一次快速排序之后划分为：27381349769765分别对前后两部分进行快速排序：273813经第三步和第四步交换后变成132738769765经第三步和第四步交换后变成657697完成排序。,39,#includestdio.hintpartions(inta,intlow,inthigh)intkey=alow,p;/alow就是a0;while(low=key)-high;p=alow;alow=ahigh;ahigh=p;while(lowhigh,40,voidqsort(inta,intlow,inthigh)inti,k;if(lowhigh)k=partions(a,low,high);for(i=0;i11;printf(%3d,ai),i+);printf(n);qsort(a,low,k-1);qsort(a,k+1,high);,voidmain()inti,a11=11,0,12,5,6,13,8,9,14,7,10;for(i=0;i11;printf(%3d,ai),+i);printf(n);qsort(a,0,10);for(i=0;i11;printf(%3d,ai),+i);printf(n);,41,42,下面几种典型的情况可以供参考：对于元素关键码为数值对象的情况，当关键码分布比较均匀的时候，通过简单的算术运算得到关键码的中值即可。,对于元素关键码分布不均匀的情况，会出现在某些值附近相对比较集中的情况，这时可能随机选取基准会更好一些。,还有一种常用的有效的方法是，从序列中随机选取三个元素，选其中关键码为中值的那个作为基准。,清华大学黄维通设计制作,43,归并排序,归并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。,清华大学黄维通设计制作,44,查找是数据处理中最常见的一种运算。所谓查找就是在数据集合中寻找满足某种条件的对象。,7.7查找概述,顺序查找,折半查找,清华大学黄维通设计制作,45,7.8顺序查找及其应用,清华大学黄维通设计制作,46,顺序查找算法的思想很简单：就是在有序集合中从头按照指定的关键码来查找，直到找到符合要求的元素或者没有找到符合要求的元素,7.8.1顺序查找算法的设计思想,47,【例】在给定的序列1,3,5,7,9,11,13,15中查找指定的数据。本例给定指定序列,在此序列中查找1、4、9、10这4个数据所在的位置。由于我们用数组存储指定的序列，那么，查找的数据所在的位置也是相对于数组下标的位置。,7.8.2顺序查找算法的实现,48,#includeintSearch(inta,intn,intkey)inti;for(i=0;in;i+)/进行顺序查找if(ai=key)/逐一进行数据匹配returni;/返回匹配数据的数组下标return-1;/如果没有找到，返回-1,49,voidmain()inta=1,3,5,7,9,11,13,15;intb=1,4,9,10;/需查找的序列intna=sizeof(a)/sizeof(int);/指定序列元素个数intnb=sizeof(b)/sizeof(int);/需查找的元素个数inti,pos;for(i=0;i=0)/若找到相应的元素printf(find%dposat%dn,bi,pos);/输出找到的元素elseprintf(cantfind%dn,bi);/没有找到,清华大学黄维通设计制作,50,折半查找算法是另一种查找算法，它在效率上比顺序查找要高，这也是目前经常使用的查找方法之一,但折半查找要求查找的数据集合是有序的,7.9折半查找及其应用,清华大学黄维通设计制作,51,折半查找算法的思想是：逐渐缩小目标对象可能存在的范围。首先测试集合中间那个元素的值，然后确定目标对象是在中间元素的左半区还是右半区，然后再到可能的半区重复上述过程，直到找到指定目标或者查找失败,7.9.1折半查找算法的设计思想,清华大学黄维通设计制作,52,【例】折半查找法的实现#include#includetime.hintBinarySearch(inta,intn,intkey)/折半查找函数inttop;/序列的首元素标识intbottom;/序列的尾元素标识intmid;/序列的中间元素标识top=n-1;bottom=0;,7.9