内部排序算法比较

内部排序算法比较班级：姓名：学号：完成日期：题目：试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。一．需求分析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.函数主要调用关系主程序模块随机数产生模块排序算法模块四．详细设计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;in+1;i++)5124321106811713）main（）9a:{L.elem[i].key=rand();if(L.elem[i].key30000)gotoa;++L.length;}（3）排序算法模块实现冒泡排序，直接插入排序，简单选择排序，快速排序，希尔排序以及堆排序的算法。（祥见源程序）五．测试分析运行程序后，得到如图所示：输入：1输入：100选择1重复上述步骤，输入150，200，250，300得到另外四个结果：退出程序，请选择：2结果分析：冒泡排序，直接插入排序以及简单选择排序比较次数较多，快速排序，希尔排序及堆排序比较次数较少；并可得冒泡排序和直接插入排序相对较稳定，其他四种内部排序为不稳定排序。六．源程序清单#includeiostream#includestdio.h#includestdlib.h#includestring.h#includetime.husingnamespacestd;#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(n50000){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;in+1;i++)a:{L.elem[i].key=rand();if(L.elem[i].key30000)gotoa;++L.length;}}voidmemory(SqList&M,SqList&L)//记录L，使每个排序算法都用一组相同的随机数{M.length=0;for(inti=1;in+1;i++){M.elem[i].key=L.elem[i].key;++M.length;}}voidBubbleSort(SqList&L)//冒泡排序{inti,j;for(i=1;iL.length;i++){for(j=1;jL.length-i+1;j++){bj1++;if(L.elem[j].keyL.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].keyL.elem[i-1].key){L.elem[0].key=L.elem[i].key;yd2++;j=i-1;bj2++;while(L.elem[0].keyL.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;iL.length;i++){k=i;for(j=i+1;jL.length;j++){bj3++;if(L.elem[j].keyL.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(lowhigh){yd4++;while(lowhigh&&L.elem[high].key=pivotkey)--high;L.elem[low]=L.elem[high];bj4++;yd4++;while(lowhigh&&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(lowhigh){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(wd){w=1;for(i=w;iL.length;i=i+d){k=i;for(j=i+d;jL.length;j=j+d){if(L.elem[i].keyL.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(jm&&L.elem[j].keyL.elem[j+1].key)++j;bj6++;if(!(rc.elem[0].keyL.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;i0;--i)HeapAdjust(L,i,L.length);for(i=L.length;i1;--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*