排序综合数据结构课程设计论文

1、排序综合成都吃喝网 00 0 0 0二10 年 6 月1题 目 ） N 44第 3天 年月日年月日年月日遵守各项纪律，工作刻苦努力，具有良好的科学工作态度。6作表通过实验、试验、查阅文献、深入生产实践等渠道获取与课程设计有关的材料。能运用所学知识和技能去发现与解决实际问题，能正确处理实验数据，能对课题进行理论分析，得出有价值的结论。能独立查阅相关文献和从事其他调研；能提出并较好地论述课题的实施方案；有收集、加工各种信息及获取新知识的能力。能力操作等实验工作，数据正确、可靠；研究思路清晰、完整。水平55具有较强的数据运算与处理能力；能运用计算机进行资料搜集、加工、处理和辅助设计等。 符合本专业相

2、关规范或规定要求；规范化符合本文件第五条要求。成果质量综述简练完整，有见解；立论正确，论述充分，结论严谨合理；实验正确，分析处理科学。 对前人工作有改进或突破，或有独特见解。指导教师评语年 月 日- 2 -2摘 要数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选

3、择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。排序算型泡排序，直接插入排序，简单选择排序，希尔排序，快速排序，堆排序等，各有情况而定。在下面的讨论中我们主要考虑用比较的次数作为复杂性的度量。关键字 数据结构；算法比较；比较次数；时间复杂度- 3 -3目录摘要. 11概要. 4 4 52排序算法 . 7 8 8 9 9 9 9 9 3流程图及详细算法. 10 4运行结果 . 18 5结束语 . 25参考文献. 24- 4 -41 1.1 设计目的数据结构与算法课程主

4、要是研究非数值计算的程序设计问题中所出现的机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、进学生的综合应用能力和专业素质的提高。1）本演示程序对以下 6 种常用的内部排序算法进行实测比较：冒泡排序，直接插入排序，简单选择排序，快速排序，希尔排序，堆排序；2）待排序表的元素的关键字为整数。比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换记为 3 次移动）；3）演示程序以以用户和计算机的对话方式执行，在计算机终端上显示提示信息，对随机数组进行排序，并输出比较指标值；4）最后对结果作出简单分析

5、。1.2 预期目标到对各算法进行比较的目的。通过此次课程设计主要达到以下目的了解并掌握数过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。- 5 -52 2.1 各排序算法的特点1）冒泡排序 1 2 2 第 3 2 3 1 2 2）直接插入排序 , ; 3）简单选择排序（1）在一组元素ViVn-12）若它不是这3素中剔除这个具有最小排序码的元素，在剩下的元素 Vi+1Vn-1中重复执行第（12）步，直到剩余元素只有一个为止。4）快速排序放在一组，其余的放在另一组，然后分别对两组数据排序；5） 希尔排序先取

6、一个正整数 d1n，把所有序号相隔d1 的数组元素放一组，组内进行直接插入排序；然后取d2d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止；6) 堆排序- 6 -6堆排序是一树形选择排序，在排序过程中，将 R1.N看成是一颗完全二叉择最小的元素；堆的定义: N 个元素的序列 K1K2K3.，Kn.称为堆，当且仅当该序列满足特性：KiK2i Ki K2i+1(1 IN/2)2.2各算法的比较方法1.稳定性比较插入排序、冒泡排序、简单选择排序及其他线形排序是稳定的希尔排序、快速排序、堆排序是不稳定的2.时间复杂性比较插入排序、冒泡排序、选择排序的时间复杂性为 O(n2)其

7、它非线形排序的时间复杂性为 O(nlog2n)线形排序的时间复杂性为 O(n);3.辅助空间的比较线形排序的辅助空间为 O(n),其它排序的辅助空间为 O(1);4.其它比较序能达到较快的速度。反而在这种情况下，快速排序反而慢了。当 n 入或冒泡排序。若待排序的记录的关键字在一个明显有限范围内时 ,且空间允许是用桶排序。当 n 较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。当 n 允许的情况下，宜用归并排序。当 n 堆排序- 7 -73 3.1流程图函数的调用关系图反映了演示程序的层次结构：strandBubbleSortInsertSortSelectSortQuickSortSh

8、ellSortHeapSorInitLinkListRandomNuLTDisplay图 3.21）Main 为主函数模块2bubblesortinsertsortselectsortquicksortshellsortheansort分别对应冒泡排序，直接插入排序，简单选择排序，快速排序，希尔排序，堆排序的各函数模块3）在初始化数据之后，选择对应的排序模块进行排序，并对排序做出比较3.3 可排序表的抽象数据类型定义：typedef structint key;/定义一个RedType型结构体，存放关键字/关键字为整型 RedType;class LinkList/定义一个顺序表- 8 -8p

9、ublic:RedType rMAXSIZE+1;为RedType/长度为MAXSIZE+1的数组r，数组里每个元素均int Length;/数组长度int CmpNum, ChgNum;LinkList();/关键字的比较次数，移动次数/构造函数bool LT(int i, int j);void Display();void Insert( int dk);void ShellSort();/比较i和j的大小/输出数组元素/插入排序/希尔排序int Partition( int low, int high); /比基准小的数放左边，比起大的数放右边，返回基准位置void QSort( in

10、t low, int high); /从low到high位置进行快速排序void QuickSort();/对有序表进行快速排序void HeapAdjust( int s, int m); /将无序堆调整为大顶堆void HeapSort();/堆排序，将大顶堆转换为小顶堆/冒泡排序void BubbleSort();int SelectMinKey( int k);void SelSort();/找到数组中最小值，返回最小值位置/对顺序表进行选择排序void SelectSort();void AllAbove();/界面设计/统计以上所有排序关键字的比较次数、移动次数及所消耗的时间;3.

11、4 程序代码3.4.1 函数声明- 9 -910 = i =- 10 -10 4.3.2 六种排序算法代码/插入排序 = i - =i- j0 j + + - 11 -11/希尔排序 /快速排序 = = - + - 12 -12 -/堆排序 j= - =2* j j - - i-/冒泡排序 = i = j- +- 13 -13 + + /选择排序 = k = = i j= 4.3.3 排序算法的选择 - 14 -14 = - = - = - = - 15 -15 = - = -4.3.4主函数程序代码 = = = - - 16 -16 = - = - = - =- 17 -17= - = -

12、4 4.1 调试分析1对正序、逆序和若干不同程度随机打乱的可排序表，进行各种排序方法定程序的随机乱序算法，对伪随机数序列的产生有了具体的认识和实践。2将排序算法中的关键字比较和交换分别由 Less 和 Swap 两个内部操作实- 18 -18图 1图 2图 3图 4图 5图 6图 74.3 排序算法的评价对各种表长和测试组数进行了测试，程序运行正常。分析实测得到的数值，6插入排序 希尔排序 快速排序 堆排序 冒泡排序 选择排序第三多第二多 乱否差异 乱否差异 乱否差异 与乱否无很小稍多移动次数 排序的两 乱否差异 乱否差异 正和逆序越多 较小 很小 越多(1)若n较小(如n50)，可采用直接插

13、入或直接选择排序。倍少于直接插人，应选直接选择排序为宜。(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。在一个学期后的基础理论知识的学习后进入实践的操作虽然仍就有些困难会通过实习我的收获如下1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。3、通过实际编译系统- 23 -23的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。4、通过课全局观念。

14、根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点： 1、认真上好专业实验课，多在实践中锻炼自己。2、写程序的过程中要考虑周到，严密。3、在做设计的时候要有信心，有耐心，切勿浮躁。4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。5、在课余时程序的能力，学习文档编写规范，培养独立学习、吸取他人经验，树立团队协作得深入了解剖析它以便得到提高。细心、耐心、团结、求知，是我这次课程设计最大的收获。同时要感谢老师这几天的悉心教导。1 宁正元，王秀丽.算法与数据的结构，2006：29322 杨辉.杨辉的纵横图论，2003：12143 唐王希.太乙金镜式经，2000：35374 王力柱。与数据结构。栈，2003（81