大数据结构课程设计综合排序.doc

课程设计报告课程设计报告课程设计题目：课程设计题目：综合排序的设计综合排序的设计 目录目录摘要 2一、题目的内容与要求-4二、需求分析-4三、概要设计-5四、四种排序源代码详细设计-5五、程序输出的结果-10六、运行结果与分析-12七、收获与体会-13八、参考文献-14摘 要数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。在许多类型的程序的设计中，数据结构的选择是一个根本的设计考虑因素。许多大型系统的构造经验明确，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择适宜的数据结构都是非常重要的。 排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，其中包含冒泡排序，直接插入排序，简单项选择择排序，希尔排序，快速排序，堆排序等，各有其特点。对排序算法比拟的分析可以遵循假如干种不同的准如此，通常以排序过程所需要的算法步数作为度量，有时也以排序过程中所作的键比拟次数作为度量。特别是当作一次键比拟需要较长时间，例如，当键是较长的字符串时，常以键比拟次数作为排序算法计算时间复杂性的度量。当排序时需要移动记录，且记录都很大时，还应该考虑记录的移动次数。终究采用哪种度量方法比拟适宜要根据具体情况而定。在下面的讨论中我们主要考虑用比拟的次数作为复杂性的度量。关键字：数据结构；算法比拟；比拟次数；时间复杂度数据结构；算法比拟；比拟次数；时间复杂度一、题目的内容与要求一、题目的内容与要求排序综合排序综合利用随机函数产生 N 个随机整数20000 以上 ，对这些数进展多种方法进展排序。要求：(1)至少采用三种方法实现上述问题求解提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序 。并把排序后的结果保存在不同的文件中。(2)统计每一种排序方法的性能以上机运行程序所花费的时间为准进展比照 ，找出其中两种较快的方法。(3)如果采用 4 种或 4 种以上的方法者，可适当加分。二、需求分析二、需求分析2.1 问题描述问题描述 此次的任务要求是输入 20000 个以上的随机整数，对这些数进展多种方法进展排序。提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序。 约束：程序可由用户自行设定排序数的个数，但排序数具体值需要由计算机生成，然后用三种以上的排序方法对随机数组进展排序，每一种排序方法执行后需统计出数据移动次数以判断排序方法的比照随机数组的执行优劣性。另：用户自行算出每一种排序方法的时间复杂度与空间复杂度。 2.2 根本要求根本要求2.2.1 输入的形式和输入值的 X 围；设定的随机数据的 X 围为 20000 以上，用户自定义随机数的个数n，随机数的数据类型均为整形。2.2.2 输出的形式；程序是以一个完整的有序数组来进展输出。2.2.3 程序所达到的功能：将一个无序数组进展排序随机生成 20000 以上个随机整数，对这些数进展多种方法进展排序。分别采用以下方法实现上述问题求解可采用的方法有简单排序、希尔排序、冒泡排序、快速排序这四种排序方法。三、概要设计三、概要设计3.13.1 可排序表的抽象数据类型定义：可排序表的抽象数据类型定义：typedefint KeyType; /关键字为整型typedef int OtherType; /关键字为整型typedef structKeyType key; /关键字为 KeyType 型OtherType other_data;RecordType; /定义一个 RecordType 型结构体，存放关键字void quicksort(RecordType a,int left,int right)/快速排序voidbubbleSort(RecordType a,int length)/冒泡排序void shellSort(RecordType a,int n)/希尔排序void BinSort (RecordType r, int length)/折半插入排序void main()/主函数运行入口四、四种排序源代码详细设计：四、四种排序源代码详细设计：4.1 快速排序模块：快速排序模块：void quicksort(RecordType a,int left,int right)RecordType t;int i,j,temp; if(leftright) return; temp=aleft.key; i=left; j=right; while(i!=j) while(aj.key=temp & ij) j-; while(ai.key=temp & ij) i+; if(ij) t=ai; ai=aj; aj=t; aleft = ai; ai.key = temp; quicksort(a,left,i-1);/继续处理左边的，这是一个递归的过程 quicksort(a,i+1,right);/继续处理右边的，这是一个递归的过程 /* 快速排序算法 */ 4.2 冒泡排序模块：冒泡排序模块：/此处是一次冒泡排序过程，在主函数中会通过循环调用此冒泡函数过程void bubbleSort(RecordType a,int length)int i,temp; for(i=1;iai+1.key) temp = ai.key; ai.key=ai+1.key; ai+1.key=temp; /* 冒泡排序算法 */ 4.3 希尔排序模块：希尔排序模块：void shellSort(RecordType a,int n)int i, j, temp; int gap = 0;while (gap 0) for ( i = gap; i = 0 ) & ( aj+1.key temp )aj + gap+1.key = aj+1.key;j = j - gap;aj+gap+1.key = temp;gap = ( gap - 1 ) / 3;4.4 希尔折半插入排序模块：希尔折半插入排序模块：/*折半插入排序法*/void BinSort (RecordType r, int length)/*对记录数组 r 进展折半插入排序，length 为数组的长度*/int i,j;RecordType x;int low,high,mid;for ( i=2; i=length ; +i ) x= ri;low=1; high=i-1;while (low=high ) /* 确定插入位置*/ mid=(low+high) / 2;if ( x.key= low; -j ) rj+1= rj; /* 记录依次向后移动 */ rlow=x; /* 插入记录 */ /*BinSort*/4.5 主函数模块：主函数模块：void main()int n,i,j,t; char b; bool q=false;RecordType a40000;while(1) printf(nn);printf( * 综 合 排 序*nn); printf( *菜 单*nn); printf( * = * n); printf( * 1. 读 取 待排序长度 * n); printf( * 2. 产生随机数并输出 * n); printf( * 3. 采用快速排序法排序 * n); printf( * 4. 采用冒泡排序法排序 * n); printf( * 5. 采用希尔排序法排序 * n); printf( * 6. 采用折半插入排序法排序 * n); printf( * 7. 输 出 * n);printf( * 0. 退 出 系 统 * n);printf( * - * n); printf( 请输入你要进展的操作); b = getch(); switch(b) case 1: printf(%cn,b);printf(请输入待排序记录的长度：);scanf(%d,&n);break; case 2:printf(%cn,b);srand( (unsigned)time( NULL );printf(下面随机生成%d 个数字存储在数组中n,n);for(i=1;i=n;i+)ai.key = rand()%20000;printf(%dt,ai.key);if(i%100=0)printf(n);printf(n);break;case 3:printf(%cn,b);printf(n-快速排序完毕-nn);quicksort(a,1,n);q=true;break;case 4:printf(%cn,b);for(i=0;in-1;i+)bubbleSort(a,n-i);printf(n-冒泡排序完毕-nn);q=true;break; case 5:printf(%cn,b);printf(n-希尔排序完毕-nn);shellSort(a,n);q=true;break; case 6:printf(%cn,b);BinSort(a,n);printf(n-折半插入排序完毕-nn);q=true;break; case 7:printf(%cn,b);if(q)printf(n-排序后输出-n);for(i=1;i=n;i+)printf(%dt,ai.key);if(i%100=0)printf(n); elseprintf(n * = * n); printf( * 您未对待排序数据排序 * n); printf( * 请重新选择排序的序号 * n); printf( * - * n);break; case 0:printf(%cn,b);printf(n 感谢使用综合排序程序n 按任意键退出.n);return;break; default:printf(输入错误请重新输入nn); 五、程序输出的结果：五、程序输出的结果：5.1 输入和输出：输入和输出：(1)主函数运行的输出结果：(2)选择 1，读取待排序长度这里以 20000 为例：(3)选择 2，产生随机数并输出：(4)选择 3，采用快速排序法排序：选择 4、5、6 的其他排序法的输出雷同，此处就不再重复(5)选择 7，输出排序结果：六、运行结果与分析六、运行结果与分析各算法的比拟方法各算法的比拟方法 折半插入排序、冒泡排序是稳定的 希尔排序、快速排序是不稳定的 折半插入排序、冒泡排序的时间复杂性为 O(n2) 其它非线形排序的时间复杂性为 O(nlog2n) 线形排序的辅助空间为 O(n),其它排序的辅助空间为 O(1);插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。反而在这种情况下，快速排序反而慢了。当 n 较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。当 n 较大时，关键字元素比拟随机，对稳定性没要求宜用快速排序。七、收获与体会七、收获与体会根据四种排序法的根底理论实际性模仿和编写算法程序，很是困难，算法是程序的灵魂，数据结构确是算法的根底，但是不断的实践也是一种进步的好途径。这次课程设计主要是对根底知识的灵活应用，这就让我进一步提高了对数结构知识的巩固。这次设计的完成，困难是少不了的，还有很多其它的难题让我都不知道所措，但是通过努力最终解决他们让我体会到成就感，更重要的是我的能力在实践中得到了提升和优化，特别是对常用的排序算法的应用，这对我以后从事软件应用程序开发是有很大的帮助的。这次课程设计的心得体会通过实习我的收获如下 1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。2、培养了我选用参考书，查阅手册与文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。4、通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点： 1、认真上好专业实验课，多在实践中锻炼自己。2、写程序的过程中要考虑周到，严密。3、在做设计的时候要有信心，有耐心，切勿浮躁。4、认真的学习课本知识，掌握课本中的知识点，并在此根底上学会灵活运用。5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。我通过课程设计建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规 X，培养独立学习、吸取他人经验，树立团队协作精神。同时，充分弥补了课堂教学与普通实验中知识深度与广度有限的缺陷，更好地帮助从全局角度把握课程体系，并且可以将理论与实际联系。在课程设计的过程中不仅仅是书本上的知识，这便促使我去查阅更多的课外资料来充实自己的内容，同时学会在面对困难时要耐心得分析它细心得解决它以与通过合作更完美得深入了解剖析它以便得到提高。细心、耐心、团结、求知，是我这次课程设计最大的收获。同时要感谢教师这几天的悉心教诲。八、参考文献八、参考文献1 啊哈磊， 啊哈！算法 ，人民邮电，2014-6-12 X 艳飞， C 语言 X 例开发大全清华大学，20103 严蔚敏，吴伟民。数据结构。：清华大学，2001