内部排序算法比较.docx

1、内部排序算法比较内部排序算法比较班级： 姓名： 学号： 完成日期：题目：试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。一需求分析1.对常用的6种内部排序算法进行比较：冒泡排序，直接插入排序，简单选择排序，快速排序，希尔排序，堆排序。2.待排序表的表长不小于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）3.最后要对结果作出简单分析，包括对各组数据得到结果波动大小的解释。二概要设计1.主界面设计对六种内部排序算法进行比较，可通过随机数程序产生几组数，要求用户手动

2、输入产生随机数的个数。运行界面如图所示：选择1运行程序，选择2退出程序2存储结构设计本程序采用顺序表结构，具体结构定义如下：typedef struct int key; ElemType;typedef struct ElemType *elem; int length;SqList;3.系统功能设计1）分配内存空间。创建顺序表2）利用伪随机数产生程序产生随机数，作为程序运行的数据3）实现每种排序算法的功能函数三模块设计1.模块设计2.系统子程序及功能设计本系统共设置13个函数，其中包括主函数。各函数名及功能说明如下。1） void addlist(SqList &L) /建立个空顺序表2）

3、 void random(SqList &L) /随机数产生函数3） void memory(SqList &M,SqList &L) /记录L，以保证每个排序函数使用一组随机数4） void BubbleSort(SqList &L) /冒泡排序5） void InsertSort(SqList &L) /直接插入排序6） void SelectSort(SqList &L) /选择排序7） int Partition(SqList &L,int low,int high) /返回快速排序枢轴的位置8） void QSort(SqList &L,int low,int high) /对子序列

4、作快速排序9） void QuickSort(SqList &L) /对数序表作快速排序10）void ShellSort (SqList &L) /希尔排序11）void HeapAdjust(SqList &L,int s,int m )/堆排序算法子程序12）void HeapSort(SqList &L) /对顺序表进行堆排序13）void main() /主函数，调用各模块函数3.函数主要调用关系四详细设计1.数据类型定义typedef struct int key; ElemType;typedef struct ElemType *elem; int length;SqList;

5、2.全局变量定义int bj1=0,yd1=0,bj2=0,yd2=0,bj3=0,yd3=0,bj4=0,yd4=0,bj5=0,yd5=0,bj6=0,yd6=0;/记录每种算法的比较，移动次数int n；/随机数的个数2.系统主要子程序详细设计（1）主函数设计模块主要是输入数据，以及程序界面的设计，调用系统的各个子程序，并输出结果。（详见源程序）（2）随机数产生模块利用伪随机数产生程序产生数据，并存储到顺序表中。void random(SqList &L) L.length=0;static bool first=true;if(first)srand(time(0);first=fal

6、se;/使每次产生的随机数不同for(int i=1;i30000) goto a; +L.length; （3）排序算法模块实现冒泡排序，直接插入排序，简单选择排序，快速排序，希尔排序以及堆排序的算法。（祥见源程序）五测试分析运行程序后，得到如图所示：输入：1输入：100选择1重复上述步骤，输入150，200，250，300得到另外四个结果：退出程序，请选择：2结果分析：冒泡排序，直接插入排序以及简单选择排序比较次数较多，快速排序，希尔排序及堆排序比较次数较少；并可得冒泡排序和直接插入排序相对较稳定，其他四种内部排序为不稳定排序。六源程序清单#includeiostream#includes

7、tdio.h#includestdlib.h#includestring.h#includetime.husing namespace std;#define LIST_INIT_SIZE 50000int bj1=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为记录关键字比较和移动的次数typedef struct int key; ElemType;typedef struct ElemType *elem; int length;SqList;void addlist(SqList

8、&L)/初始化顺序表a: printf(请输入你要输入的个数:); scanf(%d,&n); if(n50000) printf(超出范围重新输入n); goto a; L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L.elem)exit(0);void random(SqList &L)/随机数产生程序 L.length=0;static bool first=true;if(first)srand(time(0);first=false;/使输入相同个数时每次产生的随机数不同for(int i=1;i30000

9、) goto a; +L.length; void memory(SqList &M,SqList &L)/记录L，使每个排序算法都用一组相同的随机数 M.length=0; for(int i=1;in+1;i+) M.elemi.key=L.elemi.key; +M.length; void BubbleSort(SqList &L)/冒泡排序 int i,j; for(i=1;iL.length;i+) for(j=1;jL.elemj+1.key) L.elem0.key=L.elemj.key; L.elemj.key=L.elemj+1.key; L.elemj+1.key=L.

10、elem0.key; yd1+=3; void InsertSort(SqList &L)/直接插入排序 int i,j; for(i=2;i=L.length;i+) if(L.elemi.keyL.elemi-1.key) L.elem0.key=L.elemi.key; yd2+; j=i-1; bj2+; while(L.elem0.keyL.elemj.key) L.elemj+1.key=L.elemj.key; j-; yd2+; bj2+; L.elemj+1.key=L.elem0.key; yd2+; void SelectSort(SqList &L)/选择排序 int

11、i,j,k; for(i=1;iL.length;i+) k=i; for(j=i+1;jL.length;j+) bj3+; if(L.elemj.keyL.elemk.key)k=j; if(i!=k) L.elem0.key=L.elemi.key; L.elemi.key=L.elemk.key; L.elemk.key=L.elem0.key; yd3+=3; int Partition(SqList &L,int low,int high)/快速排序 int pivotkey; L.elem0=L.elemlow; yd4+; pivotkey=L.elemlow.key; whi

12、le (lowhigh) yd4+; while(low=pivotkey) -high; L.elemlow=L.elemhigh; bj4+; yd4+; while (lowhigh&L.elemlow.key=pivotkey) +low; L.elemhigh=L.elemlow; bj4+; yd4+; L.elemlow=L.elem0; yd4+; return low;void QSort(SqList &L,int low,int high)/对顺序表的子序列作快速排序 int pivotloc; if(lowhigh) pivotloc=Partition(L,low,h

13、igh); QSort(L,low,pivotloc-1); QSort(L,pivotloc+1,high); void QuickSort(SqList &L)/对顺序表L作快速排序 QSort(L,1,L.length);void ShellSort(SqList &L)/希尔排序 int i,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.elemj.key) k=j; bj5+; if(i!=k) L.elem0.key=L.elemi.key; L.elemi.key=L

14、.elemk.key; L.elemk.key=L.elem0.key; yd5+=3; w+; d=d/2; w=1; void HeapAdjust(SqList &L,int s,int m )/调整L.elems的关键字，使L.elems.m成为一个大根堆SqList rc; rc.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!rc.elem)exit(0);int j;rc.elem0=L.elems;for(j=2*s;j=m;j*=2)bj6+; if(jm&L.elemj.keyL.elemj+1.key

15、) +j; bj6+; if(!(rc.elem0.key0;-i) HeapAdjust(L,i,L.length); for(i=L.length;i1;-i) L.elem1=L.elemi; yd6+=3; HeapAdjust(L,1,i-1); void main() SqList L,M; int a; 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;

16、coutendl; cout请选择:; scanf(%d,&a);switch(a) case 1:system(cls);addlist(L);break;case 2:cout谢谢使用;exit(0);break; random(L); memory(M,L); BubbleSort(M); memory(M,L); InsertSort(M); memory(M,L); SelectSort(M); memory(M,L); QuickSort(M); memory(M,L); ShellSort(M); memory(M,L); HeapSort(L); cout *比较次数*移动次数*n; cout冒泡排序： bj1 yd1endl; cout直接插入： bj2 yd2endl; cout简单选择: bj3 yd3endl; cout快速排序: bj4 yd4endl; cout希尔排序: bj5 yd5endl; cout堆排序 : bj6 yd6endl; coutendl; goto a;七用户手册（1）本程序执行文件为“内部排序算法比较.exe”。（2）采用伪随机数程序产生随机数作为排序的数据。（3）用户只需按提示选择程序功能，并输入随机数个数即可得到结果，而且可以选择继续运行程序或者退出程序。