程序设计基础教案202课时——查找与排序.docx

《程序设计基础教案202课时——查找与排序.docx》由会员分享，可在线阅读，更多相关《程序设计基础教案202课时——查找与排序.docx（9页珍藏版）》请在第一文库网上搜索。

1、教案序号20周次授课形式新授授课章节名称查找与排序教学目的学会使用查找和排序的技术教学重点查找、排序教学难点查找、排序使用教具机房课外作业课后体会授课主要内容1.15.2查找与排序5.2.1 排序排序是数据处理中常见的操作。所谓排序就是把数组中的元素按其值递增或递减的次序排列，这在很多实际应用中都需要用到，如要将学生成绩进行排序等。常用的排序方法很多，有直接插入排序法、SHE11排序法、选择排序法、冒泡排序法等等。在本节主要介绍后两种排序法。1 .选择排序法选择排序法的基本方法是：逐次重复地找出数组中最小值（或最大值），按被找到的先后次序将数组元素排列起来，从而实现数组的排序。在这个过程中，一

2、般要借助于一个临时变量作为在排序过程中数组元素值交换时的暂存单元。例5.4有一个数组a5,其元素值及排列次序如下：4,2,8,6,1。现要求用选择排序法将其按升序排列。第一次从这5个元素中选择(找出)最小的元素，将其与数组中的第一个元素进行值的交换。第二次选择是从数组中第二个元素起的5-1个元素中选择值最小的元素，将该元素与数组的第二个元素进行值的交换。下面第三次、第四次都按这种方法进行。每选择一次，就排好一个元素的次序，然后再对余下的元素进行选择，最后剩下一个元素(即数组中最大的元素)时，排序就完成了。数组原始状态：4,2,8,6,1第一次选择后：1,2,8,6,4第二次选择后：12,8,6

3、,4第三次选择后：1,2,4,6,8第四次选择后：1,2,4,6,8这样该数组就排序完成。方括号中的内容是待排序的数组元素值。具体算法如图5.3所示，其中共分为三块：第一块i循环，功能是输入待排序的5个数据放入数组a中，上04。第二块i循环，功能是按升序选择法排序，基本方法是先选出最小值元素和第一个元素交换位置，然后，再对剩下的n-1个元素重复这样的选择和交换，这样不断重复至所有的元素全被排序为止。第三块循环是输出排好序以后的数组元素。主要功能：选择法升序排序#inc1udeintmain()(inta5,i,j,k,temp,min;Primf(输入5个待排序的数:n)for(i=0;i=4

4、;i+)scanf(%d,fcai);for(i=0;i=3;i+)k=i+1;min=i;for(j=k;j=4;j+)if(ajamin)min=j;temp=ai;ai=amin;amin=temp;)Printf(输出排序后的数:n)for(i=0;i,ai);return0;)运行情况为：输入5个待排序的数：42861/输出排序后的数：124682.冒泡法排序对于升序持序，其冒泡法的基本思路是：从第一个元素开始，将相邻两个数比较，将较小的元素交换到前面。例5.5若有7个数：9,8,7,6,5,4,3。则用冒泡法按升序持序过程如图5.4所示。第一次9I_8-I76543第二次89I_7

5、I6543第三次879I_6_I543笫四次8769I_5_I43第五次87659I_4_I3第六次8765493I结果8765439图54第一次将8和9对调，第二次将笫2个数和笫3个数(9和7)对调，第三次将第3数和第4数(9和6)对调如此共进行6次，得到8,7,6,5,4,3,9的顺序，可以看到：最大的数9已“沉底”，而小的数已“上升”，最小的数3已向上“浮起”一个位置。经第一轮(共6次)后，已得到最大的数。然后进行第二轮比较，对余下的前面的6个数按上述方法进行比较、对调(需要时)，经过5次比较，得到次大的数8。依次类推，对7个数要比较6轮，才能使7个数按升序排序。在第一轮中要进行两个数之

6、间的比较共6次，第二轮中比5次第六轮比I次。若有n个数，则要进行n-1轮比较。在第I轮中要进行n-1次两两比较，在笫j轮比较中要进行n-j次两两比较。算法设计如下：程序中定义三个变量(1)待排序的数的个数N,本题N=7。(2)比较轮数j,j=1,2,N-Io(3)第j轮待比较元素的下标i,i=1,2,N-j。程序要用两重计数型循环，步骤如下：(1)将待排序的数据放入数组a中。(2)让j取初值1。(3)让i从1到N-j,比较aiai+1,如果aiv=ai+1,位置不动；如果aiai+1,位置对调。此步结束后，aNj+1中的数为最小的数。(4)让j=j+1;只要j!=N-1就返回第(3)步，将aN

7、-j+1的值排好。j=N-I时执行步骤(5)。(5)输出排序结果。算法流程图见图5.5。主要功能：冒泡法升序排序intmain()intaN+1;定义数组长度为N+1,本题中为符合人们的习惯，a0不用,只用a1倒aNPrintf（输入待排序的数组元素:W）;for(i=1;i=N;i+)/用键盘输入数组元素scanf(,%dai);冒泡排序，外层循环for(i=1;iai1)让ai和ai+1对调temp=ai;afi=ai+1;ai+1=temp;Printfr输出排序后的数组元素:n）;printf(%dn,ai);return0;运行情况为:输入待排序的数组元素：9876543/输出排序后

8、的数组元素：34567895.2.2查找查找是指在数组中查找与给定值相同的数组元素。查找的方法很多，如线性查找法和二分查找法。1 .线性查找法线性查找法是最简单的查找方法。若在一个一维数组a10中查找给定值X,其过程是：先从数组的第一个元素a0查起，看是否等于X,若等于X,即找到了，否则，接着查找第二个元素a1,第三个元素a2,直到最后一个元素a9。线性查找法不要求被操作的数组是否排序。例5.6设有一个数组aIO,X为需查找的数组元素值。编程，用线性查找法查找。#inc1udeintmain()(inta10=12,4,23,56,34,2,15,68,56,1);intx,i,f1ag=O;

9、scanf(%d,&x);for(i=0;i10;i+)if(ai=x)f1ag=1;break;if(f1ag=()printf(nofound);e1seprintf(a%d=%dn,i,ai);returnO;)2 .二分查找法线性算法简单，但查找效率较低，当数据量很大时不宜采用。对具有大量数据的数组则采用二分查找法较好。采用二分法查找时，数组应是已排好序的。二分法的基本思想是：假设数据是按升序排序的，对于给定值X,从序列的中间位置开始比较，如果当前位置值等于X,则查找成功；否则若X小于当前位置值，则在序列的前半段数据中继续查找；若X大于当前位置值，则在序列的后半段数据中继续查找，直到找

10、到为止。若表示序列查找范围的上、下界数值颠倒时，查找不成功。假如有一组数为：3 ,12,24,36,55,68,75,88要查找给定值x=24这个数。可设三个变量front,mid,end分别指向数列的上界、中间和下界，mid=(front+end)20查找过程如下：(1)开始时令front=0(指向3),end=7(指向88),则mid=3(指向36),若用“(”和“),，代表查找范围，下划线指明要比较的数，即mid所在的位置，则有下列表示：(312243655687588)此时amid=36,xamid,故确定应在后半段中查找。(3)令新的front=mid+1=2,而end=2不变，则新

11、的mid=2,并有下列表示：(312243655687588)此时x=amid=2,查找成功了。如果要找的数X不是数列中的数，例如x=25,当第三次判断时，xamid,按以上的规律，令front=mid+1,即front=3,出现frontend的情况，表示查找不成功。例5.7用二分法查找，在一个有序的有N个元素的a数组中是否存在用户输入的数据X。算法如下：(1)确定查找范围frot=0,end=N-10计算中项mid=(front+end)2o(2)若amid=x或fror2end,则结束查找；否则，向下继续。(3)若amidx,说明待查找的元素值只可能在比中项元素小的范围内，则把mid-1

12、的值赋给end,并重新计算mid,转去执行步骤(2)。算法流程图见图5.6。主要功能：在一个已排好序的有N个数的数组中查找数据#inc1ude#defineN8intmain()(intaN;intfront,end,mid,xJ；Primfr请输入已排好序的a数组元素”）；for(i=0;i=N-1;i+)给a数组输入有序的数据(scanf(,%dai);)Primf（请输入待查找的数X”）；scanf(u%dx);front=0;end=N-1;确定查找范围mid=(front+end)2;/计算中项，为查找作准备whi1e(frontend&amid!=x)(if(amidx)end=mid-1;/进入前半段查找mid=(front+end)2;)if(amid!=x)/输出查找结果Primf（没找到！）；e1sePrintfr找到了，在a%d项nmid);return0;)运行情况一次为：请输入已排好序的a数组元素：312243655687588/请输入待查找的数X24/找到了，在a项另一次运行情况为：请输入已排好序的a数组元素：312243655687588/请输入待查找的数X25/没找到！