实验一 排序问题

实验实习名实验一排序问题求解(以下为参考内容，具体内容要求由课程在实验实习指导书中规定。)一、实验实习目的及要求实验题目：排序问题求解实验目的：以排序(分类)问题为例，掌握分治法的基本设计策略。熟练掌握一般插入排序算法的实现；熟练掌握快速排序算法的实现；理解常见的算法经验分析方法；二、实验实习设备(环境)及要求(软硬件条件)实验环境：计算机、C语言程序设计环境三、实验实习内容与步骤实验内容与步骤生成实验数据.要求：编写一个函数datagenetare，生成2000个在区间［1,10000］上的随机整数，并将这些数输出到外部文件data.txt中。这些数作为后面算法的实验数据。实现直接插入排序算法.要求：实现insertionsort算法。算法的输入是data.txt；输出记录为文件：resultsIS.txt；同时记录运行时间为TimeIS。直接插入算法思想：Procedureinsertionsort(A,n)A(0)=-forj=2tondoitem=A(j);i=j-1whileitem<A(i)doA(i+1)=A(i);i=i-1repeatA(i+1)=itemrepeatEndinsertionsort在无序的数组中，先将序列中的第一个数字看作是有序子序列，然后从第二个记录起逐个进行插入，直至将整个序列变成有序序列为止。实现快速排序算法.要求：实现QuickSort算法。算法的输入是data.txt；输出记录为文件：resultsQS.txt；同时记录运行时间为TimeQS。快速排序算法思想：ProcedureQuickSort(p,q)integerp,q；globaln,A(1:n)ifp<qthenj-q+1callPartition(p,j)callQuickSort(p,j-1)callQuickSort(j+1,q)endifendQuickSort用A(m)划分集合A的函数：Procedurepartition(m,p)integerm,p,I;globalA(m:p-1)v=A(m);I=mLooploopI=I+1untilA(I)>=vrepeatloopp=p-1untilA(p)<=vrepeatifI<pthencallinterchange(A(i),A(p))ElseexitEndifRepeatA(m)=A(p);A(p)=vEndpartition快速算法是一种基于分治技术的重要排序算法，把对n个对象的排序看作是对1到n个整数的排序。快速排序的基本思想是从中取一合适的关键字k,以k为标准把需要排序的n个对象分成两部分，一部分比k小，一部分比k大，即：(小于k的地方)k(大于k的地方)，然后对两部分分别进行快速排序，排序完成后，简单的合并连接起来即可，算法还可递归的进行。四、实验实习过程或算法(源程序、代码)源程序：#include<stdio.h>#include<stdlib.h>#include<time.h>//^include<math.h>#defineMAX2000#defineMAXVALUE10000intdata[MAX];〃生成2000个在区间[1,10000]上的随机整数voiddatagenetare()FILE*fp1;srand((unsigned)time(NULL));for(inti=0;i<MAX;i++)data[i]=rand()%MAXVALUE+1;//printf("data[i]=%5d〃，i,data[i]);if((fp1=fopen("data.txt”,〃w〃)))printf("Thefiledata.txthasbeencreatedsuccessfully!\n");elseprintf("Thefilefailedtocreate!\n");for(intj=0;j<MAX;j++){fprintf(fp1,"%5d",data[j]);fprintf(fp1,"");}if(fclose(fp1))printf("Thefile'data.txt'wasnotclosed\n");}//插入排序doubleinsertionsort(){//starttime设置计时开始doubleduration;FILE*fp1,*fp2;intdata[MAX];inttemp,k,m;clock_tfinish,start;if((fp1=fopen("data.txt”,"r"))==NULL)printf("Thefilefailedtoopen!\n");elseprintf("\nThedata.txtfilehasbeenopened!\n");for(inti=0;i<MAX;i++)fscanf(fp1,"%d”,&data[i]);fscanf(fp1,"\n");if(fclose(fp1))printf("Thefile'data.txt'wasnotclosed\n");start=clock();for(k=0;k<MAX;k++){temp=data[k];〃从右向左在有序区data[0...k-1]中找data[k]的插入位置m=k-1;while(m>=0&&temp<data[m])data[m+1]=data[m];m——;//在m+1处插入tempdata[m+1]=temp;/*〃输出每一趟的排序结果printf("k=%d〃,k);for(intn=0;n<MAX;n++)printf(〃%5d〃,data[n]);printf(〃\n〃)；*/}//finishtime设置计时结束finish=clock();//将结果写入文件if((fp2=fopen("resultsIS.txt”,〃w〃))){for(intj=0;j<MAX;j++){fprintf(fp2,〃%5d〃,data[j]);fprintf(fp2,"");}if(fclose(fp2))printf("Thefile'data.txt'wasnotclosed\n");printf("ThefileresultsIS.txthasbeencreatedsuccessfully!\n");}elseprintf("Thefilefailedtocreate!\n");duration=(double)(finish-start)/CLOCKS_PER_SEC;//统计时间durationreturnduration;}〃快速排序voidQuickSort(intsortdata[],ints,intt){//FILE*fp2;inttemp,i=s,j=t;if(s<t){temp=sortdata[s];while(i!=j)while(j>i&&sortdata[j]>temp)j--；if(i<j)sortdata[i]=sortdata[j];i++；while(i<j&&sortdata[i]<temp)i++;if(i<j)sortdata[j]=sortdata[i];j--;}}sortdata[i]=temp;QuickSort(sortdata,s,j-1);QuickSort(sortdata,j+1,t);}}voidmain(){FILE*fp2;intdata1[MAX];datagenetare();//fflush();//直接出入排序返回时间printf("TheCPUtimeofinsertionsortis%2.6fseconds:\n〃，insertionsort());〃快速排序返回时间if((fp2=fopen(〃data.txt〃，〃r〃))==NULL)printf("Thefilefailedtoopen!\n");elseprintf("\n\nThedata.txtfilehasbeenopened!\n");for(intk=0;k<MAX;k++)fscanf(fp2,〃％d〃，&data1[k]);fscanf(fp2,〃\n〃)；if(fclose(fp2))printf("Thefile'data.txt'wasnotclosed\n");printf("ThefileresultsQS.txthasbeencreatedsuccessfully!\n");//intk;//starttime设置计时开始doubleduration;clock_tfinish,start;start=clock();QuickSort(data1,0,MAX-1);finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;//统计时间duration//将结果写入文件if((fp2=fopen("resultsQS.txt”,〃w〃))){/*printf(〃Thefiledata.txthasbeencreatedsuccessfully!\n〃);elseprintf("Thefilefailedtocreate!\n〃);*/for(k=0;k<MAX;k++){fprintf(fp2,〃%5d〃,data1[k]);fprintf(fp2,"");}if(fclose(fp2))printf("Thefile'data.txt'wasnotclosed\n");}elseprintf("Thefilefailedtocreate!\n");//finishtime设置计时结束printf("TheCPUtimeofQuicksortis%2.6fseconds.\n",duration);printf("\n");}五、实验实习结果分析和(或)源程序调试过程算法理论分析直接插入排序从2开始做循环，依次和前面的数进行比较：for(inti=2;i<=n;i++)如果后面的比前面的小，则进行前移：if(number[i]<number[i-1])设置哨兵：number[0]=number[i];如果后面的比前面的小，前面的进行后移：for(j=i-1;number[0]<number[j];j--)前面的进行后移：number[j+1]=number[j];将比较的数据放置到正确位置：number[j+1]=number[0];该排序算法简洁，易于实现。从空间来看，他只需要一个记录的辅助空间，即空间复杂度为O(1).从时间来看，排序的基本操作为：比较两个关键字的大小和移动记录。当待排序列中记录按关键字非递减有序排列(即正序)时，所需进行关键字间的比较次数达最小值n-1，记录不需移动；反之，当待排序列中记录按关键字非递增有序排列(即逆序)时，总的比较次数达最大值(n+2)(n-1)/2，记录移动也达到最大值(n+4)(n-2)/2.由于待排记录是随机的，可取最大值与最小值的平均值，约为子/4.则直接插入排序的时间复杂度为0(子).由此可知，直接插入排序的元素个数n越小越好，源序列排序度越高越好(正序时时间复杂度可提高至0(n))。插入排序算法对于大数组，这种算法非常慢。但是对于小数组，它比其他算法快。其他算法因为待的数组元素很少，反而使得效率降低。插入排序还有一个优点就是排序稳定。快速排序传递设置整个数据的起点和终点：inti=first;intj=end;设置中轴：number[0]=number[i];当end大于first进行循环：while(i<j)当后面的数据大于中轴，后面的游标前移：while((i<j)&&(number[j]>=number[0]))j--;中轴和比它大的数据进行交换：number[i]=number[j];当前面的数据小于中轴，前面的游标后移：while((i<j)&&(number[i]<=number[0]))i++;中轴和比它小的数据进行交换：number[j]=number[i];将中轴进行归位：number[i]=number[0];快速排序的平均时间为k*nln(n)，其中n为待排时间中记录的个数，k为某个常数，经验证明，在所有同数量级的此类排序方法中，快速排序的常数因子k最小。因此，就平均时间而言，快速排序是最好的一种内部排序。快速排序在最好的情况时是正序，比较次数和移动次数均为O(nln(n))，最坏状况下，比较次数和移动次数均为n(n-1)/2次。快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和要交换元素的交换时刻。程序流程图直接插入排序i=Ltemp=Oj=Otemp=anr[i]j=larrbl=arrLi=l]―以—vFirr[j]=temp:a++i~T~快速排序

arrRarrfRl=anr[Ll;（三）记录结果清单给出data.txt、resultsIS.txt、resultsQS.txt三个文件任选其一的清单:arrRarrfRl=anr[Ll;data.txt清单r.I一—|L..Ir.I5勺一―l8--54296-.1■58563o-9444983!!.■_■55JI-5694243542s-55411758&3569凸4B32877,lI、4llK407

HI-rlz.74-3rr—3G556943QM-9rlz.9B4rlijoGrlij匚>-■■59s--52rlijT~I1-lIJ71rlij--73oso口l_l71--B4E9E.9匚■-■■y--46kL.1374oEl-ls31-lz8..u9E_b■-■.■.■■7--9o221bl'■'J_b6DD545II'51:IlJL'.'•J394II〕.III_b36II..II-矿Zu7Qos4_y2Ts3564_y6-h9.I65966g6-I9-yT.I.....I_:£5-h--uII..'.43787-J589一—i3一―I.3一―I55r.I一—|L..Ir.I5勺一―l8--54296-.1■58563o-9444983!!.■_■55JI-5694243542s-55411758&3569凸4B32877,lI、4llK407

HI-rlz.74-3rr—3G556943QM-9rlz.9B4rlijoGrlij匚>-■■59s--52rlijT~I1-lIJ71rlij--73oso口l_l71--B4E9E.9匚■-■■y--46kL.1374oEl-ls31-lz8..u9E_b■-■.■.■■7--9o221bl'■'J_b6DD545II'51:IlJL'.'•J394II〕.III_b36II..II-矿Zu7Qos4_y2Ts3564_y6-h9.I65966g6-I9-yT.I.....I_:£5-h--uII..'.43787-J589一—i3一―I.3一―I55857682Qo■-■■Jgs389----4FT.—B27El33TT~I32.Q73.2oI1069n.29BII.12oGrlcl3II..凸os599J1CO5-O-1009.-.U99119497325546756958787O46Q-O-8118599549009.17no13933o-72o580251848-7-99546612437-21457549948684188541::6)4145:T4C5L-&&2R-fi:-c:lI-日即F.-fi*-9:2'all'DslLT_yl49-』E4IM-

0.02s4263-7945sE1.97244176672556997'o41-1±25on-

no32799q-.1■rlI30137369o9..u599o93!!.■_■8545■■■.■....Io..u7475--5687.■..32弓4-344257D841996745-o-16-421268o5439.J71982967i—i-.1■3660135564o33l-l.ll652t—IT46838320REG3印0033675762<lu也霎叫心77布浴如明673997329032o-1415333-200662917347197927654o-3CO99846E63n—o277252326739JnoG6712o441564636-ys46o-629J&417585s.9E&9464774s181139J632-f-r.-36llK3u--378346r.-q7QM-4i—l84875i—lou/.-3E76436g&L.-td-I■■—■■1T±h.-L.-o■-_y7

_y

I

_yd-3-I997-I2r-9FF9II/.ml8oeO.J29owcI10门.』352633564rlw2o9G23--4BD4B6IIIJ£>-■■5i—lo63orlz斥?l〕4E4t—I&II〕9口■-■399II9_y3y_u||.凸TsKK8_y7■T-lIT—18..u34r.I46II.12T2Q!_■'.229!_.'o-L-..1rlIJ9992B3545--■?■-■■3453匚■-■■94■?■-■■rla444■-■.-:■E■-■.::■s4:||..〕1.14

--

II..:1

4_y&EH263Ilxll46462--833II.'.49b-4&68_■..:■5bE9459l_l6--3Frlooll.L3oo646726kL.1

B

9

&_b3rlB34&D&JI.J4JI9..I3_yflflB45B7-I

g

5794329959935n.L-l86964-llr.—6QJ--o-495900-o-36499371ono661o-9475no758514576o-576585-uo51654o-459.—o733137621485o14387o-no1901I7683356437743125-747no391424oo400s142493067-n-9sQ...-8127no4410s6572647632479Qu292256o-2o454.9E911999s2s口s59o-46561