数据结构专业课程设计样本.doc

课 程 设 计 说 明 书课程名称： 数据结构和算法 设计题目： 多个排序 院 系： 计算机科学和信息工程学院 学生姓名： 学 号： 专业班级： 计科嵌入式（12-1） 指导老师： 年 月 日课 程 设 计 任 务 书设计题目表示式计算程序设计学生姓名所在院系计科专业、年级、班12计科（嵌入式）设计要求：1) 采取以下七种方法实现上述问题求解：插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序。2) 统计每一个排序方法性能（以上机运行程序所花费时间为准进行对比），找出其中两种较快方法。并将数据序列和不一样查找算法性能结果统计入txt文件。学生应完成工作：1. 利用随机函数产生N个随机整数（10000以上）。2. 对这些数字进行排序。3. 采取插入、希尔、起泡、快速、选择、归并、堆排序方法处理问题。4. 对不一样排序算法进行性能比较并统计。参考文件阅读： 1. 数据结构(C语言版) 严蔚敏 清华大学出版社 2. C语言程序设计 丁峻岭 中国铁道出版社 3. C程序设计 谭浩强 清华大学出版社工作计划：任务下达日期： 年 月 日 任务完成日期： 年 月 日指导老师（署名）： 学生（署名）： 多个排序摘 要： 排序是算法中最基础问题之一，经典排序算法是前人不停总结得到，基于比较方法是比较直观方法，关键存在插入法排序、堆排序、希尔排序、归并排序、快速排序，每一个排序算法全部有自己优缺点，比如插入法排序适适用于那些长度短排序，要是长话，有些爱莫能助啦，堆排序关键是依据了二叉堆特征，不过创建堆过程也是一个复杂问题，希尔排序过程是一个不停正确过程，不过现在也只是一个经验方法。归并排序是一个递归问题，采取分治思想实现，不过这种算法需要额外存放空间，快速排序即使是实践中比较常见算法，不过对于有序数组采取快速排序就是灾难。比较型算法时间复杂度最优也只能抵达O(NlogN)。关键词：归并排序快排排序选择排序冒泡排序插入排序堆排序希尔排序内部排序目 录1. 设计背景41.1问题描述41.2 问题分析42.设计方案42.1 算法设计4 2.2 功效模块分析63.关键算法步骤图154. 结果和结论164.1正确结果164.2错误信息185. 算法复杂度和稳定性分析186. 收获和致谢197. 参考文件198. 附件201. 设计背景1.1问题描述 利用随机函数产生N个随机整数（10000以上），对这些数进行多个方法进行排序。包含：插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序。1.2 问题分析经典排序算法是前人不停总结得到，基于比较方法是比较直观方法，关键存在插入法排序、堆排序、希尔排序、归并排序、快速排序，每一个排序算法全部有自己优缺点。2. 设计方案2.1 算法设计（1） 选择排序 在待排序一组数据元素中，选出最小一个数据元素和第一个位置数据元素交换；然后在剩下数据元素当中再找最小和第二个位置数据元素交换，循环到只剩下最终一个数据元素为止。 （2） 冒泡排序 相邻两个元素进行比较，将小调到前面，大调到后面。 （3） 插入排序 待排序统计放在数组R0n-1中排序过程中某一时刻，R被划分成两个子区间R0,i-1 (有序和)Rin-1(无序)。直接插入基础操作是将目前无序区一个统计Ri插入到有序区R0i-1中合适位置 （4） 快速排序 在待排序数组n个元素中取一个元素(通常取第一个)，将其移动到这么位置：在其之前元素值全部小于它，在其以后元素全部大于它，这么是一趟快速排序；然后对数组两个部分进行一样操作，直到每部分只有一个统计为止；总而言之，每趟使表第一个元素放在合适位置，将表两分，再对两子表进行一样递归划分，直至划分子表长度为1。（5）堆排序堆排序中 heap 算法时间复杂度和堆所对应完全二叉树树高度 log2n 相关。而 heapsort 中对 heap 调用数量级为n，所以堆排序整个时间复杂度为O(nlog2n) 。而且堆排序是不稳定。堆排序利用了大根堆(或小根堆)堆顶统计关键字最大(或最小)这一特征，使得在目前无序区中选择最大(或最小)关键字统计变得简单。（6）归并排序 将两个或两个以上有序表组成一个新有序表。 （7） 希尔排序将无序数组分割为若干个子序列，子序列不是逐段分割，而是相隔特定增量子序列，对各个子序列进行插入排序；然后再选择一个更小增量，再将数组分割为多个子序列进行排序.最终选择增量为1，即使用直接插入排序，使最终数组成为有序。增量选择：在每趟排序过程全部有一个增量，最少满足一个规则 增量关系 d1 d2 d3 . dt = 1 (t趟排序)；依据增量序列选择其时间复杂度也会有改变，这个不少论文进行了研究，在此处就不再深究；本文采取首选增量为n/2,以此递推，每次增量为原先1/2，直到增量为1。2.2 功效模块分析1. 数据输入：采取随机函数实现输入数据表。int input_num()printf(您要给多少个数排序？ntt);scanf(%d,&data_num);srand(NULL);printf(随机产生%d个数:ntt,data_num);for(int i=1;i=1;i-)printf(%d%s,data_arrayi,i!=1? :n);其中增加了输出空格和换行区分。3. 主界面实现：printf(DATE:May twenty n); printf(All Copyright Reserved - Wang Guangchun n); printf(ADDRESS: 604 AYITrnnn); printf( n); printf(多种排序比较 n); printf(默认从大到小输出，能够选择9进行切换n); printf( n); printf( * * n); printf( * * * n); printf( * * n); printf( * 520 * n); printf( * 欢迎 * n); printf( * 使用 * n); printf( * * n); printf( * n); printf(欢迎再次使用!nrn); printf(*n); printf(* . . . . . *n); printf(* . . . . . . *n); printf(* . . . . . . *n); printf(* . . . . . . *n); printf(* . . . . *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($ 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($ 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;in;i+)min=i;for(int j=i;jaj)min=j;temp=amin; amin=ai;ai=temp;（2） 希尔排序void ShellInsert(int *a,int d,int n)for (int i=d;i= 0&ajtemp)/从后向前，找到比其小数位置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(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;ik;i+)afirst+i=tempi;void MergeSort(int a,int first,int last,int temp) if(firstlast) 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 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(lchildamax) max=lchild; if(rchildamax) 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); /交换堆顶和最终一个元素，即每次将剩下元素中最大者放到最终面 /BuildHeap(a,i-1); /将余下元素重新建立为大顶堆 HeapAdjust(a,1,i-1); /重新调整堆顶节点成为大顶堆 （5） 冒泡排序：void maopao()int temp;for(int i=1;i=data_num;i+)for(int j=i+1;jdata_arrayj)temp=data_arrayi;data_arrayi=data_arrayj;data_arrayj=temp;（6） 插入排序：void charu()int i,j;int temp; printf(插入排序:n);for(i=1;i0 & tempdata_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组随机数将随机数保留在数组中希尔排序堆排序冒泡排序选择排序插入排序归并排序快速排序选择排序方法输出无序数组排序后结果选择操作方法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)否下图表明了多种算法在不一样数据规模下，完成排序所消耗时间（毫秒为单位），从表中能够显然看出O(n2)排序算法比O(nlog2n)算法 时间多出几百上千倍，而且伴随数据数据规模增大时间比也会伴随增大；因为排序数据采取随机数，次序将被打乱，快速排序算法优于其它排序算法。算法名称1万2万3万4万5万6万7万8万9万10万冒泡排序14425497122062186134017491486739488880111939139071选择排序19981617903254506271669645126361610219643插入排序17871716282882445864468822116491454717914归并排序36912151822262833快速排序25811141821252932堆排序371216192326303437希尔排序3811152424293540416. 收获和致谢经过这次课程设计作业我着实感受了一次编程乐趣，从中学到了不少知识， 即使全部说“程序数据结构算法”，但我们在学习利用数据结构编程之前，并没能深刻体会到这一点，直到这次课设实践。 我们感受最深一点是：以前用C编程，只是重视怎样编写函数能够完成所需要功效，似乎没有明确战术，只是凭单纯意识和简单语句来堆砌出一段程序。但现在编程感觉完全不一样了。在编写一个程序之前，自己能够综合考虑多种原因，首先选择自己需要数据结构，然后选定一个或多个存放结构来具体决定后面函数关键风格。最终在编写每一个函数之前，能够仔细斟酌比对，挑选出最适合目前情况算法。这么，即使在完整还没有写出来之前，自己心中已经有了明确原图了。这么无形中就提升了自己编写程序质量。我们还体会到深刻了解数据结构关键性。只有真正了解定义数据类型好处，才能用好这么一个数据结构。了解经典数据结构性质是很有用，它往往是编写程序关键。这次试验中我们也出现过部分错误。但我们经过反复调试后，发觉并做了修改，从而完成了此次课程设计。 在这次数据结构课程设计中，我此次题目是多种排序，排序实际上是编程设计中应用比较广泛知识，经过此次设计，我对部分基础内部排序有了很好了解和掌握，而且经过此次课程设计中程序运行结果很好了解了排序多种算法稳定性和时间复杂度，既巩固了课堂上学到排序理论，又为自己编程增强了实践。总而言之，在这次数据结构课程设计中，收获还是蛮多。也让自己对数据结构这门课程有了愈加好认识，相信在越来越多尝试以后，自己会不停进步不停提升。7. 参考文件1.数据结构(C语言版) 严蔚敏 清华大学出版社2.C语言程序设计 丁峻岭 中国铁道出版社3.C程序设计 谭浩强 清华大学出版社8. 附件程序源代码：#include#include#include#include#include#include#include#include#include#include#include#include#includeusing namespace std;const int N=1000010;int data_num,data_arrayN,data_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=1;i-)printf(%d%s,data_arrayi,i!=1? :n);/排序后逆序数据输出 从小到大 1 data_numint outnew1()printf(排序后结果为:);for(int i=1;i=0;i-)printf(%d%s,data_arrayyi,i!=0? :n);/排序后逆序数据输出 从小到大 0 data_num-1int outnew3()printf(排序后结果为:);for(int i=0;idata_num;i+) printf(%d%s,data_arrayyi,i!=data_num-1? :n);/插入排序void charu()int i,j;int temp; printf(插入排序:n);for(i=1;i0 & tempdata_arrayj-1;j-)data_arrayj=data_arrayj-1;data_arrayj=temp;if(!t) outnew0();else outnew1();/冒泡排序void maopao()int temp;for(int i=1;i=data_num;i+)for(int j=i+1;jdata_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;in;i+)min=i;for(int j=i;jaj)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(lchildamax) max=lchild; if(rchildamax) 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); /交换堆顶和最终一个元素，即每次将剩下元素中最大者放到最终面 /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+data_num+1); if(!t) outnew0();else outnew1();/希尔排序void ShellInsert(int *a,int d,int n)for (int i=d;i= 0&ajtemp)/从后向前，找到比其小数位置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(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;ik;i+)afirst+i=tempi;void MergeSort(int a,int first,int last,int temp) if(firstlast) 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; /输出void print() printf(欢迎再次使用!nrn); printf(*n); printf(* . . . . . *n); printf(* . . . . . . *n); printf(* . . . . . . *n); printf(* . . . . . . *n); printf(* . . . . *n); printf(*