第三节 数组的排序-【单招零距离】计算机专业综合（下）

单招零距离·计算机专业综合·下册 for(k=i+1;k<n;k+) if(a[k]<a[m]) m=k; t=a[i];a[i]=a[m];a[m]=t; } for(i=0;i<n;i+) printf("%d\t",ai]); printf(" "); 5.程序设计题：随机产生10个两位数，存入数组x中，找出其中的最大数和最小数，并将 最大数和首元素交换，将最小数和最后一个元素交换。 #include <stdio.h #include <stdlib.h #include <time.h #define N 10 int main() int x[N],i,max,min,pmax,pmin,t; srand((unsigned)time(NULL)); /关兴米*米******米米米米BEGIN**兴关兴***米米￥**米**/ 米米米*米米END米关关 第三节 数组的排序 知识体系 CY⊙ 顺序比较排序法（即比较即交换法） 选择法排序法（即比较后交换法） 数组的排序冒泡法排序法、优化的冒泡排序法 从前向后寻找插入位置 插入法排序法 从后向前寻找插入位置 ·142· 总复习方案·第六章数组 知识梳理 排序：排序就是按照某种规则对一组对象重新排列先后次序。排序的目的是便于以后的 查找。我们只要求掌握四种方法。程序段如下（共n个数据）： 1.顺序比较排序法： for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) if(aCi]aj]) {t=a[i];a[i]=a[j];a[j]=t;} 2.选择法排序法： for(i=0;i<n-1;i++) {p= for(j=i+1;j<n;j++) if(a[p]>a[j])p= if(p！=i) {x=a[p];a[p]=a[i];a[i]=x;} } 3.冒泡法排序法： for(i=0;i<n-1;i++) {for(j=0;j< j++) if( x=ai];a[]=a[j+1];a[j+1]=a];> } 优化的冒泡排序法： for(i=0;i<n-1;i++) flag=1; for(j=1;j< j++) if( {t=a0j];a[j]=a0-1];a0G-1]=t; flag-0; if( )break; 4.插入法排序法： (1)从前往后寻找插入位置 for(i=1;i<n;i++) {x=a[i]; for(j=0;j<i;j++) if(aj]x)break; for(k=i-1;k>=j;k--) ·143· 单招零距离·计算机专业综合·下册 a[k+1]=a[k]; a[j]=ls;//a[k+1]=ls; (2)从后往前寻找插入位置，边寻找边后移 for(i=1;i<n;i++) {x=a[i];p= while( {a[p+l]=a[p]; p-一； } a[p+1]=x; 典例精析 ©⊙ 【例1】阅读下列程序写结果： #include<stdio.h int main() int i,j,flag,n; inta[6]={5,7,4,3,8,6}; for(i=0;i<6;i++) printf("%4d",ai]); printf(" "); n=1;flag=1;i=0: while(i<5 &&flag==1) flag=0; for(j=0;j<6-i;j++) if(a[j]<a[j+1]) n=a[j];a[j]=a[j+1];a[j+1]=n;flag=1;) if(flag) {for(j=0;j<6;j++) printf("%4d",a]); printf(" "); } i+十； } 【分析】本题也是冒泡法排序，外循环是while,内循环是for,但设置了flag标志位。如 果已排序好flag为0。 【答案】程序运行结果为：876543 ·144· 总复习方案·第六章数组 【例2】下面程序的功能是对从键盘输入的10个数进行升序排序，请完善程序填空。 #define N 10 int main() int i,j,min,tem,a[N]; printf("please input ten num: "); for(i=0;i<N;i++) printf("al%d]=",i); scanf("%d",&ai]); printf(" "); for(i=0;i<N-1;i++) (1) for( (2)j<N;j++) if((3))min=j; tem=ai]; (4) ； amin]=tem; printf("After sorted "); for(i=0;i<N;i++) printf("%5d",a[i]); } 【分析】本题考查是的选择法排序，其基本思想是对个元素进行排序，需要进行9轮， 每轮比较过程中，选择一个最小的与第i个元素交换。 【答案】(1)min=i(2)j=i+1(3)a[min]>a[G](4)a[i]=a[min] 【例3】一个数组有10个元素已按降序排列好，现输入一个数x,要求插入到数组中，插 入后的数组仍按原规律排序。请填空： #include <stdio.h int main() {inti,p,x,n=11,a[11]; for(i=0;i<10;i++) a[i]=20-i; for(i=0;i<n-1;i++) printf("%3d",ai]); printf(" "); scanf("%d",); p=10;a[p]=x; p=p-1; while( {a[p+l]=a[p]; ·145· 单招零距离·计算机专业综合·下册 p； for(i=0;i<n;i++) printf("%3d",ai]); printf(" "); 【分析】这是一道插入元素的题，首先要找到所在的位置。采用设置陷阱的办法，先让最 后一位是x,然后再比较前一个元素的值，如果比前一个大，就后移。直到比前一个数小，然后 插入比刚小的数的位置之后。 【答案】(1)&x(2)p>=0&&a[p]<x(3)a[p+1]=x 【例4】下面程序的功能是用“插人法”对数组进行由大到小的排序。请填空使程序完 整、正确： #include<stdio.h int main() {inta[10]={191,3,6,4,11,7,25,13,89,10};inti,j,k; for(i=1:i<10;i++) {k=a[i]; j= while(j>=0 &.&k>a[j]) { j一； } =k; for(i=0;i<10;i++) printf("%d",ali); } 【分析】简单插入排序算法的基本思想是将数组处理一1，第k次处理时，前面的元素 插入到目前的位置。第k次的元素是这样插入的：在第k次处理时，前面的元a[0],a[l], …a[k一1]必定已排成了升序，将a[k]与a[k一1]，a[k一2]，…a[0]逐个比较（由后向前）， 若有aG门<a[k],则a[k]插入到a们之后，否则a[k]维持原位不变。 【答案】i-1aGj+1]=a[j门a[j+1] 巩固练习 1.阅读程序写结果： #include<stdio.h int main() {intc[10],i=0,j=0,k=0; inta[3]={5,29,30}; ·146· 总复习方案·第六章数组 intb[5]={12,24,26,37,48}; while(i<3&.&.j<5) if(a[i门>b[j]) {c[k]=bj];k++;j++;} else {c[k]=a[i];k++;i++;} while (i<3) {c[k]=a[i];i++;k++;} while(j<5) {c[k]=b[G];j++;k++;} for(i=0;i<k;i++) printf("%d\t",ci]); } 2.阅读程序写结果： #include<stdio.h define N 12 int main() { inta[N]={13,10,32,-90,78,54,34,21,44,88,120,-77}; inti,j,t; for(i=0;i<=N-2;i+=2; for(j=i+2;j<N;j+2) if(a[i门>aj]) t=ali];ai]=a];a[j]=t;> for(i=0;i=N-2;i+=2) printf("%d\t",ai]); printf(" "); 3.下面程序的功能是将字符数组中下标值为偶数的元素从小到大排列，其它元素不变。 请填空。 #include <stdio.h> #include <string.h int main() char a[]="clanguage",t; int i,j,k; k=strlen(a); for(i=0;i<=k-2;i+=2) for(j=i+2;j<k; ①) f(② t=a[i];a[i]=a];a]=t;) puts(a); ·147· 单招零距离·计算机专业综合·下册 printf(" "); } 4.有已排好序的字符串a,下面的程序是将字符串s中的每个字符按a中元素的规律插入 到a中。 #include<stdio.h int main() {char a[20]=“cehiknqtw”; char s[]=”fbla”; int i,k,j; for(k=0; ① ;k++) {j=0: while(s[k]>=a[j]&.&a!=\0) ② for(③ ④ a[j]=s[k]; puts(a); 5.程序设计题：随机产生10个二位正整数，按十位数降序排列，十位数相同的按个位数 升序排列。 #include <stdio.h> #include <stdlib.h #include <time.h int main() int i,j,x,y,m,n,k,a[10]; srand((unsigned)time(NULL)); /*米兴米米米米关关关关￥米米兴米BGIN米***米米米米米*米*米米米米￥/ /*兴兴兴米米米￥兴兴关米米关米米END米米米米米关米米米*米米￥米兴米米/ ·148· 总复习方案·第六章数组 拓展练习 C⑤ 1.阅读程序写结果： #include<stdio.h int main() {intx[]={1,3,5,7,2,4,6,0},i,j,k; for(i=0;i<3;i++) for(j=2;j>=i;j--) if(x[j+1]>x]) {k=xj];x[j]=x[j+1];x[G+1]=k;} for(i=0;i<3;i++) for(j=4;j<7-i;j++) if(x[G+1]>x[j]) {k=xj]:x[j]=x[j+1];x[G+1]=k;} for(i=0;i<3;i++) for(j=4;j<7-i;j++) if(x[j]>x[j+1]) {k=xj];x[j]=x[j+1];xj+1]=k;} for(i=0;i<8;i++) printf("%d\t",x); } 2.有一个已排好序的数组，现输人一个数，要求按原来的顺序规律将它插入到数组中。 算法是：假设排列顺序是从小到大，对输入的数，检查它在数组中哪一个数之后，然后将比这个 数大的数顺序后移一个位置，在空出的位置上将该数插入。请在程序中的空白处填上适当的 内容，使程序完整。 #include <stdio.h define N 10 int main() float a[N++1],x; int i,p; for (i=0;i<N;i++) {a[i]=3*i+1; printf("%5.1f",ai]); printf(" "); printf("Please a data: "); scanf("f",&x); for(i=0,p=N;i<N;i++) if (x<a[i]) ·149· 单招零距离·计算机专业综合·下册 {① break;) for(i=N-1; ② i--) a[i+1]=a[i]; a[p]=x; for (i=0; ③ ;i++) printf("%5.1f",ai]); f(i%5==0) printf(" "); 3.下面程序是将10个无序的整数30,12,52,78,90,28,83,47,55,16由小到大输出，请在 相应位置完善程序。 define N 10 int main() int i,j,x; static int a[N]={30,12,52,78,90,28,83,47,55,16}; printf(" the original numbers are: "); for(i=0;i<N;i++) printf("%4d",ari); for(i=1;i<=N-1;i++) {x=a[i];①； k:if(j>=0② {a[G+1]=a[j]; ③ ； goto k; ④ printf(" the sorted numbers are: "); for(i=0;i<N;i++) printf("%4d",a[i); printf(" "); 4.程序设计题：随机产生10个【29,92】互不相同的整数，放在数组a中，再从键盘上输入 两个整数m和n(且m<n),然后对数组a中第m到第n个数进行降序排序后输出。 #include <stdio.h #include <stdlib.h #include <time.h define N 10 int main() ·150· 总复习方案·第六章数组 米米米*BEGIN** 技能实践 1.程序填空题：将s所指字符串的正序和反序进行连接，形成一个新串放在t所指的数组中。 #include <stdio.h #include <string.h> int main() { char s[100]="abcd1234",t[100]="; inti,d; printf("%s ",s); d=① for(i=0;i<d; ② t[i门=s[i]; for(i=0;i<d;i+) t[d+i门=s[d-1-i门； ③ =\0; printf("%s ",t); 2.程序填空题：下列程序的功能是将N行N列二维数组中每一行的元素进行排序，第0 行从小到大排序，第1行从大到小排序，第2行从小到大排序，第3行从大到小排序，依此类 推。例如，当N=4时： 2341 1234 a=8657 8765 1112109 排序后：9101112 15141613 16151413 请认真阅读程序，在空白处填上程序所需的内容。 #include<stdio.h define N 4 int main() ·151【拓展练习】 　１．１　２　３　９　８　７　６　５　４　１０　１１　１２ 　２．１７１２ 　３．(１)rand()％２０１－１００　(２)max＝a[i][０] 　(３)j１＝j 　４．(１)(rand()％９０＋１０)∗k 　(２)i－－,k＝－k 　(３)sum＋a[j％２０] 　(４)p＝i 　(５)printf(“％d ”,a[i％２０]) 　(６)printf(“％d＋”,a[i％２０]) 　５．gets(str); for(i＝０;str[i];i＋＋) 　if(isalpha(str[i]) 　　A[toupper(str[i])－６５]＋＋; for(i＝０;i＜２６;i＋＋) 　printf(“次数[％c(％c)]＝％d\t”,６５＋i,９７＋ i,a[i]); 【技能实践】 　１．(１)strlen(a)　 (２)j＞len/２ 　２．(１)d[i]＝０ 　(２)b[i]/１０ 　(３)i∗１０,i∗１０＋９ 　３．(１)&x[i] 　(２)av＋x[i] 　(３)x[i]＝－１ 　(４)y[j＋＋]＝x[i] 　４．i＜１０改为i＜２ 　m＝０改为 m＝i 　a[k]＜a[m]改为(a[k]＞a[m] 　５．for(i＝０;i＜N;i＋＋) 　x[i]＝rand()％９０＋１０; printf(“SOURCEDATA: ”); for(i＝０;i＜N;i＋＋) 　printf(“％４d”,x[i]); max＝min＝x[０]; pmax＝pmin＝０; for(i＝０;i＜N;i＋＋) {　if(x[i]＞max)max＝x[i],pmax＝i; if(x[i]＜min)min＝x[i],pmin＝i; } t＝x[０];x[０]＝x[pmax];x[pmax]＝t; if(pmin＝＝０)pmin＝pmax; t＝x[N－１];x＝x[N－１]＝x[pmin];x[pmin]＝t; printf(“ LASTDATA: ”); for(i＝０;i＜N;i＋＋) 　printf(“％４d”,x[i]); 第三节　数组的排序 【知识梳理】 　２．i　j 　３．n－１－i　a[j]＞a[j＋１] n－i　a[j]＜a[j－１]　flag＝＝１ 　４．(２)i－１　p＞＝０&&x＜a[p] 【巩固练习】 　１．５　１２　２４　２６　２９　３０　３７　４８ 　２．１３　３２　３４　４４　７８　１２０ 　３．(１)j＋＝２　 (２)a[i]＞a[j] 　４．(１)s[k]　 (２)j＋＋ 　(３)i＝strlen(a);i＞＝j;i－－　(４)a[i＋１]＝a[i] 　５．for(i＝０;i＜１０;i＋＋) 　　a[i]＝rand()％９０＋１０; for(i＝０;i＜９;i＋＋) 　　for(j＝i＋１;j＜１０;j＋＋) 　　{　x＝a[i]％１０;m＝a[i]/１０; y＝a[j]％１０;n＝a[j]/１０; if(m＜n) {　k＝a[i];a[i]＝a[j];a[j]＝k;} if(m＝＝n&&x＞y) {　k＝a[i];a[i]＝a[j];a[j]＝k;} 　　} for(i＝０;i＜１０;i＋＋) 　　printf(＂％d,＂,a[i]); 【拓展练习】 　１．７　５　３　１　０　２　４　６ 　２．(１)p＝i　(２)i＞＝p　(３)i＜N＋１或i＜＝N 　３．(１)j＝i－１　(２)&&x＜a[j] 　(３)j－－　(４)a[j＋１]＝x 　４．inta[１０],i,j,m,n,t; srand((unsigned)time(NULL)); for(i＝０;i＜１０;i＋＋) {　a[i]＝rand()％９０＋１０; for(j＝０;j＜i;j＋＋) 　　if(a[i]＝＝a[j]) 　　{i－－;break;} } printf(“SORTEDBEFORE: ”); for(i＝０;i＜１０;i＋＋) 　　printf(＂％４d＂,a[i]); printf(“请输入整数 m 和n(m＜n):”); 􀅰３２􀅰 总复习方案􀅰参考答案 scanf(“％d％d”,&m,&n); for(i＝m－１;i＜n－１;i＋＋) 　　for(j＝i＋１;j＜＝n－１;j＋＋) if(a[i]＜a[j]) t＝a[i],a[i]＝a[j],a[j]＝t; printf(“ SORTEDAFTER: ”); for(i＝０;i＜１０;i＋＋) 　　printf(＂％４d＂,a[i]); 【技能实践】 　１．(１)strlen(s)　(２)i＋＋　(３)t[i＋d] 　２．(１)j＋１　 (２)i％２　 (３)t＝a[i][j] 　(４)printf(“ ”) 　３．j＜N改为j＜N－１－i 　a[j]＜a[j＋１]改为strcmp(a[j],a[j＋１])＜０ 　b＝a[j],a[j]＝a[j＋１],a[j＋１]＝b改为:strcpy(b, a[j]),strcpy(a[j],a[j＋１]),strcpy(a[j＋１],b); 　４．(１)for(i＝j＋１;i＜n－１;i＋＋ )改为for(i＝ j＋１;i＜n;i＋＋ ) 　(２)if(a[p]＞a[i])t＝i;改为if(a[p]＞a[i])p＝i; 　(３)printf(“％d“,&a[j]);改为printf(“％d“,&a[j]); 　５．charx[５];floatc; for(i＝０;i＜n－１;i＋＋) 　　for(j＝i＋１;j＜n;j＋＋) if(b[i]＞b[j]) {　c＝b[i];b[i]＝b[j];b[j]＝c; strcpy(x,a[i]);strcpy(a[i],a[j]); strcpy(a[j],x); } for(i＝０;i＜n;i＋＋) 　　printf(＂％s,％．２f ＂,a[i],b[i]); 第四节　数组的查找 【知识梳理】 　２．有序 (l＋h)/２　mid＋１ 【巩固练习】 　１．(１)left＜＝right&&flag＝＝０ 　(２)(left＋right)/２ 　(３)flag＝１ 　(４)flag 【拓展练习】 　１．(１)if(a[i]＝＝a[j])i－－ 　(２)j＝０;j＜２０－i;j＋＋ 　(３)l＜＝r&&f＝＝０ 　(４)p＝m 【技能实践】 　１．(１)left＝mid＋１; 　(２)elseif(m＜a[mid]) 　(３)right＝mid－１; 　２．srand((unsigned)time(NULL)); for(i＝０;i＜１０;i＋＋) {　a[i]＝rand()％９１＋１０; b[i]＝i; } for(i＝０;i＜１０;i＋＋) 　　printf(＂％d\t＂,a[i]); for(i＝０;i＜９;i＋＋) 　　for(j＝０;j＜９－i;j＋＋) 　　　if(a[j]＞a[j＋１]) {　k＝a[j];a[j]＝a[j＋１];a[j＋１]＝k; t＝b[j];b[j]＝b[j＋１];b[j＋１]＝t; } scanf(＂％d＂,&x); l＝０;r＝９;f＝０; while(l＜＝r&&f＝＝０) {　m＝(l＋r)/２; if(x＝＝a[m]){f＝１;p＝m;} if(x＞a[m])l＝m＋１; if(x＜a[m])r＝m－１; } if(f＝＝１) 　　printf(＂值为％d,是原数组中的第％d个.＂, x,p＋１); else 　　printf(＂NotFound!＂); 第五节　数组元素的复制、移动、插入、删除 【巩固练习】 　１．S＝１２３ 　２．１０　１１　１２　１３　１４　１５　１６　１７　１８　１９ １０　１１　１６　１７　１８　１９　１２　１３　１４　１５ 　３．１２　４５　６８　７８　６７　２３　７７　８８ 【拓展练习】 　１．２３　４５　６７　１２　３３　７８　９　９０　７７ １３　４５　３３　９０　６６　９９　１００　－６０ ４５　３　９０ k＝３ 　２．(１)i＋＋　(２)while(a[j]％２＝＝０) 　３．/∗从前往后找插入位置∗/ for(i＝０;i＜n;i＋＋) 􀅰４２􀅰 单招零距离􀅰计算机专业综合􀅰下册