内部排序算法比较

..部排序算法比拟班级：：学号：完成日期：题目：试通过随机数据比拟各算法的关键字比拟次数和关键字移动次数，以取得直观感受。一．需求分析1.对常用的6种部排序算法进展比拟：冒泡排序，直接插入排序，简单项选择择排序，快速排序，希尔排序，堆排序。2.待排序表的表长不小于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比拟；比拟的指标为有关键字参加的比拟次数和关键字的移动次数〔关键字交换计为3次移动〕3.最后要对结果作出简单分析，包括对各组数据得到结果波动大小的解释。二．概要设计1.主界面设计对六种部排序算法进展比拟，可通过随机数程序产生几组数，要求用户手动输入产生随机数的个数。运行界面如下图：选择1运行程序，选择2退出程序2．存储构造设计本程序采用顺序表构造，具体构造定义如下：typedefstruct{intkey;}ElemType;typedefstruct{ElemType*elem;intlength;}SqList;3.系统功能设计1〕分配存空间。创立顺序表2〕利用伪随机数产生程序产生随机数，作为程序运行的数据3〕实现每种排序算法的功能函数三．模块设计随机数产生模块1.模块设计随机数产生模块主程序模块主程序模块排序算法模块排序算法模块2.系统子程序及功能设计本系统共设置13个函数，其中包括主函数。各函数名及功能说明如下。1〕voidaddlist(SqList&L)//建立个空顺序表2〕voidrandom(SqList&L)//随机数产生函数3〕voidmemory(SqList&M,SqList&L)//记录L，以保证每个排序函数使用一组随机数4〕voidBubbleSort(SqList&L)//冒泡排序5〕voidInsertSort(SqList&L)//直接插入排序6〕voidSelectSort(SqList&L)//选择排序7〕intPartition(SqList&L,intlow,inthigh)//返回快速排序枢轴的位置8〕voidQSort(SqList&L,intlow,inthigh)//对子序列作快速排序9〕voidQuickSort(SqList&L)//对数序表作快速排序10〕voidShellSort(SqList&L)//希尔排序11〕voidHeapAdjust(SqList&L,ints,intm)//堆排序算法子程序12〕voidHeapSort(SqList&L)//对顺序表进展堆排序13〕voidmain()//主函数，调用各模块函数3.函数主要调用关系913〕main〔〕51243211068117913〕main〔〕51243211068117四．详细设计1.数据类型定义typedefstruct{intkey;}ElemType;typedefstruct{ElemType*elem;intlength;}SqList;2.全局变量定义intbj1=0,yd1=0,bj2=0,yd2=0,bj3=0,yd3=0,bj4=0,yd4=0,bj5=0,yd5=0,bj6=0,yd6=0;//记录每种算法的比拟，移动次数intn；//随机数的个数2.系统主要子程序详细设计〔1〕主函数设计模块主要是输入数据，以及程序界面的设计，调用系统的各个子程序，并输出结果。〔详见源程序〕〔2〕随机数产生模块利用伪随机数产生程序产生数据，并存储到顺序表中。voidrandom(SqList&L){L.length=0;staticboolfirst=true;if(first){srand(time(0));first=false;}//使每次产生的随机数不同for(inti=1;i<n+1;i++)a:{ L.elem[i].key=rand();if(L.elem[i].key>30000) gotoa;++L.length;}〔3〕排序算法模块实现冒泡排序，直接插入排序，简单项选择择排序，快速排序，希尔排序以及堆排序的算法。〔祥见源程序〕五．测试分析运行程序后，得到如下图：输入：1输入：100选择1重复上述步骤，输入150，200，250，300得到另外四个结果：退出程序，请选择：2结果分析：冒泡排序，直接插入排序以及简单项选择择排序比拟次数较多，快速排序，希尔排序及堆排序比拟次数较少；并可得冒泡排序和直接插入排序相对较稳定，其他四种部排序为不稳定排序。六．源程序清单#include"iostream"#include"stdio.h"#include"stdlib.h"#include"string.h"#include"time.h"usingnamespacestd;#defineLIST_INIT_SIZE50000intbj1=0,yd1=0,bj2=0,yd2=0,bj3=0,yd3=0,bj4=0,yd4=0,bj5=0,yd5=0,bj6=0,yd6=0,n;//yd，bj为记录关键字比拟和移动的次数typedefstruct{intkey;}ElemType;typedefstruct{ElemType*elem;intlength;}SqList;voidaddlist(SqList&L)//初始化顺序表{a:printf("请输入你要输入的个数:");scanf("%d",&n);if(n>50000){printf("超出围重新输入!!!\n");gotoa;}L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(0);}voidrandom(SqList&L)//随机数产生程序{L.length=0;staticboolfirst=true;if(first){srand(time(0));first=false;}//使输入一样个数时每次产生的随机数不同for(inti=1;i<n+1;i++)a:{ L.elem[i].key=rand();if(L.elem[i].key>30000) gotoa;++L.length;}}voidmemory(SqList&M,SqList&L)//记录L，使每个排序算法都用一组一样的随机数{ M.length=0; for(inti=1;i<n+1;i++) {M.elem[i].key=L.elem[i].key; ++M.length; }}voidBubbleSort(SqList&L)//冒泡排序{ inti,j; for(i=1;i<L.length;i++) { for(j=1;j<L.length-i+1;j++) {bj1++; if(L.elem[j].key>L.elem[j+1].key){L.elem[0].key=L.elem[j].key;L.elem[j].key=L.elem[j+1].key;L.elem[j+1].key=L.elem[0].key;yd1+=3;} } }}voidInsertSort(SqList&L)//直接插入排序{inti,j;for(i=2;i<=L.length;i++){if(L.elem[i].key<L.elem[i-1].key){L.elem[0].key=L.elem[i].key;yd2++;j=i-1;bj2++;while(L.elem[0].key<L.elem[j].key){L.elem[j+1].key=L.elem[j].key;j--;yd2++;bj2++;}L.elem[j+1].key=L.elem[0].key;yd2++;}}}voidSelectSort(SqList&L)//选择排序{inti,j,k;for(i=1;i<L.length;i++){k=i;for(j=i+1;j<L.length;j++){bj3++;if(L.elem[j].key<L.elem[k].key)k=j;}if(i!=k){L.elem[0].key=L.elem[i].key;L.elem[i].key=L.elem[k].key;L.elem[k].key=L.elem[0].key;yd3+=3;}}}intPartition(SqList&L,intlow,inthigh)//快速排序{intpivotkey;L.elem[0]=L.elem[low];yd4++;pivotkey=L.elem[low].key;while(low<high){yd4++;while(low<high&&L.elem[high].key>=pivotkey)--high;L.elem[low]=L.elem[high];bj4++;yd4++;while(low<high&&L.elem[low].key<=pivotkey)++low;L.elem[high]=L.elem[low];bj4++;yd4++;}L.elem[low]=L.elem[0];yd4++;returnlow;}voidQSort(SqList&L,intlow,inthigh){//对顺序表的子序列作快速排序intpivotloc;if(low<high){pivotloc=Partition(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);}}voidQuickSort(SqList&L){//对顺序表L作快速排序QSort(L,1,L.length);}voidShellSort(SqList&L)//希尔排序{inti,d=L.length/2,j,w=0,k;while(w<d){w=1;for(i=w;i<L.length;i=i+d){k=i;for(j=i+d;j<L.length;j=j+d){if(L.elem[i].key>L.elem[j].key){k=j;bj5++;}}if(i!=k){L.elem[0].key=L.elem[i].key;L.elem[i].key=L.elem[k].key;L.elem[k].key=L.elem[0].key;yd5+=3;}w++;}d=d/2;w=1;}}voidHeapAdjust(SqList&L,ints,intm){//调整L.elem[s]的关键字，使L.elem[s…..m]成为一个大根堆SqListrc;rc.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!rc.elem)exit(0);intj;rc.elem[0]=L.elem[s];for(j=2*s;j<=m;j*=2){bj6++; if(j<m&&L.elem[j].key<L.elem[j+1].key) ++j; bj6++; if(!(rc.elem[0].key<L.elem[j].key))break;L.elem[s]=L.elem[j];s=j;yd6+=3;}L.elem[s]=rc.elem[0];}voidHeapSort(SqList&L){//对顺序表L进展堆排序inti; for(i=L.length/2;i>0;--i) HeapAdjust(L,i,L.length); for(i=L.length;i>1;--i) {L.elem[1]=L.elem[i]; yd6+=3; HeapAdjust(L,1,i-1); }}voidmain(){SqListL,M;inta;M.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!M.elem)exit(0);a:cout<<"---------------------------------部排序算法比拟-----------------------------\n";cout<<"************************************欢送使用***********************************\n";cout<<"**********************************(1)运行程序**********************************\n";cout<<"**********************************(2)退出系统**********************************\n";cout<<endl;cout<<"请选择:";scanf("%d",&a);switch(a){case1:system("cls");addlist(L);break;case2:cout<<"使用";exit(0);break;}random(L);memory(M,L);BubbleS