数据结构课程设计-排序算法集成.docVIP

xx大学 本科生课程设计论文 题 目：排序算法集成 学生姓名： 学 号： 专 业：计算机 班 级： 指导教师： 2013年 5月20日 xx大学课程设计任务书 课程名称 数据结构课程设计 设计题目 排序算法集成 指导教师 时间 2013.5.20-2013.5.30 一、教学要求 1. 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。1. 分析课程设计题目的要求2. 写出详细设计说明3. 编写程序代码，调试程序使其能正确运行4. 设计完成的软件要便于操作和使用. 设计完成后提交课程设计报告资料查阅与讨论1. 根据平时上机考勤、表现和进度，教师将每天点名和检查2. 根据课程设计完成情况，必须有可运行的软件。3. 根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。数据结构:用面向对象方法与C++语言描述?清华大学出版社 2007.6 目 录 目 录 3 引言 4 一．算法的设计思想 4 二．算法的流程图 4 三．算法的设计与分析 5 3.1 建立数组 5 3.2 算法思想 5 3.3 主要函数 6 3.4 主要函数声明 6 3.5 主要变量说明 10 四．程序源代码 11 五．运行结果与分析（测试） 18 六．总结（收获与体会） 20 七．参考文献 21 引 言 本课程设计主要解决几种不同排序方法以及在各种不同排序的过程中某一趟的具体排序结果。通过观察各种排序的具体排序过程，加深对不同排序方法的认识，加深对不同排序算法的掌握。 一．算法设计的思想 数据结构是与数据相关的一门重要学科，不论是想通过升学考试还是想把程序编得有水平，都要对这门学科下一点功夫才行。而课程设计是让我们更好的掌握这门学科的重要方式。 排序是计算机程序中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列重新排列成一个按关键字有序的序列 。而内部排序中包括各种不同的排序，本课程设计主要讨论的是插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。 完成这几种排序最主要的就是弄好不同排序的算法，只有深刻的认识了这不同排序的算法，才能了解不同排序的优点与缺点。通过对不同排序算法的分析，了解它们的优劣特点。 据对题目的分析，首先要根据插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序的不同算法，写出实现各个排序算法的函数。然后通过在主函数中对不同排序的子函数的调用来实现对某个序列的具体排序。内部排序的方法很多，但就其全面性而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合不同的环境。通常，在排序的过程中需进行两种基本操作：（1）比较两个关键字的大小；（2）将记录从一个位置移动至另一位置。前一个操作对大多数排序方法来说都是必要的，而后一个操作可以通过改变记录的存储方式来予以避免。 二．算法的流程图 如图2.1 图2.1 主要设计思想流程图 三．算法的设计与分析 3.1建立数组 在程序中建立一个数组data[ ]，用于存储程序运行中的数据。 3.2算法思想 （1）插入排序 插入排序的主要算法思想是将一个记录插入到已排好的有序表中，从而得到一个新的、记录数增1的有序表。 （2）希尔排序 希尔排序的基本思想是先将整个待排记录列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。 （3）冒泡排序函数 冒泡排序首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序则将两个记录交换，然后比较第二个记录和第三个记录的关键字，依次类推。 （4）选择排序函数 选择排序的基本思想是：每一趟在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。 （5）堆排序 先将一个序列进行建堆，然后将大顶堆的第一个元素和最后一个元素对换（或将小顶堆的最后一个元素和第一个元素对换），再对除最后一个元素的序列进行求大顶堆（或对除第一个元素的序列进行求小顶堆），依次类推。 3.3 主要函数 （1）插入排序函数 void insertion_sort(int[],int);/*插入排序*/ （2）希尔排序函数 void shell_sort(int[],int);/*希尔排序*/ （3）冒泡排序函数 void