算法实验(比较不同排序算法)

攀枝花学院实验报告实验课程：计算机算法实验实验项目：比较多种不同排序算法实验日期：2013.3.26系：数学与计算机学院班级：软件工程姓名：冯斌学号：201010804004指导教师：银星成绩：【实验目的：】1.掌握基本的排序算法2.学习各种算法实现的优劣3.掌握vc++6.0环境下程序的编写和调试【实验设备器材：】1.pc机一套2.java相应编译软件【实验原理：】基于直接插入，折半插入排序，冒泡排序，快速排序的实现，并记录其实现所用比较次数。【实验内容：】1.编写相应算法源程序2.在vc++6.0环境下调试通过3.通过程序排序所交换的次数，比较各种算法的优劣程序代码如下：#includestdio.h#includestdlib.h#includetime.h#defineRecordtypeintvoidcopy(Recordtypes[],Recordtyped[],intn);/************************************************************************//*直接插入法*//************************************************************************/intcmpTforIs=0;//记录插入法的比较次数intChgTforIs=0;//记录插入法的交换次数voidInsertSort(Recordtypedata[],intn);/************************************************************************//*折半插入法*//************************************************************************/intcmpTforBinarys=0;//记录冒泡的比较次数intChgTforBinarys=0;//记录冒泡的交换次数voidBinarySearchInsertion(intnumbers[],constintn);/************************************************************************//*冒泡法*//************************************************************************/intcmpTforBs=0;//记录冒泡的比较次数intChgTforBs=0;//记录冒泡的交换次数voidBubsort(Recordtype*start,Recordtype*end);/************************************************************************//*快排*//************************************************************************/intcmpTforQs=0;//记录快排的比较次数intChgTforQs=0;//记录快排的交换次数intquickPass(intstart,intlast,Recordtyperecord[]);intquickSort(intstart,intlast,Recordtyperecord[]);intmain(){RecordtypeData[100];RecordtypeD[100];srand(time(NULL));printf(therand100numbersare:\n);for(inti=0;i100;i++){D[i]=rand()%1000;//便于观察,每次产生1000内的整数printf(%d,D[i]);}printf(\n\n\n);copy(D,Data,100);BinarySearchInsertion(Data,100);printf(折半插入法的比较次数为%d,交换次数为%d\n,cmpTforBinarys,ChgTforBinarys);copy(D,Data,100);InsertSort(Data,100);printf(直接插入法的比较次数为%d,交换次数为%d\n,cmpTforIs,ChgTforIs);copy(D,Data,100);Bubsort(&Data[0],&Data[99]);printf(冒泡法的比较次数为%d,交换次数为%d\n,cmpTforBs,ChgTforBs);copy(D,Data,100);quickSort(0,99,Data);printf(快排的比较次数为%d,交换次数为%d\n,cmpTforQs,ChgTforQs);printf(排序后的序列为\n);//你可以这块放在任意排序完毕的语句后面,检查排序的正确性for(i=0;i100;i++){printf(%d,Data[i]);}return0;}voidcopy(Recordtypes[],Recordtyped[],intn){for(inti=0;in;i++){d[i]=s[i];}}voidBinarySearchInsertion(intnumbers[],constintn){intmiddle=0;for(inti=1;in;i++){intlow=0;inthigh=i-1;inttemp=numbers[i];while(low=high){cmpTforBinarys++;middle=(low+high)/2;if(tempnumbers[middle]){high=middle-1;}elselow=middle+1;}for(intk=i;kmiddle;k--){ChgTforBinarys++;numbers[k]=numbers[k-1];}ChgTforBinarys++;numbers[low]=temp;}}voidInsertSort(Recordtypedata[],intn){for(inti=1;in;i++){inttemp=data[i];for(intj=i;j0&&tempdata[j-1];--j){ChgTforIs++;cmpTforIs++;data[j]=data[j-1];}data[j]=temp;}}voidBubsort(Recordtype*start,Recordtype*end){intnum=end-start+1;Recordtypetemp;inti,j;Recordtype*a=start;for(i=0;inum;i++){for(j=0;jnum-i;j++){cmpTforBs++;if(*(a+j-1)*(a+j)){ChgTforBs++;temp=*(a+j-1);*(a+j-1)=*(a+j);*(a+j)=temp;}}}}intquickPass(intstart,intlast,Recordtyperecord[]){ints=start,l=last;inttemp=record[s];while(sl){while(sl&&temp=record[l]){l--;cmpTforQs++;}if(sl){record[s++]=record[l];ChgTforQs++;}while(sl&&temp=record[s]){s++;cmpTforQs++;}if(sl){record[l--]=record[s];ChgTforQs++;}}record[s]=temp;ChgTforQs++;returns;}intquickSort(intstart,intlast,Recordtyperecord[]){intpos=0;if(startlast){pos=quickPass(start,last,record);quickSort(start,pos-1,record);quickSort(pos+1,last,record);}return0;}#includestdio.h#includestdlib.h#defineMAXSIZE20#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)(b))#defineLQ(a,b)((a)=(b))#defineN7typedefintKeyType;typedefintInfoType;/*定义其它数据项的类型*/typedefstruct{KeyTypekey;/*关键字项*/InfoTypeotherinfo;/*其它数据项，具体类型在主程中定义*/}RedType;/*记录类型*/typedefstruct{RedTyper[MAXSIZE+1];/*r[0]闲置或用作哨兵单元*/intlength;/*顺序表长度*/}SqList;/*顺序表类型*/voidMerge(RedTypeSR[],RedTypeTR[],inti,intm,intn){/*将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]算法10.12*/intj,k,l;for(j=m+1,k=i;i=m&&j=n;++k)/*将SR中记录由小到大地并入TR*/ifLQ(SR[i].key,SR[j].key)TR[k]=SR[i++];elseTR[k]=SR[j++];if(i=m)for(l=0;l=m-i;l++)TR[k+l]=SR[i+l];/*将剩余的SR[i..m]复制到TR*/if(j=n)for(l=0;l=n-j;l++)TR[k+l]=SR[j+l];/*将剩余的SR[j..n]复制到TR*/}voidMSort(RedTypeSR[],RedTypeTR1[],ints,intt){/*将SR[s..t]归并排序为TR1[s..t]。算法10.13*/intm;RedTypeTR2[MAXSIZE+1];if(s==t)TR1[s]=SR[s];else{m=(s+t)/2;/*将SR[s..t]平分为SR[s..m]和SR[m+1..t]*/MSort(SR,TR2,s,m);/*递归地将SR[s..m]归并为有序的TR2[s..m]*/MSort(SR,TR2,m+1,t);/*递归地将SR[m+1..t]归并为有序的TR2[m+1..t]*/Merge(TR2,TR1,s,m,t);/*将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]*/}}voidMergeSort(SqList*L){/*对顺序表L作归并排序。算法10.14*/MSort((*L).r,(*L).r,1,(*L).length);}voidprint(SqListL){inti;for(i=1;i=L.length;i++)printf((%d,%d),L.r[i].key,L.r[i].otherinfo);printf(\n);}程序运行结果：实验总结：通过本次实验，对于在vc++6.0的编译，以及各种算法的实现有了更深入的了解和掌握，通过对各种排序算法的实现以及比较其优劣性，对它们的优劣性有了更多的了解，在以后的编程过程中，是很宝贵的经验。在本次实验中，借助了很多的资料帮助，自己在以后的学习中，还有很多方面需要提高。