数据结构课程设计

1、课 程 设 计 说 明 书课程名称： 数据结构和算法 设计题目： 多种排序 院 系： 计算机科学与信息工程学院 学生姓名： 学 号： 专业班级： 计科嵌入式（12-1） 指导教师： 年 月 日课 程 设 计 任 务 书设计题目表达式计算程序设计学生姓名所在院系计科专业、年级、班12计科（嵌入式）设计要求：1) 采用如下七种方法实现上述问题求解：插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序。2) 统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。并将数据序列和不同的查找算法的性能结果记录入txt文件。学生应完成的工作：1. 利用随机

2、函数产生N个随机整数（10000以上）。2. 对这些数字进行排序。3. 采用插入、希尔、起泡、快速、选择、归并、堆排序方法解决问题。4. 对不同的排序算法进行性能比较并记录。参考文献阅读： 1. 数据结构(C语言版) 严蔚敏 清华大学出版社 2. C语言程序设计 丁峻岭 中国铁道出版社 3. C程序设计 谭浩强 清华大学出版社工作计划：任务下达日期： 年 月 日 任务完成日期： 年 月 日指导教师（签名）： 学生（签名）： 多种排序摘 要： 排序是算法中最基础的问题之一，经典的排序算法是前人不断总结得到的，基于比较的方法是比较直观的方式，主要存在插入法排序、堆排序、希尔排序、归并排序、快速排序

3、，每一种排序算法都有自己的优缺点，比如插入法排序适用于那些长度短的排序，要是长的话，有些爱莫能助啦，堆排序主要是依据了二叉堆的特性，但是创建堆的过程也是一个复杂的问题，希尔排序的过程是一个不断精确的过程，但是目前也只是一个经验方式。归并排序是一个递归的问题，采用分治的思想实现，但是这种算法需要额外的存储空间，快速排序虽然是实践中比较常用的算法，但是对于有序的数组采用快速排序就是灾难。比较型算法的时间复杂度最优也只能到达O(NlogN)。关键词：归并排序快排排序选择排序冒泡排序插入排序堆排序希尔排序内部排序目 录1. 设计背景41.1问题描述41.2 问题分析42.设计方案42.1 算法设计4

4、2.2 功能模块分析63.主要算法流程图154. 结果与结论164.1正确结果164.2错误信息185. 算法复杂度以及稳定性分析186. 收获与致谢197. 参考文献198. 附件201. 设计背景1.1问题描述 利用随机函数产生N个随机整数（10000以上），对这些数进行多种方法进行排序。包括：插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序。1.2 问题分析经典的排序算法是前人不断总结得到的，基于比较的方法是比较直观的方式，主要存在插入法排序、堆排序、希尔排序、归并排序、快速排序，每一种排序算法都有自己的优缺点。2. 设计方案2.1 算法设计（1） 选择排序 在待排序的

5、一组数据元素中，选出最小的一个数据元素与第一个位置的数据元素交换；然后在剩下的数据元素当中再找最小的与第二个位置的数据元素交换，循环到只剩下最后一个数据元素为止。 （2） 冒泡排序 相邻的两个元素进行比较，将小的调到前面，大的调到后面。 （3） 插入排序 待排序的记录放在数组R0n-1中排序过程中某一时刻，R被划分成两个子区间R0,i-1 (有序和)Rin-1(无序)。直接插入的基本操作是将当前无序区的一个记录Ri插入到有序区R0i-1中适当的位置 （4） 快速排序 在待排序的数组的n个元素中取一个元素(一般取第一个)，将其移动到这样的位置：在其之前的元素的值都小于它，在其之后的元素都大于它，

6、这样是一趟快速排序；然后对数组的两个部分进行同样的操作，直到每部分只有一个记录为止；总之，每趟使表的第一个元素放在适当位置，将表两分，再对两子表进行同样的递归划分，直至划分的子表长度为1。（5）堆排序堆排序中 heap 算法的时间复杂度与堆所对应的完全二叉树的树高度 log2n 相关。而 heapsort 中对 heap 的调用数量级为n，所以堆排序的整个时间复杂度为O(nlog2n) 。并且堆排序是不稳定的。堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。（6）归并排序 将两个或两个以上的有序表组成一个新的有序表

7、。 （7） 希尔排序将无序数组分割为若干个子序列，子序列不是逐段分割的，而是相隔特定的增量的子序列，对各个子序列进行插入排序；然后再选择一个更小的增量，再将数组分割为多个子序列进行排序.最后选择增量为1，即使用直接插入排序，使最终数组成为有序。增量的选择：在每趟的排序过程都有一个增量，至少满足一个规则 增量关系 d1 > d2 > d3 >.> dt = 1 (t趟排序)；根据增量序列的选取其时间复杂度也会有变化，这个不少论文进行了研究，在此处就不再深究；本文采用首选增量为n/2,以此递推，每次增量为原先的1/2，直到增量为1。2.2 功能模块分析1. 数据输入：采取随

8、机函数实现输入数据表。int input_num()printf("您要给多少个数排序？ntt");scanf("%d",&data_num);srand(NULL);printf("随机产生%d个数:ntt",data_num);for(int i=1;i<=data_num;i+)data_arrayi=rand()%10000000; printf("%dn",data_arrayi);oldi=data_arrayi; printf("ntt");2. 数据输出：for循环

9、输出即可。int outnew0()printf("排序后的结果为:");for(int i=data_num;i>=1;i-)printf("%d%s",data_arrayi,i!=1?" ":"n");其中增加了输出空格与换行区别。3. 主界面实现：printf("DATE:May twenty 2014n"); printf("All Copyright Reserved 2014-2015 Wang Guangchun n"); printf("AD

10、DRESS: 604 AYITrnnn"); printf(" n"); printf("各种排序比较 n"); printf("默认从大到小输出，可以选择9进行切换n"); printf(" n"); printf(" * * n"); printf(" * * * n"); printf(" * * n"); printf(" * 520 * n"); printf(" * 欢迎 * n"); prin

11、tf(" * 使用 * n"); printf(" * * n"); printf(" * n"); printf("欢迎再次使用!nrn"); printf("*n"); printf("* . . . . . *n"); printf("* . . . . . . *n"); printf("* . . . . . . *n"); printf("* . . . . . . *n"); printf("

12、* . . . . *n"); printf("*n");4. 人机交互界面：printf("n n");printf("请输入指令 n");printf("* n");printf("$ 1.快速排序 $ n");printf("$ 2.归并排序 $ n");printf("$ 3.堆排序 $ n");printf("$ 4.希尔排序 $ n");printf("$ 5.插入排序 $ n");printf

13、("$ 6.选择排序 $ n");printf("$ 7.冒泡排序 $ n");printf("$ 8.重新随机输入 $ n");printf("$ 9.选择排序方式 $ n");printf("* n");printf(" 0.退出 n");printf(" n");printf("请选择：n"); printf("请输入指令 n"); printf("* n"); printf("$

14、 1.从小到大 $ n"); printf("$ 0.从大到小 $ n"); printf("* n"); printf(" 87.退出 n"); printf(" n"); printf("请选择：n");5. 排序方法的实现：（1）选择排序void chose_sort(int a,int n)int min,temp;for(int i=0;i<n;i+)min=i;for(int j=i;j<n;j+)if(amin>aj)min=j;temp=amin; a

15、min=ai;ai=temp;（2） 希尔排序void ShellInsert(int *a,int d,int n)for (int i=d;i<n;i+)/从第2个数据开始插入int j=i-d;int temp=ai;/记录要插入的数据while(j >= 0&&aj>temp)/从后向前，找到比其小的数的位置aj+d=aj;/向后挪动j-=d;if(j!=i-d)/存在比其小的数aj+d=temp;void ShellSort(int* a,int n)int d=n/2;/初始增量设为数组长度的一半while(d>=1)ShellInsert(

16、a,d,n);d=d/2;/每次增量变为上次的二分之一（3） 归并排序：void _merge(int a,int first,int mid,int last,int temp)int i=first,j=mid+1,m=mid,n=last,k=0;while(i<=m&&j<=n)if(ai<=aj)tempk+=ai+;elsetempk+=aj+;while(i<=m)tempk+=ai+;while(j<=n)tempk+=aj+;for(i=0;i<k;i+)afirst+i=tempi;void MergeSort(int a

17、,int first,int last,int temp) if(first<last) int mid=(first+last)/2; MergeSort(a,first,mid,temp); MergeSort(a,mid+1,last,temp); _merge(a,first,mid,last,temp); bool MergeSort(int a,int n) int *p=new intn; if(p=NULL) return false; else MergeSort(a,0,n-1,p); delete p; return true; （4） 堆排序：void HeapA

18、djust(int *a,int i,int size)/调整堆 int lchild=2*i;/i的左孩子节点序号 int rchild=2*i+1;/i的右孩子节点序号 int max=i;/临时变量 if(i<=size/2)/如果i是叶节点就不用进行调整 if(lchild<=size&&alchild>amax) max=lchild; if(rchild<=size&&archild>amax) max=rchild; if(max!=i) swap(ai,amax); HeapAdjust(a,max,size);/避

19、免调整之后以max为父节点的子树不是堆 void BuildHeap(int *a,int size)/建立堆 int i; for(i=size/2;i>=1;i-)/非叶节点最大序号值为size/2 HeapAdjust(a,i,size);void HeapSort(int *a,int size)/堆排序 int j=1; BuildHeap(a,size); for(int i=size;i>=1;i-) swap(a1,ai); /交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面 /BuildHeap(a,i-1); /将余下元素重新建立为大顶堆 HeapA

20、djust(a,1,i-1); /重新调整堆顶节点成为大顶堆 （5） 冒泡排序：void maopao()int temp;for(int i=1;i<=data_num;i+)for(int j=i+1;j<=data_num;j+)if(data_arrayi>data_arrayj)temp=data_arrayi;data_arrayi=data_arrayj;data_arrayj=temp;（6） 插入排序：void charu()int i,j;int temp; printf("插入排序:n");for(i=1;i<=data_num

21、;i+)int temp=data_arrayi;for (j=i;j>0 && temp<data_arrayj-1;j-)data_arrayj=data_arrayj-1;data_arrayj=temp;if(!t) outnew0();else outnew1();（7） 快速排序：void kuaisu1()/快速排序1 printf("快速排序:n"); sort(data_array+1,data_array+data_num+1); if(!t) outnew0();else outnew1();3.主要算法流程图 主程序产生1

22、组随机数将随机数保存在数组中希尔排序堆排序冒泡排序选择排序插入排序归并排序快速排序选择排序方式输出无序数组排序后的结果选择操作方式4. 结果与结论4.1 正确结果1. 主界面 人机交互2. 输入界面3. 选择排序方式4. 输出结果5. 退出界面4.2错误信息5. 算法复杂度以及稳定性分析下图反映了不同算法排序的时间复杂度的级别及其空间复杂度和稳定性。算法名称平均时间辅助空间稳定性冒泡排序O(n2)O(1)是选择排序O(n2)O(1)否插入排序O(n2)O(1)是归并排序O(nlog2n)O(n)是快速排序O(nlog2n)O(n)否堆排序O(nlog2n)O(1)否希尔排序O(1)否下图表明了

23、各种算法在不同数据规模下，完成排序所消耗的时间（毫秒为单位），从表中可以显然看出O(n2)的排序算法比O(nlog2n)的算法 时间多出几百上千倍，而且随着数据数据规模增大时间比也会随着增大；因为排序的数据采用随机数，顺序将被打乱，快速排序算法优于其他排序算法。算法名称1万2万3万4万5万6万7万8万9万10万冒泡排序14425497122062186134017491486739488880111939139071选择排序19981617903254506271669645126361610219643插入排序17871716282882445864468822116491454717914

24、归并排序36912151822262833快速排序25811141821252932堆排序371216192326303437希尔排序3811152424293540416. 收获与致谢通过这次课程设计作业我着实感受了一次编程的乐趣，从中学到了不少知识， 虽然都说“程序数据结构算法”，但我们在学习运用数据结构编程之前，并没能深刻体会到这一点，直到这次课设实践。 我们感受最深的一点是：以前用C编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意识和简单的语句来堆砌出一段程序。但现在编程感觉完全不同了。在编写一个程序之前，自己能够综合考虑各种因素，首先选取自己需要的数

25、据结构，然后选定一种或几种存储结构来具体的决定后面的函数的主要风格。最后在编写每一个函数之前，可以仔细斟酌比对，挑选出最适合当前状况的算法。这样，即使在完整的还没有写出来之前，自己心中已经有了明确的原图了。这样无形中就提高了自己编写的程序的质量。我们还体会到深刻理解数据结构的重要性。只有真正理解定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。这次实验中我们也出现过一些错误。但我们经过反复调试后，发现并做了修改，从而完成了此次课程设计。 在这次的数据结构课程设计中，我此次的题目是各种排序，排序实际上是编程设计中应用比较广泛的知识，通过本次

26、设计，我对一些基本的内部排序有了很好的理解和掌握，并且通过此次课程设计中的程序运行结果很好的理解了排序各种算法的稳定性和时间复杂度，既巩固了课堂上学到的排序理论，又为自己的编程增强了实践。总之，在这次的数据结构课程设计中，收获还是蛮多的。也让自己对数据结构这门课程有了更好的认识，相信在越来越多的尝试之后，自己会不断进步不断提高的。7. 参考文献1.数据结构(C语言版) 严蔚敏 清华大学出版社2.C语言程序设计 丁峻岭 中国铁道出版社3.C程序设计 谭浩强 清华大学出版社8. 附件程序源代码：#include<cstdio>#include<algorithm>#incl

27、ude<iostream>#include<cmath>#include<cstring>#include<string>#include<stack>#include<map>#include<ctime>#include<queue>#include<vector>#include<set>#include<cstdlib>using namespace std;const int N=1000010;int data_num,data_arrayN,data

28、_arrayyN;int oldN,aN,t;/数据输入int input_num()printf("您要给多少个数排序？ntt");scanf("%d",&data_num);srand(NULL);printf("随机产生%d个数:ntt",data_num);for(int i=1;i<=data_num;i+)data_arrayi=rand()%10000000; printf("%dn",data_arrayi);oldi=data_arrayi; printf("ntt&quo

29、t;);/排序后数据输出 从大到小 data_num 1int outnew0()printf("排序后的结果为:");for(int i=data_num;i>=1;i-)printf("%d%s",data_arrayi,i!=1?" ":"n");/排序后逆序数据输出 从小到大 1 data_numint outnew1()printf("排序后的结果为:");for(int i=1;i<=data_num;i+) printf("%d%s",data_ar

30、rayi,i!=data_num?" ":"n");/排序后数据输出 从大到小 data_num-1 0int outnew2()printf("排序后的结果为:");for(int i=data_num-1;i>=0;i-)printf("%d%s",data_arrayyi,i!=0?" ":"n");/排序后逆序数据输出 从小到大 0 data_num-1int outnew3()printf("排序后的结果为:");for(int i=0;i

31、<data_num;i+) printf("%d%s",data_arrayyi,i!=data_num-1?" ":"n");/插入排序void charu()int i,j;int temp; printf("插入排序:n");for(i=1;i<=data_num;i+)int temp=data_arrayi;for (j=i;j>0 && temp<data_arrayj-1;j-)data_arrayj=data_arrayj-1;data_arrayj=temp

32、;if(!t) outnew0();else outnew1();/冒泡排序void maopao()int temp;for(int i=1;i<=data_num;i+)for(int j=i+1;j<=data_num;j+)if(data_arrayi>data_arrayj)temp=data_arrayi;data_arrayi=data_arrayj;data_arrayj=temp;/选择排序void chose_sort(int a,int n)int min,temp;for(int i=0;i<n;i+)min=i;for(int j=i;j<

33、;n;j+)if(amin>aj)min=j;temp=amin; amin=ai;ai=temp;/堆排序void HeapAdjust(int *a,int i,int size)/调整堆 int lchild=2*i;/i的左孩子节点序号 int rchild=2*i+1;/i的右孩子节点序号 int max=i;/临时变量 if(i<=size/2)/如果i是叶节点就不用进行调整 if(lchild<=size&&alchild>amax) max=lchild; if(rchild<=size&&archild>am

34、ax) max=rchild; if(max!=i) swap(ai,amax); HeapAdjust(a,max,size);/避免调整之后以max为父节点的子树不是堆 void BuildHeap(int *a,int size)/建立堆 int i; for(i=size/2;i>=1;i-)/非叶节点最大序号值为size/2 HeapAdjust(a,i,size);void HeapSort(int *a,int size)/堆排序 int j=1; BuildHeap(a,size); for(int i=size;i>=1;i-) swap(a1,ai); /交换堆

35、顶和最后一个元素，即每次将剩余元素中的最大者放到最后面 /BuildHeap(a,i-1); /将余下元素重新建立为大顶堆 HeapAdjust(a,1,i-1); /重新调整堆顶节点成为大顶堆 /快速排序可以选择用algorithm里的sort排序实现void kuaisu1()/快速排序1 printf("快速排序:n"); sort(data_array+1,data_array+data_num+1); if(!t) outnew0();else outnew1();void kuaisu2()/快速排序2 sort(data_array+1,data_array+

36、data_num+1); if(!t) outnew0();else outnew1();/希尔排序void ShellInsert(int *a,int d,int n)for (int i=d;i<n;i+)/从第2个数据开始插入int j=i-d;int temp=ai;/记录要插入的数据while(j >= 0&&aj>temp)/从后向前，找到比其小的数的位置aj+d=aj;/向后挪动j-=d;if(j!=i-d)/存在比其小的数aj+d=temp;void ShellSort(int* a,int n)int d=n/2;/初始增量设为数组长度的一

37、半while(d>=1)ShellInsert(a,d,n);d=d/2;/每次增量变为上次的二分之一/归并排序void _merge(int a,int first,int mid,int last,int temp)int i=first,j=mid+1,m=mid,n=last,k=0;while(i<=m&&j<=n)if(ai<=aj)tempk+=ai+;elsetempk+=aj+;while(i<=m)tempk+=ai+;while(j<=n)tempk+=aj+;for(i=0;i<k;i+)afirst+i=tem

38、pi;void MergeSort(int a,int first,int last,int temp) if(first<last) int mid=(first+last)/2; MergeSort(a,first,mid,temp); MergeSort(a,mid+1,last,temp); _merge(a,first,mid,last,temp); bool MergeSort(int a,int n) int *p=new intn; if(p=NULL) return false; else MergeSort(a,0,n-1,p); delete p; return t

39、rue; /输出void print() printf("欢迎再次使用!nrn"); printf("*n"); printf("* . . . . . *n"); printf("* . . . . . . *n"); printf("* . . . . . . *n"); printf("* . . . . . . *n"); printf("* . . . . *n"); printf("*n");/主函数，显示菜单并进行算法选择

40、int main() printf("DATE:May twenty 2014n"); printf("All Copyright Reserved 2014-2015 Wang Guangchun n"); printf("ADDRESS: 604 AYITrnnn"); printf(" n"); printf("各种排序比较 n"); printf("默认从大到小输出，可以选择9进行切换n"); printf(" n"); printf("

41、 * * n"); printf(" * * * n"); printf(" * * n"); printf(" * 520 * n"); printf(" * 欢迎 * n"); printf(" * 使用 * n"); printf(" * * n"); printf(" * n");int n;/变量定义用于菜单选择input_num();/调用输入函数，请求用户输入数据while(true)printf("n n");

42、printf("请输入指令 n");printf("* n");printf("$ 1.快速排序 $ n");printf("$ 2.归并排序 $ n");printf("$ 3.堆排序 $ n");printf("$ 4.希尔排序 $ n");printf("$ 5.插入排序 $ n");printf("$ 6.选择排序 $ n");printf("$ 7.冒泡排序 $ n");printf("$ 8.重新随机输入 $ n");printf("$ 9.选择排序方式 $ n");printf("* n");printf(" 0.退出 n");printf(" n");printf("请选择：n");scanf("%d",&n);switch(n) case 1:/快速排序 kuaisu1();break; case 2:/归并排序 printf("归并排序：n"); for(int j=0;j<data_num;j+) d