1、 课 程 设 计 说 明 书 题目 内部排序算法的比较 系(部) 计算机科学与技术系 专 业 ( 班 级 ) 软件八班 姓名 学号 指导教师 起止日期 1 课程设计任务书 课程名称：课程名称：数据结构与算法数据结构与算法 设计题目：设计题目：内部排序算法的比较内部排序算法的比较已知技术参数和设计要求：已知技术参数和设计要求： 问题描述问题描述： 通过随机数据比较各内部排序算法的关键字比较次数和关键字移动的次数，以取得直观感受。 基本要求：基本要求： 1 待排序表的表长不小于 100；至少要用 5 组不同的输入数据作比较；排序算法不少于5 种。 2 待排序的元素的关键字为整数。 3 比较的指标为
2、有关键字参加的比较次数和关键字的移动次数(关键字交换以 3 次计)。 4 演示程序以人机对话的形式进行。 每次测试完毕显示各种比较指标的列表， 以便比较各种排 序的优劣。 5 最后要对结果作简单的分析。 测试数据：测试数据： 用伪随机数产生程序产生。 选作内容：选作内容： 对不同的表长做试验分析两个指标相对于表长变化关系。 设计工作量：设计工作量： 40 课时 工作计划：工作计划： 班级 时间 节次 教室 内容 指导教师 11软件8班 15 周周一 1-4 节 致远楼 1413 布置任务 曾俊勇 15 周周一 5-8 节 致远楼 1502 上机调试 15 周周二 1-4 节 I 涵虚楼 C32
3、01 答疑 15 周周二 5-8 节 致远楼 1503 上机调试 15 周周三 1-4 节 涵虚楼 C3202 答疑 16 周周一 1-4 节 致远楼 1413 上机调试 16 周周一 5-8 节 致远楼 1502 上机调试 16 周周二 1-4 节 涵虚楼 C3201 答疑 16 周周二 5-8 节 致远楼 1503 上机调试 16 周周三 1-4 节 致远楼 1408 答辩 指导教师签名： 日期: 教研室主任签名： 日期： 系主任签名： 日期： 2 目录 摘要 3 第一章 系统总体设计 4 2.1 原始数据 . 4 2.2 输出数据 . 4 2.3 系统架构设计 4 2.3.1 程序的主要
4、模块 4 2.3.2 进入排序过程 4 2.3.3 程序流程 . 5 第二章 算法与数据设计 6 3.1 选择排序 6 3.2 插入排序 6 3.3 冒泡排序 6 3.4 快速排序 6 3.5 希尔排序 7 第三章 总结 8 参考文献 . 9 附录代码 A .10 摘要 本次课程设计是在数据结构基础上设计的，它的目的是帮助同学更深入的了解数据结构这 门课程，使同学达到熟练掌握的程度。课程设计其中一个内容是内部排序算法的比较，它要求通过随机 数据比较各内部排序算法的关键字比较次数和关键字移动的次数， 以取得直观感受。 并且待排序表的表 长不小于 100；至少要用 5 组不同的输入数据作比较；排序
5、算法不少于 5 种；比较的指标为有关键字参 加的比较次数和关键字的移动次数演示程序以人机对话的形式进行。 每次测试完毕显示各种比较指标的 列表，以便比较各种排序的优劣。用到的序的种类有：直接选择排序，冒泡排序，折半插入排序、快速 排序、 归并排序。 通过这几种方法的比较： 快速排序、 归并排序的效率较高， 但适合用于数据多的情况； 插入排序的时间复杂度同于直接选择排序、冒泡排序，但它大大降低比较次数，所有它的效率高于直接 选择排序，冒泡排序。 关键字关键字：选择排序；冒泡排序；插入排序；快速排序；希尔排序 第一章 系统总体设计 2.1 2.1 原始数据原始数据 用户输入关键字的个数，数据由随机
6、序列生成器和特殊序列生成器生成 。 2.2 2.2 输出数据输出数据 产生的序列分别用选择排序、插入排序、冒泡排序、快速排序、希尔排序等这些排序方法 进行排序，输出关键字的排序时间 、比较次数、移动次数。 2.3 2.3 系统架构设计系统架构设计 2.3.1 2.3.1 程序的主要模块程序的主要模块 程序的主要模块主要模块排序算法演示模块 2.3.22.3.2 进入排序过程进入排序过程 a.选择排序，根据简单选择排序的算法，输出排序时间、比较次数、移动次数 b.插入排序，根据插入排序算法，输出排序时间、比较次数、移动次数 5 c.冒泡排序，根据冒泡排序的算法，输出排序时间、比较次数、移动次数 d.快速排序，根据快速排序的算法，输出排序时间、比较次数、移动次数 e.希尔排序，根据归并排序的算法，输出排序时间、比较次数、移动次数 2.3.32.3.3 程序流程程序流程 开始 随机获取 20000 个数据 选择排序 冒泡排序 插入排序 快速排序 希尔排序 这五种排序方法各自比较次数，移动次数，运行时间 步
