1、程序设计培训五程序设计培训五排序与查找排序与查找一、顺序查找一、顺序查找基本思想：从第一个元素或最后一个元素开始，逐个把数据元素的关键字值和给定值比较，若某个元素的关键字值和给定值相等，则查找成功。否则，若直至第n个数据元素都不相等，说明不存在满足条件的数据元素，查找失败。算法特点：算法简单，既适用于以顺序存储结构组织的查找表的查找，也适用于以链式存储结构组织的查找表的查找；但执行效率低。#includeint search(int a,int n,int k)/*a查找表,n表长,k关键字*/int i;for(i=0;in;i+)if(k=ai)return(i+1);return 0;v
2、oid main()int x,t，a9=10,31,12,42,35,76,16,18,29,;scanf(%d,&x);t=search(a,9,x);if(t=0)printf(Not found!n);else printf(%dn,t);/改进的顺序查找#includeint search(int a,int n,int k)/*a查找表,n表长,k关键字*/int i=n;a0=k;while(ai!=k)i-;return i;void main()int a10=0,10,31,12,42,35,76,16,18,29,;int x,t;scanf(%d,&x);t=searc
3、h(a,9,x);if(t=0)printf(Not found!n);else printf(%dn,t);二、折半二、折半(二分二分)查找查找基本思想：如果查找表中的数据元素按关键字有序（假设递增有序），则在查找时，可不必逐个顺序比较，而采用跳跃的方式先与“中间位置”的数据元素关键字比较，若相等，则查找成功；若给定值大于“中间位置”的关键字，则在查找表的后半部继续进行二分查找，否则在前半部进行二分查找。算法特点：仅适用于以顺序存储结构组织有序表的查找。先确定待查元素所在区域，然后逐步缩小区域，直到查找成功或失败为止。假设：待查元素所在区域的下界为low，上界为hig，则中间位置mid=(l
4、ow+hig)/2 1、若此元素关键字值等于给定值，则查找成功 2、若此元素关键字值大于给定值，则在区域(mid+1)与high 内进行二分查找 3、若此元素关键字值小于给定值，则在区域low与(mid-1)内进行二分查找/非递归算法int bin_search(int a,int n,int k)int low,high,mid;low=0;high=n-1;while(low=high)mid=(low+high)/2;if(k amid)low=mid+1;else return mid;return -1;/递归算法int bin_search(int a,int low,int hi
5、gh,int k)int mid=(low+high)/2;if(lowhigh)return-1;else if(k=amid)return mid;else if (k amid)bin_search(a,mid+1,high,k);else bin_search(a,low,mid-1,k);例例1、2006年湖南人文科技学院预赛试题年湖南人文科技学院预赛试题给定整数给定整数 a1,a2,a3,an（其中有负数），求整数中的（其中有负数），求整数中的最大子序列和。为了方便起见，如果所有整数为负数，则最最大子序列和。为了方便起见，如果所有整数为负数，则最大子序列和为大子序列和为0。例如：对
6、于。例如：对于-2、11、-4、13、-5、-2，最大，最大子序列和为子序列和为20（11-4+13）。）。方法方法1：二分法，时间复杂度为：二分法，时间复杂度为O（nlog2n）其余方法详见：其余方法详见：程序设计培训讲义程序设计培训讲义7：数组：数组#include#define N 100int aN=-2,11,-4,13,-5,-2;int max3(int x,int y,int z)int m;m=xy?x:y;return mz?m:z;void main()int maxsub(int a,int left,int right);printf(Maxsub=%dn,maxsu
7、b(a,0,3);int maxsub(int a,int left,int right)int i,mid,maxleft,maxright,m1,m2,max1,max2;if(left=right)if(aleft0)return aleft;else return 0;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+ai;if(m1 max1)max1=m1;for(m2=0,max2=0,i=mid+1;
8、i max2)max2=m2;return max3(maxleft,maxright,max1+max2);三、排序算法分类三、排序算法分类 插入排序类直接插入排序、折半插入排序、希尔排序选择排序类直接选择排序、树型选择排序、堆排序交换排序类冒泡排序（称直接交换排序）、快速排序归并排序类二路归并四、非递归排序算法四、非递归排序算法 把n个数据元素的序列分成两部分：R1,.,Ri-1为已排好序的有序部分 Ri,Ri+1,.,Rn 为未排序部分 把未排序部分的第1个元素Ri依次与R1,.,Ri-1比较，并插入到有序部分的合适位置上，使得 R1,.,Ri 变为新的有序部分。初始时，令i=2。因为一
9、个元素自然有序，故R1 自然成为一个有序部分，未排序部分是R2,.,Rn，然后依次将R2,R3,.,Rn插入到有序部分中去，就可得整个有序序列初始关键字:49 38 65 97 76 13 27 49i=2:38 49 65 97 76 13 27 49i=3:38 49 65 97 76 13 27 49i=4:38 49 65 97 76 13 27 49i=6:13 38 49 65 76 97 27 49i=7:13 27 38 49 65 76 97 49i=8:13 27 38 49 49 65 76 97i=5:38 49 65 76 97 13 27 49无序有序void in
10、sert(int a,int n)/对数组a中的元素a1、a2an 排序int i,j;for(i=2;i=n;i+)if(aiai-1)a0=ai;j=i-1;while(a0=1)for(i=d+1;i0&a0aj)aj+d=aj;j=j-d;aj+d=a0;d=d/2;第一趟排序是在无序的R1,R2,R3,.,Rn按排序码选出最小的元素，将它与R1交换。第二趟排序是在无序的R2,R3,.,Rn中选出最小的元素，将它与R2交换。第i趟排序时R1,R2,R3,.,Ri-1已排好序，在当前无序的Ri,.,Rn中再选出最小的元素，将它与Ri元素交换，使R1,R2,R3,.,Ri成为有序 经过n-
11、1趟排序后，整个数据元素序列就递增有序。/直接选择排序/对数组a中的元素a0、a1an-1 排序void sort(int a,int n)int i,j,t,min;for(i=0;in-1;i+)min=i;/寻找当前最小元素的下标存入min for(j=i+1;jn;j+)if(ajamin)min=j;t=amin;amin=ai;ai=t;第一趟每次进行相邻两个元素关键字的比较，如不符合次序立即交换,这样关键值大的（或小的）就会象冒气泡一样逐步升起。算法思想：算法思想：先将rn与rn-1比较，若rnrn-1则互相交换。再比较rn-1和rn-2，依次类推，直到rt与r1比较（交换）把关
12、键字较小的记录移至最前，完成一趟排序。然后对余下的r(2)r(n)的n-1个记录重复上述操作。/冒泡排序1：大数向后移/对数组a中的元素a0、a1an-1 排序void sort(int a,int n)int i,j,t;/大数向后移，外循环一次，/将当前的最大数移到a10-i上for(i=0;in-1;i+)for(j=0;jaj+1)t=aj;aj=aj+1;aj+1=t;/冒泡排序2：小数向前移/对数组a中的元素a0、a1an-1 排序void sort(int a,int n)int i,j,t;/小数向前移，外循环一次/将当前的最小数移到ai上for(i=0;in-1;i+)for
13、(j=i+1;jn;j+)if(ajai)t=aj;aj=ai;ai=t;/冒泡排序3：改进的冒泡排序/对数组a中的元素a0、a1an-1 排序void sort(int a,int n)int i,j,t,bz=1;for(i=0;in-1&bz;i+)bz=0;/表示不需要继续排序 for(j=0;jaj+1)t=aj;aj=aj+1;aj+1=t;bz=1;/*存在交换，需要继续排序*/冒泡排序4：改进的冒泡排序/对数组a中的元素a0、a1an-1 排序void sort(int a,int n)int k,j,t,m=n-1;while(m0)/小数向前移，将当前的最小数移到ai上 f
14、or(k=j=0;jaj+1)t=aj;aj=aj+1;aj+1=t;k=j;/记下最后一次交换的元素的下标 到km=k;/也可以为 m=m-1 快速排序又称分区交换排序，是对冒泡排序的一种改进，是目前内部排序中比较快的方法。它通过分步排序来完成整个表的排序。这种方法的每一步都把要排序表的第一个元素（或者是中间位置的元素）放到它在表中的最终位置，同时在这个元素的前面和后面各形成一个子表。在前子表中的所有元素的关键字都比该元素的关键字小，而在后子表中的都比它大。此后再对每个子表做同样的操作，直到最后每个子表都只有一个元素，排序结束初始关键字序列:49 38 65 97 76 13 27 4949
15、 38 65 97 76 13 27 4927 38 65 97 76 13 49 4927 38 49 97 76 13 65 4927 38 13 97 76 49 65 4927 38 13 49 76 97 65 49i1j1ij1i1i1j1i1j1i1j1i1j1/快速排序1：以第1个元素来分区间/对数组a中的元素aleft、aleft+1aright 排序void sort(int a,int left,int right)int i,j,t;i=left;j=right;t=ai;do while(t=aj&ij)j-;/从后向前搜索 if(ij)ai=aj;i+;while(
16、ai=t&ij)i+;/从前向后搜索 if(ij)aj=ai;j-;while(i!=j);ai=t;/把t即最先的ai放到此次的适当位置if(lefti)qsort(a,i+1,right);/排序后半部分/快速排序2：以中间元素来分区间/对数组a中的元素aleft、aleft+1aright 排序void sort(int a,int left,int right)int i,j,x,y;i=left;j=right;x=a(left+right)/2;/用中间元素 do while(aix&ix&jleft)j-;/找一个比x小的元素aj if(i=j)y=aj;aj=ai;ai=y;i
17、+;j-;while(i=j);if(lefti)sort(a,i+1,right);/排序后半部分归并的含义是把两个（或两个以上）有序的序列合并为一个有序的序列。将有n个元素的原始序列看作n个有序子序列，每个子序列的长度为1然后从第一个子序列开始，把相邻的子序列两两合并，得到n/2个长度为2或1的子序列，这一过程称为一次归并排序。对第一次归并排序后的n/2个子序列采用上述方法，继续顺序归并，如此重复，当最后得到长度为n的一个子序列时，该子序列便是原始序列归并排序后的有序序列。void merge(int r,int r1,int low,int m,int h)/*rlow.m及rm+1.h
18、分别有序,归并后置于r1中*/int i=low,j=m+1,k=low;/*i和j是r的指示器*/*i的取值从l到m,j的取值从m+1到h;k是r1的指示器*/while(i=m&j=h)if(rim)/*前部分结束*/while(j=h)/*将后部分复制到r1*/r1k=rj;j+;k+;else/*后部分结束*/while(i2*len)merge(r,r1,p,p+len-1,p+2*len-1);p+=2*len;/p向后移动2*l,准备下一次合并if(n-p+1len)/一个长度为len的部分与一个长度小于len的部分合并merge(r,r1,p,p+len-1,n);else /
19、只剩下一个长度不大于len的部分,将其复制到r1for(;p=n;p+)r1p=rp;void mergesort(int r,int r1,int n)/*对r中数据元素进行归并,结果仍放在r中*/int len=1;while(lenn)mergepass(r,r1,n,len);len*=2;/*从r归并到r1*/mergepass(r1,r,n,len);len*=2;/*从r1归并到r*/void main()int a11=0,75,87,68,92,88,61,77,96,80,72;/*a0元素不计入元素个数*/int a110,n=10,i;mergesort(a,a1,n)
20、;for(i=1;i=n;i+)printf(%6d,ai);归并排序的非递归算法归并排序的非递归算法2：void merge(int r,int r1,int low,int m,int h)/*rlow.m及rm+1.h分别有序,归并后置于r1中*/int i=low,j=m+1,k=low;while(i=m&j=h)if(rim)/*前部分结束*/while(j=h)/*将后部分复制到r1*/r1k=rj;j+;k+;else/*后部分结束*/while(i=m)/*将前部分复制到r1*/r1k=ri;i+;k+;for(i=low;i=h;i+)ri=r1i;返回递归函数void s
21、ort(int a,int b,int n)/自底向上排序/将数组a0,a1,an-1排序/利用数组b 过渡,b与a的长度相等int i,len;len=1;while(lenn)i=0;while(i+2*len=n)merge(a,b,i,i+len-1,i+2*len-1);i=i+2*len;if(i+lenn)merge(a,b,i,i+len-1,n-1);len=len*2;利用完全二叉树对数组排序：1、将一个无序序列建成堆，2、输入出顶点元素后，调整并重建堆，3、重复2直至全部元素都输出完毕。void sift(int p,int i,int n)/调整数组p的第i元素,n为数
22、组长度 int j,t;t=pi;j=2*(i+1)-1;/左子树 while(j=n)if(jn)&(pjpj+1)j+;/右子树 if(t=0;i-)/初始建堆 sift(p,i,n-1);for(i=n-1;i=1;i-)/重建堆 t=p0;p0=pi;pi=t;sift(p,0,i-1);void main()int i,a10=75,87,68,92,88,61,77,96,80,72;sort(a,10);for(i=0;i10;i+)printf(%d,ai);五、递归排序算法五、递归排序算法1、选择排序的递归算法、选择排序的递归算法/对数组a中的元素aleft,aleft+1a
23、right排序void sort(int a,int left,int right)int min,j,t;if(leftright)min=left;for(j=left+1;j=right;j+)if(aj amin)min=j;if(left!=min)t=aleft;aleft=amin;amin=t;sort(a,left+1,right);2、冒泡排序的递归算法、冒泡排序的递归算法/对数组a中的元素aleft,aleft+1aright排序void sort(int a,int left,int right)int min,j,t;if(leftright)min=left;for
24、(j=left+1;j=right;j+)if(aj amin)min=j;if(left!=min)t=aleft;aleft=amin;amin=t;sort(a,left+1,right);3、插入排序的递归算法、插入排序的递归算法/对数组a中的元素aleft,aleft+1aright排序void sort(int a,int left,int right)int j,x;if(left=0&ajx)aj+1=aj;j-;aj+1=x;4、归并排序的递归算法、归并排序的递归算法void sort(int a,int b,int low,int high)/将数组alow,alow+1,ahigh排序/利用数组b 过渡,b与a的长度相等int mid;if(lowhigh)mid=(low+high)/2;sort(a,b,low,mid);sort(a,b,mid+1,high);merge(a,b,low,mid,high);（merge函数）函数）
