程序设计培训讲义5：排序与查找

程序设计培训五排序与查找一、顺序查找基本思想：从第一个元素或最后一个元素开始，逐个把数据元素的关键字值和给定值比较，若某个元素的关键字值和给定值相等，则查找成功。否则，若直至第n个数据元素都不相等，说明不存在满足条件的数据元素，查找失败。算法特点：算法简单，既适用于以顺序存储结构组织的查找表的查找，也适用于以链式存储结构组织的查找表的查找；但执行效率低。#includestdio.hintsearch(inta[],intn,intk)/*a查找表,n表长,k关键字*/{inti;for(i=0;in;i++)if(k==a[i])return(i+1);return0;}voidmain(){intx,t，a[9]={10,31,12,42,35,76,16,18,29,};scanf(%d,&x);t=search(a,9,x);if(t==0)printf(Notfound!\n);elseprintf(%d\n,t);}//改进的顺序查找#includestdio.hintsearch(inta[],intn,intk)/*a查找表,n表长,k关键字*/{inti=n;a[0]=k;while(a[i]!=k)i--;returni;}voidmain(){inta[10]={0,10,31,12,42,35,76,16,18,29,};intx,t;scanf(%d,&x);t=search(a,9,x);if(t==0)printf(Notfound!\n);elseprintf(%d\n,t);}二、折半(二分)查找基本思想：如果查找表中的数据元素按关键字有序（假设递增有序），则在查找时，可不必逐个顺序比较，而采用跳跃的方式——先与“中间位置”的数据元素关键字比较，若相等，则查找成功；若给定值大于“中间位置”的关键字，则在查找表的后半部继续进行二分查找，否则在前半部进行二分查找。算法特点：仅适用于以顺序存储结构组织有序表的查找。先确定待查元素所在区域，然后逐步缩小区域，直到查找成功或失败为止。假设：待查元素所在区域的下界为low，上界为hig，则中间位置mid=(low+hig)/21、若此元素关键字值等于给定值，则查找成功2、若此元素关键字值大于给定值，则在区域(mid+1)与high内进行二分查找3、若此元素关键字值小于给定值，则在区域low与(mid-1)内进行二分查找//非递归算法intbin_search(inta[],intn,intk){intlow,high,mid;low=0;high=n-1;while(low=high){mid=(low+high)/2;if(ka[mid])high=mid-1;elseif(ka[mid])low=mid+1;elsereturnmid;}return-1;}//递归算法intbin_search(inta[],intlow,inthigh,intk){intmid=(low+high)/2;if(lowhigh)return-1;elseif(k==a[mid])returnmid;elseif(ka[mid])bin_search(a,mid+1,high,k);elsebin_search(a,low,mid-1,k);}例1、2006年湖南人文科技学院预赛试题给定整数a1,a2,a3,……an（其中有负数），求整数中的最大子序列和。为了方便起见，如果所有整数为负数，则最大子序列和为0。例如：对于-2、11、-4、13、-5、-2，最大子序列和为20（11-4+13）。方法1：二分法，时间复杂度为O（nlog2n）其余方法详见：程序设计培训讲义7：数组#includestdio.h#defineN100inta[N]={-2,11,-4,13,-5,-2};intmax3(intx,inty,intz){intm;m=xy?x:y;returnmz?m:z;}voidmain(){intmaxsub(inta[],intleft,intright);printf(Maxsub=%d\n,maxsub(a,0,3));}intmaxsub(inta[],intleft,intright){inti,mid,maxleft,maxright,m1,m2,max1,max2;if(left==right)if(a[left]0)returna[left];elsereturn0;mid=(left+right)/2;maxleft=maxsub(a,left,mid);maxright=maxsub(a,mid+1,right);for(m1=0,max1=0,i=mid;i=left;i--){m1=m1+a[i];if(m1max1)max1=m1;}for(m2=0,max2=0,i=mid+1;i=right;i++){m2=m2+a[i];if(m2max2)max2=m2;}returnmax3(maxleft,maxright,max1+max2);}三、排序算法分类插入排序类直接插入排序、折半插入排序、希尔排序选择排序类直接选择排序、树型选择排序、堆排序交换排序类冒泡排序（称直接交换排序）、快速排序归并排序类二路归并四、非递归排序算法1、插入排序把n个数据元素的序列分成两部分：{R1,...,Ri-1}为已排好序的有序部分{Ri,Ri+1,...,Rn}为未排序部分把未排序部分的第1个元素Ri依次与R1,...,Ri-1比较，并插入到有序部分的合适位置上，使得{R1,...,Ri}变为新的有序部分。初始时，令i=2。因为一个元素自然有序，故{R1}自然成为一个有序部分，未排序部分是{R2,...,Rn}，然后依次将R2,R3,...,Rn插入到有序部分中去，就可得整个有序序列初始关键字:[49][38659776132749]i=2:[3849][659776132749]i=3:[384965][9776132749]i=4:[38496597][76132749]i=6:[133849657697][2749]i=7:[13273849657697][49]i=8:[1327384949657697]i=5:[3849657697][132749]无序有序voidinsert(inta[],intn)//对数组a中的元素a[1]、a[2]……a[n]排序{inti,j;for(i=2;i=n;i++)if(a[i]a[i-1]){a[0]=a[i];j=i-1;while(a[0]a[j]){a[j+1]=a[j];j--;}a[j+1]=a[0];}}2、Shell排序将整个待排序数据按一个步长序列d1,d2,d3,…,dt分割成若干个较小的数据。对步长dk所分割的若干子文件分别进行直接插入排序在文件达到基本有序时，再对全文件进行一次直接插入排序12345678910初始关键字49386597761327495504取步长为5分割数据13386597764927495504132765977649384955041327499776493865550413274955764938659704一趟排序结果13274955044938659776取步长为3分割数据:二趟排序结果[0413]4938274955659776取步长为1即对整个数据进行插入排序[041349]38274955659776[04133849]274955659776[0413273849]4955659776三趟排序结果04132738494955657697130449382749556597761327493804495565977613044938274955659776//希尔排序//对数组a中的元素a[1]、a[2]……a[n-1]排序voidshell(inta[],intn){inti,j,d;d=n/2;while(d=1){for(i=d+1;i=n;i++){a[0]=a[i];j=i-d;while(j0&&a[0]a[j]){a[j+d]=a[j];j=j-d;}a[j+d]=a[0];}d=d/2;}}3、直接选择排序第一趟排序是在无序的{R1,R2,R3,...,Rn}按排序码选出最小的元素，将它与R1交换。第二趟排序是在无序的{R2,R3,...,Rn}中选出最小的元素，将它与R2交换。第i趟排序时{R1,R2,R3,...,Ri-1}已排好序，在当前无序的{Ri,...,Rn}中再选出最小的元素，将它与Ri元素交换，使{R1,R2,R3,...,Ri}成为有序……………经过n-1趟排序后，整个数据元素序列就递增有序。//直接选择排序//对数组a中的元素a[0]、a[1]……a[n-1]排序voidsort(inta[],intn){inti,j,t,min;for(i=0;in-1;i++){min=i;//寻找当前最小元素的下标存入minfor(j=i+1;jn;j++)if(a[j]a[min])min=j;t=a[min];a[min]=a[i];a[i]=t;}}4、冒泡排序(直接交换排序)第一趟每次进行相邻两个元素关键字的比较，如不符合次序立即交换,这样关键值大的（或小的）就会象冒气泡一样逐步升起。算法思想：先将r[n]与r[n-1]比较，若r[n]r[n-1]则互相交换。再比较r[n-1]和r[n-2]，依次类推，直到r[t]与r[1]比较（交换）把关键字较小的记录移至最前，完成一趟排序。然后对余下的r(2)~r(n)的n-1个记录重复上述操作。//冒泡排序1：大数向后移//对数组a中的元素a[0]、a[1]……a[n-1]排序voidsort(inta[],intn){inti,j,t;//大数向后移，外循环一次，//将当前的最大数移到a[10-i]上for(i=0;in-1;i++)for(j=0;jn-i;j++)if(a[j]a[j+1]){t=a[j];a[j]=a[j+1];a[j+1]=t;}}//冒泡排序2：小数向前移//对数组a中的元素a[0]、a[1]……a[n-1]排序voidsort(inta[],intn){inti,j,t;//小数向前移，外循环一次//将当前的最小数移到a[i]上for(i=0;in-1;i++)for(j=i+1;jn;j++)if(a[j]a[i]){t=a[j];a[j]=a[i];a[i]=t;}}//冒泡排序3：改进的冒泡排序//对数组a中的元素a[0]、a[1]……a[n-1]排序voidsort(inta[],intn){inti,j,t,bz=1;for(i=0;in-1&&bz;i++){bz=0;//表示不需要继续排序for(j=0;jn-i-1;j++)if(a[j]a[j+1]){t=a[j];a[j]=a[j+1];a[j+1]=t;bz=1;/*存在交换，需要继续排序*/}}}//冒泡排序4：改进的冒泡排序//对数组a中的元素a[0]、a[1]……a[n-1]排序voidsort(inta[],intn){intk,j,t,m=n-1;while(m0){//小数向前移，将当前的最小数移到a[i]上for(k=j=0;jm;j++)if(a[j]a[j+1]){t=a[j];a[j]=a[j+1];a[j+1]=t;k=j;}//记下最后一次交换的元素的下标到km=k;//也可以为m=m-1}}5、快速排序快速排序又称分区交换排序，是对冒泡排序的一种改进，是目前内部排序中比较快的方法。它通过分步排序来完成整个表的排序。这种方法的每一步都把要排序表的第一个元素（或者是中间位置的元素）放到它在表中的最终位置，同时在这个元素的前面和后面各形成一个子表。在前子表中的所有元素的关键字都比该元素的关键字小，而在后子表中的都比它大。此后再对每个子表做同样的操作