内部排序算法比较

1、数据结构实验报告实习6 存储管理、查找和排序题目:内部排序算法比较班级：1403011班 姓名：付尧 学号完成日期：2016.1.10一需求分析(1)对起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、归并排序算法进行比较。(2)待排序的元素的关键字为整数，其中数据要用伪随机产生程序产生，并且至少用5组的输入数据做比较，再使用各种算法对其进行排序，记录其排序时间，再汇总比较。(3)演示程序以人机对话的形式进行，每次测试完毕显示各种比较指标值，比较次数、移动次数和排序时间的列表，并用条形图即星号表示出来，以便比较各种排序的优劣。二概要设计1. 基本操作： (1)

2、 输入要排序的数据数目 (2) 抽象数据类型定义typedef struct int key; ElemType; /关键字typedef struct ElemType *elem; int length;SqList;/分配顺序存储结构 (3) 存储结构：本程序采用了线性表的顺序存储结构。 (4) 算法设计：简单选择排序：运用顺序表。时间复杂度O(n2)，空间复杂度O(1)。起泡排序：时间复杂度O(n2)，空间复杂度O(1)直接插入排序：时间复杂度O(n2)，空间复杂度O(1)希尔排序：时间复杂度O(n1.3)，空间复杂度O(1)快速排序：时间复杂度O(nlog2n)，空间复杂度O(nlo

3、g2n)归并排序：时间复杂度O(nlog2n)，空间复杂度O(n)2 本程序包含8个模块：(1)伪随机产生数据模块：本程序要求数据是要用伪随机产生程序产生，再用不同排序算法进行排序。(2)简单选择排序模块：运用简单选择排序法对伪随机产生的数据进行排序。(3) 起泡排序模块：运用起泡排序法对伪随机产生的数据进行排序。(4)直接插入排序模块：运用直接插入排序法对伪随机产生的数据进行排序。(5)希尔排序模块：运用希尔排序法对伪随机产生的数据进行排序。(6)快速排序：运用快速排序法对伪随机产生的数据进行排序。(7)归并排序：运用归并排序法对伪随机产生的数据进行排序。(8)条形图表示比较结果：统计6种排

4、序算法的比较结果，用条形图表示出来。 三调试分析（1）本题采用结构体储存数据，使相关信息紧密相联系，便于编辑和输出。（2）通过这道题，让我深入理解了内部排序算法，获益良多。调试编码过程中产生的小错误，让我的编程习惯有所改善。四用户使用说明（1）本程序的运行环境为VS2010。（2）进入演示程序后可得到结果。五测试结果点击运行，首先出现的是要输入伪随机产生数据的数目，如图9所示。图9 输入界面输入数据个数然后回车，可显示出不同排序算法的比较次数、移动次数和排序用时。如图10所示。图10 显示比较结果界面显示比较次数的条形图。如图11所示。图11 比较次数条形图界面显示移动次数条形图。如图12所示

5、图12 移动次数条形图界面显示排序用时条形图。如图13所示图13 排序用时条形图界面六、附录 #include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>#include<time.h>#define LIST_INIT_SIZE 30000int bj1,yd1,n,com,mov;long int A5,B5;double t0,t1,t2,t3,t4,t5,C5;clock_t start_t,end_t;typedef struct int key;

6、 ElemType;typedef struct ElemType *elem; int length;SqList;void addlist(SqList &L) int i;a: printf("请输入你要输入的个数:"); scanf("%d",&n); if(n>20000) printf("超出范围重新输入!n"); goto a; L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L.elem)exit(0); L.length

7、=0; for(i=1;i<n+1;i+) b: L.elemi.key=rand(); if(L.elemi.key>20000)goto b; +L.length; void SelectSort(SqList &L) /简单选择排序 start_t=clock(); int i,j,k,com=0,mov=0; for(i=1;i<L.length;i+) k=i; for(j=i+1;j<L.length;j+) com+; if(L.elemj.key<L.elemk.key)k=j; if(i!=k) L.elem0.key=L.elemi.k

8、ey; L.elemi.key=L.elemk.key; L.elemk.key=L.elem0.key; mov+=3; end_t=clock(); printf("比较次数为 %d移动次数为 %dn",com,mov); t0=(double)(end_t-start_t)/CLK_TCK; printf("排序用时为 %fn",t0); A0=com; B0=mov; C0=t0;void bubblesort(SqList &L) /起泡排序 start_t=clock(); int i=1,j,com=0,mov=0; while(i

9、<L.length) for(j=1;j<L.length;j+) com+; if(L.elemj.key>L.elemj+1.key) L.elem0.key=L.elemj.key; L.elemj.key=L.elemj+1.key; L.elemj+1.key=L.elem0.key; mov+=3; i+; end_t=clock(); printf("比较次数为 %d移动次数为 %dn",com,mov); t1=(double)(end_t-start_t)/CLK_TCK; printf("排序用时为 %fn",t1)

10、; A1=com; B1=mov; C1=t1;void InsertSort(SqList &L) /直接插入排序 start_t=clock(); int i,j,com=0,mov=0; for(i=2;i<=L.length;i+) if(L.elemi.key<L.elemi-1.key) L.elem0.key=L.elemi.key; mov+; j=i-1; com+; while(L.elem0.key<L.elemj.key) L.elemj+1.key=L.elemj.key; j-; mov+; com+; L.elemj+1.key=L.el

11、em0.key; mov+; end_t=clock(); printf("比较次数为 %d移动次数为 %dn",com,mov); t2=(double)(end_t-start_t)/CLK_TCK; printf("排序用时为 %fn",t2); A2=com; B2=mov; C2=t2;void xier(SqList &L) /希尔排序 start_t=clock(); int i,d=L.length/2,j,w=0,k,com=0,mov=0; while(w<d) w=1; for(i=w;i<L.length;i=

12、i+d) k=i; for(j=i+d;j<L.length;j=j+d) if(L.elemi.key>L.elemj.key) k=j; com+; if(i!=k) L.elem0.key=L.elemi.key; L.elemi.key=L.elemk.key; L.elemk.key=L.elem0.key; mov+=3; w+; d=d/2; w=1; end_t=clock(); printf("比较次数为 %d移动次数为 %dn",com,mov); t3=(double)(end_t-start_t)/CLK_TCK; printf(&quo

13、t;排序用时为 %fn",t3); A3=com; B3=mov; C3=t3;void BeforeSort() yd1=0,bj1=0;void display(int m,int n) printf("比较次数为 %d移动次数为 %dn",m,n);int Partition(SqList L,int low,int high) /快速排序 int pivotkey; L.elem0=L.elemlow; yd1+; pivotkey=L.elemlow.key; while (low<high) yd1+; while(low<high&

14、;&L.elemhigh.key>=pivotkey) -high; L.elemlow=L.elemhigh; bj1+; yd1+; while (low<high&&L.elemlow.key<=pivotkey) +low; L.elemhigh=L.elemlow; bj1+; yd1+; L.elemlow=L.elem0; yd1+; return low;void QSort(SqList &L,int low,int high) int pivotloc; if(low<high) pivotloc=Partition(

15、L,low,high); QSort(L,low,pivotloc-1); QSort(L,pivotloc+1,high); void QuickSort(SqList &L) start_t=clock(); BeforeSort(); QSort(L,1,L.length); display(bj1,yd1); end_t=clock(); t4=(double)(end_t-start_t)/CLK_TCK; printf("排序用时为 %fn",t4); A4=bj1; B4=yd1; C4=t4;void Merge(ElemType R,ElemTyp

16、e R1,int low,int m,int high) /归并排序 int i=low, j=m+1, k=low; while(i<=m&&j<=high) if(Ri.key<=Rj.key) bj1+; R1k=Ri; yd1+; i+; k+; else bj1+; R1k=Rj; yd1+; j+; k+; while(i<=m) R1k=Ri; yd1+; i+; k+; while(j<=high) R1k=Rj; yd1+; j+; k+; void MergePass(ElemType R,ElemType R1,int len

17、gth, int n) int i=0,j; while(i+2*length-1<n) Merge(R,R1,i,i+length-1,i+2*length-1); i=i+2*length; if(i+length-1<n-1) Merge(R,R1,i,i+length-1,n-1); else for(j=i;j<n;j+) R1j=Rj;void MSort(ElemType R,ElemType R1,int n) int length=1; while (length<n) MergePass(R,R1,length,n); length=2*length

18、; MergePass(R1,R,length,n); length=2*length; void MergeSort(SqList &L) start_t=clock(); BeforeSort(); MSort(L.elem,L.elem,L.length); display(bj1,yd1); end_t=clock(); t5=(double)(end_t-start_t)/CLK_TCK; printf("排序用时为 %fn",t5); A5=bj1; B5=yd1; C5=t5;void printf(SqList &L)long int d6;

19、int i,n; printf("n比较次数n");printf("n=n"); for(i=0;i<5;i+) di= sqrt (Ai/A5); printf("n 归并排序： *"); printf("n=n"); printf(" 选择排序： "); for(n=0,i=0;n<=di;n+) printf("*"); printf("n=n"); printf(" 冒泡排序： "); for(n=0,i=1;n&l

20、t;=di;n+) printf("*"); printf("n=n"); printf(" 直插排序： "); for(n=0,i=2;n<=di;n+) printf("*"); printf("n=n"); printf(" 希尔排序： "); for(n=0,i=3;n<=di;n+) printf("*"); printf("n=n"); printf(" 快排排序： "); for(n=0,i

21、=4;n<=di;n+) printf("*"); printf("n=n"); printf("n移动次数n"); printf("n=n"); double e6; for(i=0;i<6;i+) ei= sqrt (Bi/B3); printf("n 希尔排序： *"); printf("n=n"); printf(" 选择排序： "); for(n=0,i=0;n<=ei;n+) printf("*"); pr

22、intf("n=n"); printf(" 冒泡排序： "); for(n=0,i=1;n<=ei;n+) printf("*"); printf("n=n"); printf(" 直插排序： "); for(n=0,i=2;n<=ei;n+) printf("*"); printf("n=n"); printf(" 快排排序： "); for(n=0,i=4;n<=ei;n+) printf("*"

23、;); printf("n=n");printf(" 归并排序： "); for(n=0,i=5;n<=ei;n+) printf("*"); printf("n=n"); printf("n排序用时n"); printf("n=n"); double f6; for(i=0;i<6;i+) fi= sqrt (Ci/0.001); printf("n 希尔排序： *"); printf("n=n"); printf(" 选择排序： "); for(n=0,i=0;n<=fi;n+) printf("*"); printf("n=n&quo