数据结构课程设计报告---各种内排序性能比较.doc

数据结构课程设计报告 题目： 各种内排序性能比较 学生姓名： 学 号： 班 级： 指导教师： 2011-6-13 目 录 需求分析说明............................2 1.1 所需完成的任务及要求 1.2 程序实现的功能 总体设计................................3 2.1 总体设计说明 2.2 总体流程图 2.3 各主程序详细流程图 详细设计................................7 3.1 使用的算法思想 3.2 各个算法的效率简析 实现部分................................8 4.1程序算法的代码 程序测试...............................15 5.1 程序运行的主界面 5.2 各算法运行界面 总结...................................18 需求分析说明 排序是数据处理中经常遇到的一种重要操作。然而排序的算法有很多，各有其优缺点和使用场合。本程序的设计的主要目的是通过比较各种内部排序（包括：插入法排序、起泡法、选择法、快速法、合并法排序）的时间复杂度，即元素比较次数和移动次数，来分析各种算法优缺点和适合排列何种序列。达到在实际应用中选择合适的方法消耗最短的时间完成排序。 所需完成的任务及要求 任务： 用程序实现插入法排序、起泡法、选择法、快速法、合并法排序； 输入的数据形式为任何一个正整数，大小不限。 要求：排序后的数组是从小到大的； 程序实现的功能 使用随机函数实现数组初始化，生成多组元素个数不同的数组； 用列表打印出每种排序下的各趟排序结果； 打印使用各种排序算法以后元素比较和交换的次数； 设计合理的打印列表来打印。 总体设计（从总体上说明该题目的框架，用文字和图表说明） 2.1 总体设计说明 采用插入气泡，选择，快速，合并的方法实现各种排序算法，并且在实现过程中插入适当变量来实现计数元素交换次数和比较次数的统计。对于每一趟比较之后元素顺序以及最后的结果使用单独的函数来实现，形成单独的一个模块； 2.2 总体流程图 2.3 各主程序详细流程图 ①主函数流程图： ②插入法函数流程图 ③起泡法函数流程图 ④选择法函数流程图： 详细设计 3.1 使用的算法思想 对主界面的menu菜单，在主函数里面用switch语句调用各个模块的功能调用； 在插入法时，其算法思想是：将第一个元素作为单独的一个数组独立出来，对剩下的元素，逐个与前面的数组从后往前进行比较，一旦发现当前的元素大于或是等于前面已经排序好的元素中某个元素，则在这个元素之后插入即可； 在起泡法时 ，其算法思想是：将待排序的数组从后往前，依次比较相邻的两个元素，如果发现逆序则交换序列，使得数值、比较小的元素逐渐往前排列，在这个算法时要用flag作为标记位，用来判断元素是否交换，用以减少不必要的交换次数； 对于选择法，其排序思想是:从第一个元素开始，并且标记当前元素的位置，比较后面所有的元素，找到其中最小的元素，也标记当前元素的位置，然后把两个标记位的元素进行交换，前面的标记位不断地向后移动，直到最后一个元