数据结构与算法课程设计报告-内部排序算法比较

课程设计报告课程数据结构与算法课程设计名称内部排序算法比较题目：内部排序算法比较在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各种算法的关键字比较次数和关键字移动次数，以取得直观感受。 对以下7种常用的内部排序算法进行比较：冒泡排序、直接插入排序、简单选择排序、希尔排序、堆排序、归并排序、快速排序。待排序表的表长不小于100；其中的数据要用伪随机数程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。最后要对结果作出简单分析，包括对各组数据得出结果波动大小的解释。由随机数产生器生成一、问题分析和任务定义：在本次课程设计中，正如前面所说的一样，迫切需要一个能实现常用的排序算法，并对各种排序算法仅仅考虑在相同条件情况下直观地反映排序算法在对比次数、移动次数、时间消耗方面的性能对比。本程序只做排序性能的分析，故人机交换方面要求不高，相关控制用宏实现。二、数据结构的选择和概要设计：（一）数据结构的选择：（根据实验的要求）//***结构体***typedefstruct{KeyTypekey;}RedType;typedefstruct{ RedTyper[MAXSIZE+1]; intlength; intinfo;//记录关键字移动次数 intcmp;//关键字的比较次数}SqList;（二）概要设计：设计思路：首先，从完成的功能上看，用随机种子产生随机数（用时间），200取余，取100个数，对这100个数进行排序。三、详细设计和编码：//***冒泡排序***voidBubbleSort(SqList*L){ inti=0,j=0,k=0,change; intn=L->length,x; change=1;//记录元素交换的标志变量for(i=0;i<n-1&&change;++i) { change=0; for(j=0;j<n-i-1;++j) {if(L->r[j].key>L->r[j+1].key)//如果前面的数大于后面的数就交换（从小到大排序） { x=L->r[j].key; L->r[j].key=L->r[j+1].key; L->r[j+1].key=x; L->info+=3;//由于进行三次交换关键字移动的次数为三次 change=1; } L->cmp++;//每经过一次循环就会比较一次 } }}//***直接插入排序***voidInsertSort(SqList*L){ inti,j; RedTypek;//监视哨 for(i=1;i<L->length;i++) { k=L->r[i];//将带插入元素存到监视哨中L->cmp++; j=i-1; while(k.key<L->r[j].key)//寻找插入位置 { L->r[j+1]=L->r[j]; L->info++; L->cmp++; j=j-1; } L->r[j+1]=k;//将待插入元素插入到已排序的的序列中L->cmp++; L->info++; }}//***简单选择排序***voidSelectSort(SqList*L){intn,i,k,j; n=L->length-1; for(i=0;i<n;i++) { for(j=i+1;j<n+1;j++) { if(L->r[j].key<L->r[i].key) { change(&L->r[j].key,&L->r[i].key);L->info+=3; }L->cmp++; } }}//***希尔排序***voidShellinsert(SqList*L,intdelta){//直接插入排序 inti,j,k,count=0; RedTypeflag; for(i=0;i<delta;i++) { for(j=i+delta;j<=L->length-1;j=j+delta) { flag.key=L->r[j].key; L->info++; k=j-delta; while((flag.key<L->r[k].key)&&k>=0) { L->r[k+delta].key=L->r[k].key; k=k-delta; L->cmp++;count=1; L->info++; } if(count==0)//防止多加了 { L->cmp++; } L->r[k+delta].key=flag.key; L->info++; count=0;//初始化count } }}SqList*ShellSort(SqList*L){ inti,di[100]; di[0]=L->length/2;//取长度的一半作为步长 for(i=0;i<L->length-1;i++) { Shellinsert(L,di[i]); di[i+1]=di[i]/2;//每次取其一半作为步长 if(di[i]==1)//当步长为1时，此时排序已结束序列已有序 { break;//跳出for循环 } } returnL;}//***堆排序***voidSift(SqList*L,inti,intm){ intk,t; t=L->r[i].key;L->info++;k=2*i+1; while(k<m) { if((k<m-1)&&(L->r[k].key<L->r[k+1].key)) { k++; } if(t<L->r[k].key) { L->r[i].key=L->r[k].key; L->info++; i=k; k=2*i+1; } else { break; } L->cmp++; } L->r[i].key=t;L->info++;}voidHeapSort(SqList*L){ intn,i; RedTypetemp; n=L->length; for(i=n/2-1;i>=0;--i) { Sift(L,i,n); } for(i=n-1;i>=1;i--) { change(&L->r[0].key,&L->r[i].key); Sift(L,0,i); }}//***归并排序***SqList*mergesort(SqList*L){ inti,di[100],flag=0,n; di[0]=2; n=L->length; for(i=0;i<L->length-1;i++) { merge(L,di[i]); di[i+1]=di[i]*2; if((di[i+1]>L->length)&&(di[i]<=L->length))//当步长小于等于顺序表的长度时，步长*2大于顺序表时，此时做最后的排序 { di[i]=n; merge(L,di[i]);//此时步长等于顺序表的长度 break;//跳出for循环 } } returnL;}voidmerge(SqList*L,intdelta){//用的是直接插入进行排序的 inti,j,k,n,count=0;; RedTypeflag; n=L->length-1;for(i=0;i<=n;i=i+delta) {for(j=i+1;((j<i+delta)&&(j<=n));j++) { flag.key=L->r[j].key; L->info++; k=j-1; while((flag.key<L->r[k].key)&&(k>=i)) { L->r[k+1].key=L->r[k].key; k=k-1; count=1;L->info++; L->cmp++; } if(count==0) { L->cmp++; } L->r[k+1].key=flag.key; L->info++; count=0; } }}//***快速排序***intPartition(SqList*H,intleft,intright){RedTypex; intlow,high,flag=0; x=H->r[left]; low=left; high=right; // printf("0"); while(low<high) { while(H->r[high].key>=x.key&&low<high) { high--; flag=1; H->cmp++; } if(low<high) { H->r[low]=H->r[high]; H->info++; low++; } while(H->r[low].key<x.key&&low<high) { if(flag==0) { H->cmp++; } low++; } if(low<high) { H->r[high]=H->r[low]; H->info++; high--; } if(flag==0) {H->cmp++;} } H->r[low]=x; H->info++; returnlow;}voidQuickSort(SqList*L,intlow,inthigh){ intmid; // printf("1"); if(low<high) { mid=Partition(L,low,high);QuickSort(L,low,mid-1); QuickSort(L,mid+1,high); }}四、测试结果及分析：五、测试结果及其分析表中数据为关键字移动次数：BubbleSortInsertSortSelectSortShellSortHeapSortmergesortQuickSort第一组69096906634514007943499288第二组75487548656113717753712295第三组68586858638713377903482271第四组79927992701713937783860293第五组75937593616214617773727309第六组76057605653114107653731304表中数据为关键字比较次数：BubbleSortInsertSortSelectSortShellSortHeapSortmergesortQuickSort第一组4872487249506754962641404第二组4935493549506484772872435第三组4949494949506224922630385第四组4922492249506594803008375第五组4719471949507294792877385第六组4872487249506784672889319有数据分析可知：无论待排序列排序如何，BubbleSort与SelectSort两种算法的关键字比较次数均为4950，即n(n-1)/2次，待排序列伪随机序列是直接插入排序的关键字比较次数和关键字移动平均值约为/4，正序时比较次数为(n-1),移动次数为0，逆序时为n(n-1)/2次；整体看来六种排序中QuickSort、ShellSort、HeapSort三种排序比较和移动次数相对较少；但BubbleSort、insertSort两种属于稳定排序。在测试过程中，当连续选择一个操作时，发现有的排序方式的关键字移动次数会随之增加，例如：BubbleSort、QuickSort、HeapSort；仔细分析后得知，无论待排序是否排好，它每次运行都会有关键字的移动；每次运行程序，六种排序方式的关键字比较次数也会随这操作次数的增加而增加。Mergesort排序空间性能比较差。六、用户使用说明输入：1-7数字，每次只能输一次，从1到7都可以。七、参考文献【1】王昆仑李红.数据结构与算法.中国铁道出版社.2007年6月第一版八、附录/*内部排序算法比较【问题描述】在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各种算法的关键字比较次数和关键字移动次数，以取得直观感受。 【任务要求】 对以下7种常用的内部排序算法进行比较：冒泡排序、直接插入排序、简单选择排序、希尔排序、堆排序、归并排序、快速排序。 待排序表的表长不小于100；其中的数据要用伪随机数程序产生；至少要用5组不同的输入数据作比较； 比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。 最后要对结果作出简单分析，包括对各组数据得出结果波动大小的解释。 【测试数据】由随机数产生器生成*/#include<iostream.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#include<malloc.h>#include<time.h>#defineKeyTypeint#defineMAXSIZE100//***结构体***typedefstruct{KeyTypekey;}RedType;typedefstruct{ RedTyper[MAXSIZE+1]; intlength; intinfo;//记录关键字移动次数 intcmp;//关键字的比较次数}SqList;voidchange(int*a,int*b);voidshow_paixu(SqList*L);intmenu_select();voidmain_menu();voidBubbleSort(SqList*L);voidInsertSort(SqList*L);voidSelectSort(SqList*L);voidShellinsert(SqList*L,intn);SqList*ShellSort(SqList*L);voidHeapSort(SqList*L);SqList*mergesort(SqList*L);voidmerge(SqList*L,intdelta);voidQuickSort(SqList*L,intlow,inthigh);//***两个数交换***voidchange(int*a,int*b){ intc; c=*a; *a=*b; *b=c;}//***显示函数***voidshow_paixu(SqList*L){ inti,j=-1;printf("该排序排序的结果：\n"); for(i=0;i<MAXSIZE;i++) { j++; if(j==10) { j=0; printf("\n"); } printf("%d",L->r[i].key); } printf("\n记录关键字移动次数为:%d\n",L->info);printf("关键字的比较次数为：%d\n",L->cmp);}/**********************菜单************************/intmenu_select(){ intchioce; printf("***********************************************************\n"); printf("******************************菜单*************************\n"); printf("1.BubbleSort\n");//冒泡排序 printf("2.insertSort\n");//直接插入排序 printf("3.SelectSort\n");//简单选择排序 printf("4.ShellSort\n");//希尔排序 printf("5.HeapSort\n");//堆排序 printf("6.mergesort\n");//归并排序 printf("7.QSort\n");//快速查找排序 printf("8.退出程序\n"); printf("***********************************************************\n"); printf("请输入数字：1-7选择相应的排序方式或操作：\n"); scanf("%d",&chioce); returnchioce;}/**********************主菜单************************/voidmain_menu(){SqListL,L1,L2,L3,L4,L5,L6; intj=-1,i=0;L.length=0; L.info=0; L.cmp=0; srand((unsigned)time(NULL)); printf("以下数据为需要排序的数据：\n");for(i=0;i<MAXSIZE;i++) { j++; L.r[i].key=rand()%200; L.length++; if(j==10) { j=0; printf("\n"); } printf("%d",L.r[i].key); } L1=L2=L3=L4=L5=L6=L; printf("\n"); for(i=0;i<7;i++) { switch(menu_select()) { case1:BubbleSort(&L); show_paixu(&L); break; case2:InsertSort(&L1); show_paixu(&L); break; case3:SelectSort(&L2); show_paixu(&L2); break; case4:show_paixu(ShellSort(&L3)); break; case5:HeapSort(&L4); show_paixu(&L4); break; case6:show_paixu(mergesort(&L5)); break; case7:QuickSort(&L6,0,L.length-1); show_paixu(&L6); break; } }}/******************************************************主程序*****************************************************************/intmain(){ main_menu();return0;}/******************************************************排序******************************************************************///***冒泡排序***voidBubbleSort(SqList*L){ inti=0,j=0,k=0,change; intn=L->length,x; // printf("%d",L->length); change=1;for(i=0;i<n-1&&change;++i) { change=0; for(j=0;j<n-i-1;++j) {if(L->r[j].key>L->r[j+1].key) { x=L->r[j].key; L->r[j].key=L->r[j+1].key; L->r[j+1].key=x; L->info+=3; change=1; } L->cmp++; } }}//***直接插入排序***voidInsertSort(SqList*L){ inti,j; RedTypek; for(i=1;i<L->length;i++) { k=L->r[i]; j=i-1; while(k.key<L->r[j].key) { L->r[j+1]=L->r[j]; L->info++; L->cmp++; j=j-1; } L->r[j+1]=k; L->info++; }}//***简单选择排序***voidSelectSort(SqList*L){intn,i,k,j; n=L->length-1; for(i=0;i<n;i++) { for(j=i+1;j<n+1;j++) { if(L->r[j].key<L->r[i].key) { change(&L->r[j].key,&L->r[i].key);L->info+=3; }L->cmp++; } }}//***希尔排序***voidShellinsert(SqList*L,intdelta){ inti,j,k,count=0; RedTypeflag; for(i=0;i<delta;i++) { for(j=i+delta;j<=L->length-1;j=j+delta) { flag.key=L->r[j].key; L->info++; k=j-delta; while((flag.key<L->r[k].key)&&k>=0) { L->r[k+delta].key=L->r[k].key; k=k-delta; L->cmp++;count=1; L->info++; } if(count==0) { L->cmp++; } L->r[k+delta].key=flag.key; L->info++; count=0; } }}SqList*ShellSort(SqList*L){ inti,di[100]; di[0]=L->length/2; for(i=0;i<L->length-1;i++) { Shellinsert(L,di[i]); di[i+1]=di[i]/2; if(di[i]==1) { break; } } returnL;}//***堆排序***voidSift(SqList*L,inti,intm){ intk,t; t=L->r[i].key;L->info++;k=2*i+1; while(k<m) { if((k<m-1)&&(L->r[k].key<L->r[k+1].key)) { k++; } if(t<L->r[k].key) { L->r[i].key=L->r[k].key; L->info++; i=k; k=2*i+1; } else { break; } L->cmp++; } L->r[i].key=t;L->info++;}voidHeapSort(SqList*L){ intn,i; RedTypetemp; n=L->length; for(i=n/2-1;i>=0;--i) { Sift(L,i,n); } for(i=n-1;i>=1;i--) { change(&L->r[0].key,&L->r[i].key); Sift(L,0,i); }}//***归并排序***SqList*mergesort(SqList*L){ inti,di[100],flag=0,n; di[0]=2; n=L->length; for(i=0;i<L->length-1;i++) { merge(L,di[i]); di[i+1]=di[i]*2; if((di[i+1]>L->length)&&(di[i]<=L->len