选择排序的的递归排序.doc

10月2日上课流程：一、 冒泡排序、选择排序、堆排序（40分钟）二、 指针串讲P157-170（10分钟）三、 指针练习（10分钟）四、 文件串讲（15分钟）五、 文件练习（50分钟）选择排序的的递归排序P155插入排序P66二分查找p70传统的冒泡排序法是这样操作：从前往后，依次比较两个相邻的元素，如果逆序则交换这两个元素值，然后继续往后操作；到了数据尾部时，就找出了一个最大值（或最小值）。然后重复上面的操作n-1次（n为元素个数）。 相关的改进办法：按照上面的办法来操作的话，第一次扫描把最大数（或最小数）放到最后面的位置，第二次扫描时其实只需要扫描到倒数第二个位置就可以了，因为最后一个位置已经不需要判断了，以后的操作都是类似的。这样可以减小程序运行时间。双向走动法（以升序排序为例）：首先，从前往后扫描，如果相邻两个元素前面的比后面的大，则交换，继续往后；到尾部以后，再往回走，如果后面的元素比前面的小，则交换，继续往前走；到了头以后，再往后走。为了减少走动次数，我们用变量start表示头，用变量end表示尾。每找到一个剩余数据中的最大数，就让变量end减1，每找到一个剩余数据中的最小数，就让变量start加1。循环条件为start=end。#include#include #include void maopao(int source,int n)int start=0,end=n-1;int i;while(start=end)/*如果还有元素没有确定其位置*/for(i=start;isourcei+1)int t;t=sourcei;sourcei=sourcei+1;sourcei+1=t; printf(qian pai xu:n);for(i=0;istart;i-)/*寻找剩余元素的最小元素*/if(sourceisourcei-1)int t;t=sourcei;sourcei=sourcei-1;sourcei-1=t;start+;/*找到一个最小数*/ printf(hou pai xu:n);for(i=0;i10;i+) printf(%d ,sourcei);printf(n);void output(int data,int n)int i;for(i=0;in;i+)if(i%10=0)printf(n);printf(%4d,datai);printf(n);int check(int data,int n)/*检查结果数据是否已升序排列*/int i;for(i=0;idatai+1)return 0;return 1;main()int data10; int i; srand(time(NULL); for(i=0;i10;i+) datai=random(10); printf(nThe original data is:n); output(data,10); maopao(data,10); printf(nAfter sort:n); output(data,10); printf(n); if(check(data,10)=1) printf(nRight.); else printf(nWrong.); getch(); system(pause);The original data is: 1 7 0 2 1 7 1 6 7 2qian pai xu:1 0 2 1 7 1 6 7 2 7qian pai xu:0 1 1 1 2 2 6 7 7 7qian pai xu:0 1 1 1 2 2 6 7 7 7qian pai xu:0 1 1 1 2 2 6 7 7 7qian pai xu:0 1 1 1 2 2 6 7 7 7hou pai xu:0 1 1 1 2 2 6 7 7 7After sort: 0 1 1 1 2 2 6 7 7 7Right.Press any key to continue . . .堆排序程序#include conio.h#include stdio.hchar ch=q,A,S,O,R,T,E,X,A,M,P,L,E;int n=12;void shift(int k,int n)/*建造堆的过程*/ char v; int j; v=chk;j=k+k; while(j=n) if(jn) & (chjchj+1) j+;/*找出其左右孩子树中较大的一个*/ if(v0;k-) shift(k,n);/*对从chn/2结点构成的子树开始调整堆,*/ /*直至结点ch0形成整个结点序列的堆*/ printf(No.1:); for(k=1;k0;k-)/*堆排序,循环次数为n-1*/ tmp=ch1;ch1=chk;chk=tmp;/*对调结点*/ shift(1,k-1);/*对调后,重新调整堆*/ main() int k; hpsrt(); printf(No.2:); for(k=1;k=n;k+) putchar(chk); putchar(n); system(pause); 直接插入排序：#include#define MAX 100void main()int dMAX; int s,q,t,n,i; printf(How many nodes?n); scanf(%d,&n); for(s=0;sn;s+) printf(Input No %d valuen,s+1); scanf(%d,&ds);s=1;while(s=0&tdq;q-) dq+1=dq;/*结点右移一个位置*/ printf(t=%dn,t);printf(q=%dn,q); dq+1=t;/*q的值为-1,则不存在某个值比t小,否则,至少存在q+1个值比t小*/ s+; for(i=0;in;i+) printf(%d,di);printf(n); for(s=0;sn;s+) printf(%d ,ds);printf(n);system(pause);希尔排序#include#define MAX 100void xier_sort();void main()int dMAX,ddMAX; int s,q,t,n,i; printf(How many nodes?n); scanf(%d,&n); for(s=0;s1)ddq+=s/2;s=s/2;/*最后一个增量为1*/xier_sort(d,n,dd,q);for(s=0;sn;s+) printf(%d ,ds);printf(n);system(pause);void xier_sort(int d,int n,int dd,int t)int s,x,k,h,i; int y; for(s=0;st;s+) h=dds; for(x=h;x=0 & ydk;k-=h) dk+h=dk; dk+h=y; for(i=0;in;i+) printf(%d ,di); printf(n); 练习：一.填空题（将正确的答案填在相应的空中）1. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较 次。 2. 在利用快速排序方法对一组记录（54， 38， 96， 23， 15， 72， 60， 45， 83）进行快速排序时，递归调用而使用的栈所能达到的最大深度为 ，共需递归调用的次数为 ，其中第二次递归调用是对 一组记录进行快速排序。 3. 在堆排序，快速排序和归并排序中，若只从存储空间考虑，则应首先选取 方法，其次选取 方法，最后选取 方法；若只从排序结果的稳定性考虑，则应选取 方法；若只从平均情况下排序最快考虑，则应选取 方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取 方法。 4. 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有 。 5. 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是 ，需要内存容量最多的是 . 6. 在堆排序和快速排序中，若原始记录接近正序或反序，则选用 ，若原始记录无序，则最好选用 。 7. 在插入和选择排序中，若初始数据基本正序，则选用 ；若初始数据基本反序，则选用 。 8. 对n个元素的序列进行起泡排序时，最少的比较次数是 。 答案1：32：2 4 （23，38，15）3：堆排序快速排序归并排序归并排序快速排序难排序4：希尔排序、选择排序、快速排序和堆排序5：快速排序基数排序6：堆排序快速排序7：插入排序选择排序8：n1二.综合题1. 已知序列17，18，60，40，7，32，73，65，85，请给出采用起泡排序法对该序列作升序排序时的每一趟的结果。 2. 已知序列503，87，512，61，908，170，897，275，653，462，请给出采用快速排序法对该序列作升序排序时的每一趟的结果。 3. 已知序列503，87，512，61，908，170，897，275，653，462，请给出采用堆排序法对该序列作升序排序时的每一趟的结果。 4. 已知序列503，87，512，61，908，170，897，275，653，462，请给出采用基数排序法对该序列作升序排序时的每一趟的结果。 5. 已知序列503，17，512，908，170，897，275，653，426，154，509，612，677，765，703，94，请给出采用希尔排序法（d1=8）对该序列作升序排序时的每一趟的结果。 6. 已知序列70，83，100，65，10，32，7，9，请给出采用插入排序法对该序列作升序排序时的每一趟的结果。 7. 已知序列10，18，4，3，6，12，1，9，18，8，请给出采用Shell排序法对该序列做升序排序时每一趟的结果。 8. 已知序列10，18，4，3，6，12，l，9，18，8，请给出采用归并排序法对该序列作升序排序时的每一趟的结果。 1答案：依题意，采用起泡排序法排序的各趟的结果如下：初始：17，18，60，40，7，32，73，65，851趟：17，18，40，7，32，60，65，73，852趟：17，18，7，32，40，60，65，73，853趟：17，7，18，32，40，60，65，73，854趟：7，17，18，32，40，60，65，73，855趟：7，17，18，32，40，60，65，73，85第5趟无元素交换，则排序结束。2答案依题意，采用快速排序法排序的各趟的结果如下：初始：503，87，512，61，908，170，897，275，653，4621趟：462，87，275，61，170 503897，908，653，5122趟：170，87，275，61462，503897，908，653，5123趟：61，87170275462，503897，908，653，5124趟：61 87 170 275 462，503897，908，653，5125趟：61，87，170275462，503897，908，653，5126趟：61，87，170，275，462，503897，908，653，5127趟：61，87，170，275，462，503512，653 897 9088趟：61，87，170，275，462，503，5126538979089趟：61，87，170，275，462，503，512，653，89790810趟：61，87，170，275，462，503，512，653，897，9083答案依题意，采用难排序法排序的各趟的结果如图11l所示。4答案依题意，采用基数排序法排序的各趟的结果如下：初始：503，87，512，61，908，170，897，275，653，462l趟（按个位排序）：170，61，462，512，503，653，275，87，897，9082趟（按十位排序）：503，908，512，653，61，462，170，275，87，8973趟（按百位排序）：61，87，170，275，462，503，512，653，897，9085 答案依题意，采用希尔排序法排序的各趟的结果如下：初始：503，17，512，908，170，897，275，653，426，154，509，612，677，765，703，94l趟（dl=8）：426，17，509，612，170，765，275，94，503，154，512，908，677，897，703，6532趟（d2=4）：170，17，275，94，426，154，509，612，503，765，512，653，677，897，703，9083趟（d3=2）：170，17，275，94，426，154，503，612，509，653，512，765，677，897，703，9084趟(d1=1)：17，94，154，170，275，426，503，509，512，612，653，677，703，765，897，9086答案依题意，采用插入排序法排序的各趟的结果如下：初始：（70），83，100，65，10，32，7，9l趟：（70，83），100，65，10，32，7，92趟：（70，83，100），65，10，32，7，93趟：（65，70，83，100），10，32，7，94趟：（l0，65，70，83，100），32，7，95趟：（l0，32，65，70，83，100），7，96趟：（7，10，32，65，70，83，100），97趟：（7，9，10，32，65，70，83，100）7答案依题意，采用Shell排序法排序的各趟的结果如下：初始：10，18，4，3，6，12，1，9，18，8l趟：10，1，4，3，6，12，18，9，15，82趟：4，1，6，3，10，8，15，9，18，123趟：1，3，4，6，8，9，10，12，15，18第3趟无元素交换，则排序结束8答案依题意，采用归并排序法排序的各趟的结果如下：初始：10，18，4，3，6，12，1，9，18，8l趟：10，18 3，46，121，98，152趟：3，4，10，18l，6，9，128，153趟：3，4，10，181，6，8，9，12，154趟：1，3，4，6，8，9，10，12，15，18第4趟归并完毕，则排序结束。81求字符串从第m个字符起，长度为k的子串。其中m,k从键盘输入。#include#include#include#define MAX 80main()char s1MAX,s2MAX,*p1,*p2;int m,k,i;printf(input a string:n);gets(s1);printf(input m,k:n);scanf(%d%d,&m,&k);p1=s1+m-1;p2=s2;for(i=m-1;im+k-1;i+) *p2+=*p1+;puts(s2);system(pause);2利用指针打印指定星期的英文名称。#include #includemain()char *name=Illegal weekday,monday,Tuesday,Wendsday,Thursday,Friday,Saturday,sunday; int j; printf(Input month Number(1-7)n); scanf(%d,&j); printf(No. %d:%sn,j,(j7)?name0:namej); system(pause);文件13P179. 29例修改(要在同一目录下先建立chengfa.txt文件#include#includemain()int i,j; FILE *fp; char fname20; printf(Enter file name for write data:n); gets(fname); if(fp=fopen(fname,w)=NULL) printf(Cannot open file,press any key exit!); getchar();exit(1); for(i=1;i=9;i+) for(j=i;j=9;j+) fprintf(fp,%d*%d=%2d,i,j,i*j); fprintf(fp,n);fclose(fp);system(pause);30例修改(要在同一目录下先建立in1.txt文件(输入源数据),还有out1.txt(输出数据)#include#includemain()float a65; int j,k; FILE *fp; char fname20; printf(Enter file name for read data:n); gets(fname); if(fp=fopen(fname,r)=NULL) printf(Cannot open file,press any key exit!); getchar();exit(1); printf(Input a 5*4 matrics:n); for(j=1;j=5;j+) for(k=1;k=4;k+) fscanf(fp,%f,&ajk); fclose(fp); printf(Enter file name for write data:n); gets(fname); if(fp=fopen(fname,w)=NULL) printf(Cannot open file,press any key exit!); getchar();exit(1); for(j=1;j=5;j+) for(k=1;k=4;k+) fprintf(fp,%7.2f,ajk); printf(n); fclose(fp); system(pause); 56题修改（要在同一目录下先建立lx1.txt（单词表）文件 ,还有lx2.txt(输出各个单词的长度)#include#include#include#define IN 1#define OUT 0#define MAXL 80main() FILE *fp,*fp2; char fname20,ch; int nwarrMAXL=0; int nw,i,k,c ,state=OUT,mlentgh; nw=i=0; printf(Enter file name for read data:n); gets(fname); if(fp=fopen(fname,r)=NULL) printf(Cannot open file,press any key exit!); getchar();exit(1); while(ch=fgetc(fp)!=EOF) if(ch= |ch=n|ch=t) state=OUT; else if(state=OUT) state=IN;+nw; +nwarrnw; printf(Enter file name for write data:n); gets(fname); if(fp2=fopen(fname,w)=NULL) printf(Cannot open file,press any key exit!); getchar();exit(1); for(i=1;i=nw;+i) fprintf(fp2,%3d ,nwarri); if(i%20=0)printf(n); printf(n); fclose(fp);fclose(fp2); system(Pause); 61例修改（要在同一目录下先建立sin.txt文件）#include#include#includeconst double PI=3.14159265;main() int j,k,sin2100; double x,t; FILE *fp; char fname20; t=2.0*PI/80;for(j=0,x=-PI;x=-11;k-)for(j=0;j=79;j+) if(j=40) fprintf(fp,%c,|); else if(sin2j=k) fprintf(fp,%c,*)