内部排序算法对比

本文格式为Word版，下载可任意编辑——内部排序算法对比内部排序算法比较

班级：姓名：学号：完成日期：

题目：试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。一．需求分析

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}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

staticboolfirst=true;if(first){

srand(time(0));first=false;

}//使每次产生的随机数不同for(inti=1;i30000)gotoa;++L.length;}

（3）排序算法模块实现冒泡排序，直接插入排序，简单项选择择排序，快速排序，希尔排序以及堆排序的算法。（祥见源程序）五．测试分析

运行程序后，得到如下图：

输入：1

输入：100

选择1重复上述步骤，输入150，200，250，300得到另外四个结果：

退出程序，请选择：2

结果分析：冒泡排序，直接插入排序以及简单项选择择排序比较次数较多，快速排序，希尔排序及堆排序比较次数较少；并可得冒泡排序和直接插入排序相对较稳定，其他四种内部排序为不稳定排序。

六．源程序清单#include\#include\#include\#include\#include%usingnamespacestd;

#defineLIST_INIT_SIZE50000

intbj1=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.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(0);}

voidrandom(SqList

staticboolfirst=true;if(first){

srand(time(0));first=false;

}//使输入一致个数时每次产生的随机数不同for(inti=1;i30000)gotoa;++L.length;}}

voidmemory(SqListfor(inti=1;iL.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

for(i=2;iL.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

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;j0;--i)HeapAdjust(L,i,L.length);for(i=L.length;i>1;--i)

{L.elem[1]=L.elem[i];yd6+=3;HeapAdjust(L,