数据结构课程设计内部排序算法比较

1、 数据结构课程设计 题目：内部排序算法比较 学 院 计算机工程学院 班 级 计算1311 姓 名 学 号 成 绩 指导老师 评语：一：目的1 进一步掌握和利用c语言进行程设计的能力；2 进一步理解和运用结构化程设计的思想和方法；3 学会调试一个较长程序的基本方法；4 掌握书写程设计开发文档的能力（书写课程设计报告）。二：问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快

2、速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！三：基本要求（1） 从以下常用的内部排序算法至少选取5种进行比较：直接插入排序；折半折入排序；希尔排序；冒泡排序；快速排序；简单选择排序；堆排序；归并排序。（2） 待排序表的表长为20000；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字移动次数（关键字交换计为3次移动）。四：实验内容 对各种内部排序算法的时间复杂度有一个比较直观的感受，包括关键字比较次数和关键字移动次数。五：程

3、序调试与结果第一组数据：5个随机产生数 第二组数据：10个手动输入第三组数据 ： 8个随机产生第四组数据：50个随机产生数第五组数据：25个手动输入数六：调试分析（一）时间估算排序方法平均时间复杂度最好时间复杂度最坏时间复杂度直接插入排序o(n2)o(n)o(n2) 简单选择排序o(n2)o(n)o(n2)冒泡排序o(n2)o(n)o(n2)堆排序o(nlog2 n)o(nlog2 n)o(nlog2 n)归并排序o(nlog2 n) o(nlog2 n)o(nlog2 n)快速排序o(nlog2 n)o(nlog2 n)o(nlog2 n)希尔排序o(n3/2)o(nlogn)o(n2)（2

4、） 影响排序的因素1：待排序的记录数目n 的大小；2：记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小；3：关键字的结构及其分布情况；4：对排序稳定性的要求。（3） 分析 对于一般的排序，比较次数多，而交换次数相对较少；而快速排序比较次数和交换次数都较少，两者相差不如前者大。其中冒泡排序比较和交换次数都很大。七：数据结构 typedef struct int key; datatype; extern datatype rmaxnum;/定义结构体数组八：总结与体会 老实说，通过这一星期对数据结构的课程设计我对数据排序这章的理解加深了很多,也让我对编程更加的热爱，更感兴趣了。当一

5、个程序从你手中成功时，那种愉悦是无法形容的。不过惭愧的是程序并不是我自己完完全全独立编出来的，期间借助了同学的帮助及查询了一些资料。九：源程序清单（主要代码） #include #include #include#define maxnum 20000extern long cnmaxnum,mnmaxnum;typedef struct int key; datatype;extern datatype rmaxnum;/定义结构体数组void d_insertsort(datatype r,int n);/直接插入排序 void select_sort(datatype r,int n);

6、/简单选择排序 void bubble_sort(datatype r,long n);/冒泡排序 void heapadjust(datatype r,long s,long t);/堆排序 void heapsort(datatype r,int n);void merge(datatype r,datatype r1,long s,long m,long t);/归并排序 void msort(datatype r,datatype r1,long s,long t);void mergesort(datatype r,datatype r1,int n);long partition(

7、datatype r,long low,long high);/快速排序 void quick_sort(datatype r,long s,long t);void shellinsert(datatype r,int gap,int n);/希尔排序 void shellsort(datatype r, int n);void prin(datatype r,long n);#includexu.hlong cnmaxnum,mnmaxnum;datatype rmaxnum;/直接插入排序：void d_insertsort(datatype r,int n)int i,j;for(i=

8、2;i=n;i+)cn0+;if(ri.keyri-1.key)r0=ri;mn0+;for(j=i-1;r0.keyrj.key;j-)rj+1=rj;mn0+;cn0+;cn0+;rj+1=r0; mn0+;/简单选择排序void select_sort(datatype r,int n)/k记录第一次比较结果最小的下标int i,j,k;for(i=1;in;i+)k=i;for(j=i+1;j=n;j+)cn1+;if(rj.keyrk.key)k=j;if(i!=k)r0=rk;rk=ri;ri=r0;mn1+=3;/冒泡排序void bubble_sort(datatype r,l

9、ong n)long i,j;for(i=1;in-1;i+)for(j=2;j=n-i+1;j+)cn2+;if(rj.keyrj-1.key)r0=rj;rj=rj-1;rj-1=r0;mn2+=3;/堆排序void heapadjust(datatype r,long s,long t)datatype rc;long i,j;rc=rs;i=s;for(j=2*i;j=t;j=2*j)cn3+;if(jt&rj.keyrj.key)break;ri=rj;mn3+;i=j;ri=rc;mn3+;void heapsort(datatype r,int n)int i;for(i=n/2

10、;i0;i-)heapadjust(r,i,n);for(i=n;i1;i-)r0=r1;r1=ri;ri=r0;mn3+=3;heapadjust(r,1,i-1);/归并排序void merge(datatype r,datatype r1,long s,long m,long t)long i,j,k;i=s; j=m+1; k=s;while(i=m&j=t)cn4+;if(ri.keyrj.key)r1k+=ri+;mn4+;elser1k+=rj+;mn4+;while(i=m)r1k+=ri+;mn4+;while(j=t)r1k+=rj+;mn4+;void msort(dat

11、atype r,datatype r1,long s,long t)long m;datatype r2maxnum;if(s=t)r1s=rs;mn4+;elsem=(s+t)/2;msort(r,r2,s,m);msort(r,r2,m+1,t);merge(r2,r1,s,m,t);void mergesort(datatype r,datatype r1,int n)msort(r,r,1,n);/快速排序long partition(datatype r,long low,long high)r0=rlow;mn5+;while(lowhigh)while(low=r0.key)cn

12、5+;high-;if(lowhigh)rlow.key=rhigh.key;mn5+;low+;while(lowhigh&rlow.key=r0.key)cn5+; low+;if(lowhigh)rhigh.key=rlow.key;mn5+; high-;rlow=r0;mn5+;return low;void quick_sort(datatype r,long s,long t)long i;if(st)i=partition(r,s,t);quick_sort(r,s,i-1);quick_sort(r,i+1,t);/希尔排序void shellinsert(datatype

13、r,int gap,int n)int i, j;for (i = gap + 1; i = n; i+)if (ri.key0 & r0.keyrj.key; j = j - gap)rj + gap = rj;mn6+;cn6+;rj + gap = r0;mn6+;void shellsort(datatype r, int n)int gaps = 5, 3, 1 ;int k;for (k = 0; k3; +k)shellinsert(r, gapsk, n);void prin(datatype r,long n)/结果输出函数 long i;printf(排序的结果为：);fo

14、r(i=1;i20000)printf(超出输入个数范围，请重新输入！n);goto a;printf(请选择输入方式，1.手动输入 2.电脑产生随机数：);scanf(%d,&k);if(k=1) for(i=1;in+1;i+)scanf(%d,&ri.key);else srand(int)time(0);for(i=1;in+1;i+) ri.key=rand();printf(排序前元素顺序为：);for(i=1;in+1;i+)printf(%d ,ri.key);printf(n);for(i=1;i=n;i+)r3i.key=ri.key;r4i.key=ri.key;r5i.

15、key=ri.key;r6i.key=ri.key;r7i.key=ri.key;r8i.key=ri.key;printf(排序前的序列为：);for(i=1;i=n;i+)printf(%d ,ri);shellsort(r,n);/希尔排序d_insertsort(r3,n);/直接插入排序 select_sort(r4,n);/简单选择排序bubble_sort(r5,n);/冒泡排序heapsort(r6,n);/堆排序mergesort(r7,r2,n);/归并排序quick_sort(r8,1,n);/快速排序printf(n*比较结果*n);printf(n 排序方式 比较次数 移动次数n);printf(n 直接插入排序 %d %d n,cn0,mn0);prin(r3,n);printf(n 简单选择 %d %d n,cn1