数据结构课程设计五——排序算法综合分析

数据结构课程设计五——排序算法综合分析I’m段剀越^_^******************感谢郭鹏老师和史绍强老师耐心指点*******************#includeiostream.h#includeconio.h#includemath.h#includestdio.h#includestdlib.h#includetime.h#includecstdlib//#defineclock_tstart//#defineclock_tcomplete#defineMAXSIZE2000//排序表的最大容量intcn,mn;typedefstruct//定义排序表的结构{intelemword[MAXSIZE];//数据元素关键字intcount;//表中当前元素的个数}SqList;voidInitialSqList(SqList&);//初始化排序表voidPrintSqList_after(SqList);//显示表中的已排序完毕的元素voidPrintSqList_before(SqList);//显示表中的未排序完毕的元素voidInsertSort(SqList&);//直接插入排序voidShellSort(SqList&,int[],int);//希尔排序voidShellInsert(SqList&,int);//一趟希尔排序voidQuickSort(SqList&);//快速排序voidQSort(SqList&,int,int);//子序列快速排序intPartition(SqList&,int,int);//一趟快速排序voidBubbleSort(SqList&);//冒泡排序voidHeapSort(SqList&L);//堆排序voidHeapAdjust(SqList&L,ints);//使SqList成为一个大顶堆voidMergeSort(SqList&,SqList&,intlow,intmid,inthigh);//归并法排序voidMSort(SqList&,SqList&,intlow,inthigh);//归并法递归调用///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////voidInitialSqList(SqList&L){//表初始化inti,j;printf(请输入待排序的记录的个数:);scanf(%d,&L.count);cout请选择：1.手动输入2.电脑随机输入(选择1或者2)endl;cinj;switch(j){case1:{printf(请输入待排序的记录的关键字(整型数):\n);for(i=1;i=L.count;i++)scanf(%d,&L.elemword[i]);};break;case2:{srand(time(NULL));for(inti=1;i=L.count;i++){L.elemword[i]=rand()%50+1;}PrintSqList_before(L);};break;default:coutAreyoukidding?endl;}}voidPrintSqList_after(SqListL){//显示表中的已排序完毕的元素inti;printf(排序后的序列如下：\n);for(i=1;i=L.count;i++)printf(%4d,L.elemword[i]);printf(\n);}voidPrintSqList_before(SqListL){//显示表中的未排序完毕的元素inti;printf(排序前的序列如下：\n);for(i=1;i=L.count;i++)printf(%4d,L.elemword[i]);printf(\n);}///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////voidInsertSort_main(){SqListL;//声明表Lcharj='y';printf(本程序将演示直接插入排序的操作。\n);while(j!='n'&&j!='N'){InitialSqList(L);InsertSort(L);printf(继续进行下一次排序吗?(Y/N));scanf(%c,&j);}printf(程序运行结束!\n返回选择界面!\n);getchar();getchar();//exit(0);}voidInsertSort(SqList&L){inti,j;cn=0;mn=0;doublestart=clock();for(i=2;i=L.count;i++)if(L.elemword[i]L.elemword[i-1])//,需将L.elemword[i]插入有序子表{cn++;L.elemword[0]=L.elemword[i];//复制为哨兵mn++;for(j=i-1;L.elemword[0]L.elemword[j];--j){cn++;L.elemword[j+1]=L.elemword[j];//记录后移mn++;}L.elemword[j+1]=L.elemword[0];//插入到正确的位置mn++;}doublecomplete=clock();PrintSqList_after(L);cout\t\t\t\t\t\t所花时间：(complete-start)/CLOCKS_PER_SEC\t秒endl;cout\t\t\t\t\t\t比较次数：cn\t次endl;cout\t\t\t\t\t\t移动次数：mn\t次endl;}/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////希尔排序voidShellSort_main(){SqListL;//声明表Lcharj='y';intdlta[3]={5,3,1};//希尔排序增量序列，本程序采用5，3，1序列intt=3;//希尔排序增量序列中增量的个数printf(本程序将演示希尔排序的操作。\n增量序列为5，3，1。\n);while(j!='n'&&j!='N'){InitialSqList(L);//待排序列初始化ShellSort(L,dlta,t);//希尔排序printf(继续进行下一次排序吗?(Y/N));scanf(%c,&j);}printf(程序运行结束!\n返回选择界面!\n);getchar();getchar();//exit(0);}voidShellSort(SqList&L,intdlta[],intt){//按增量序列dlta[0..t-1]对顺序表L作希尔排序cn=0;mn=0;doublestart=clock();for(intk=0;kt;++k)ShellInsert(L,dlta[k]);//一趟增量为dlta[k]的插入排序doublecomplete=clock();PrintSqList_after(L);//显示希尔排序结果cout\t\t\t\t\t\t所花时间：(complete-start)/CLOCKS_PER_SEC\t秒endl;cout\t\t\t\t\t\t比较次数：cn\t次endl;cout\t\t\t\t\t\t移动次数：mn\t次endl;}voidShellInsert(SqList&L,intdk){//对顺序表L做一趟希尔插入排序。本算法是和一趟直接插入排序相比，作了以下修改：//1.前后记录的增量是dk，而不是1//2.0号单元只是暂存单元，不是哨兵。当j=0时，插入位置已找到inti,j;for(i=dk+1;i=L.count;i++)if(L.elemword[i]L.elemword[i-dk])//,需将L.elemword[i]插入有序子表{cn++;L.elemword[0]=L.elemword[i];//暂存在0号单元for(j=i-dk;j0&&L.elemword[0]L.elemword[j];j-=dk){L.elemword[j+dk]=L.elemword[j];//记录后移，查找插入位置cn++;mn++;}L.elemword[j+dk]=L.elemword[0];//插入到正确的位置mn+=2;}}/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////快速排序voidQuickSort_main(){SqListL;//声明表Lcharj='y';printf(本程序将演示快速排序的操作。\n);while(j!='n'&&j!='N'){InitialSqList(L);//待排序列初始化QuickSort(L);//快速排序printf(继续进行下一次排序吗?(Y/N));scanf(%c,&j);}printf(程序运行结束!\n返回选择界面!\n);getchar();getchar();//exit(0);}voidQuickSort(SqList&L){//对顺序表L做快速排序。cn=0;mn=0;doublestart=clock();QSort(L,1,L.count);doublecomplete=clock();PrintSqList_after(L);//显示排序结果cout\t\t\t\t\t\t所花时间：(complete-start)/CLOCKS_PER_SEC\t秒endl;cout\t\t\t\t\t\t比较次数：cn\t次endl;cout\t\t\t\t\t\t移动次数：mn\t次endl;}voidQSort(SqList&L,intlow,inthigh){//对顺序表中的子序列L.r[low..high]作快速排序intpivotloc;if(lowhigh)//长度大于1{pivotloc=Partition(L,low,high);//将L.elemword[low..high]一分为二QSort(L,low,pivotloc-1);//对低子表递归排序,pivotloc是枢轴位置QSort(L,pivotloc+1,high);//对高子表递归排序}}intPartition(SqList&L,intlow,inthigh){//交换顺序表L中子表r[low..high]的记录，枢轴记录到位，并返回其所在位置，此时//在它之前(后)的记录均不大(小)于它intpivotkey;pivotkey=L.elemword[low];//用子表的第一个记录作枢轴记录mn++;while(lowhigh)//从表的两端交替地向中间扫描{while