内部排序算法比较.doc

数据结构程序设计 I 内部排序算法比较 目录 摘摘 要要 1 1 绪论绪论 1 2 系统分析系统分析 1 2 1 功能需求 1 2 2 数据需求 1 2 3 性能需求 2 3 总体设计总体设计 2 3 1 系统设计方案 2 3 2 功能模块设计 2 4 详细设计详细设计 3 4 1 数据结构定义 3 4 2 伪随机产生数据模块 4 4 3 简单选择排序模块 6 4 4 起泡排序模块 7 4 5 直接插入排序模块 8 4 6 希尔排序模块 9 4 7 快速排序模块 10 4 8 归并排序模块 11 4 9 条形图模块 12 5 调试与测试调试与测试 13 5 1 调试 13 5 2 测试 13 6 结论结论 14 结束语结束语 14 参考文献参考文献 15 附录附录 1 用户手册 用户手册 16 附录附录 2 源程序 源程序 18 数据结构程序设计 1 摘摘 要要 本程序是比较几种排序算法的关键字比较次数和移动次数以取得直观感受 内部算法有冒泡排序 直接插入排序 快速排序 希尔排序 归并排序等 每种算法都有自己的比较方法和优缺点 本程序能更直观的显示出各种排序的 比较次数 移动次数和排序时间 并能用条形图 星号表示 进行表示 以便 比较各种排序的优劣 该程序运用了数据结构中线性表的顺序存储结构和各种 排序算法来共同实现的 关键词 内部排序 条形图 1 绪论绪论 随着科技的快速发展 越来越多的企业不再浪费人力财力去计算一些统计 性结果 而是应用一些简单的程序或系统来完成这些任务 随着学习数据结构 课程的深入 了解了不同排序算法的不同排序方法 每种排序对数据的比较次 数 移动次数和排序用时都是不同的 本程序实现了六种内部排序算法的比较 并用条形图直观的显示出各种算法的优劣 运用伪随机产生的数据 调用六种 排序算法 记录其比较次数 移动次数和排序时间 再分别用条形图 星号表 示 表示出来 2 系统分析系统分析 2 1 功能需求功能需求 1 对起泡排序 直接插入排序 简单选择排序 快速排序 希尔排序 归 并排序算法进行比较 2 待排序的元素的关键字为整数 其中数据要用伪随机产生程序产生 并 且至少用 5 组的输入数据做比较 再使用各种算法对其进行排序 记录其排序 时间 再汇总比较 3 演示程序以人机对话的形式进行 每次测试完毕显示各种比较指标值 比较次数 移动次数和排序时间的列表 并用条形图即星号表示出来 以便比 较各种排序的优劣 2 2 数据需求数据需求 抽象数据类型 线性表 排序算法 数据结构课程设计 2 1 输入数据 需要比较的数据数目 2 输出数据 不同算法的比较次数 移动次数 排序时间的数据以及对 应的条形图 2 3 性能需求性能需求 在运行本程序时 只要按照正确的操作方法不会出现无法运行的情况 系 统稳定性好 安全 可靠 响应速度由需比较的数字数目多少来决定 3 总体设计总体设计 3 1 系统设计方案系统设计方案 1 输入要排序的数据数目 2 抽象数据类型定义 typedef struct int key ElemType 关键字 typedef struct ElemType elem int length SqList 分配顺序存储结构 3 存储结构 本程序采用了线性表的顺序存储结构 4 算法设计 简单选择排序 运用顺序表 时间复杂度 O n2 空间复杂度 O 1 起泡排序 时间复杂度 O n2 空间复杂度 O 1 直接插入排序 时间复杂度 O n2 空间复杂度 O 1 希尔排序 时间复杂度 O n1 3 空间复杂度 O 1 快速排序 时间复杂度 O nlog2n 空间复杂度 O nlog2n 归并排序 时间复杂度 O nlog2n 空间复杂度 O n 3 2 功能模块设计功能模块设计 根据分析整个程序主要划分为 8 个功能模块 分别执行要求中的功能 1 个产生伪随机数据模块 6 个内部排序算法模块以及 1 个形成条形图模块 功 数据结构课程设计 3 能模块图如图 1 所示 内内部部排排序序算算法法比比较较系系统统 简简 单单 选选 择择 排排 序序 起起 泡泡 排排 序序 直直 接接 插插 入入 排排 序序 希希 尔尔 排排 序序 伪伪 随随 机机 产产 生生 数数 据据 快快 速速 排排 序序 归归 并并 排排 序序 条条 形形 图图 表表 示示 比比 较较 结结 果果 图图 1 1 功能模块图功能模块图 1 伪随机产生数据模块 本程序要求数据是要用伪随机产生程序产生 再用不同排序算法进行排序 2 简单选择排序模块 运用简单选择排序法对伪随机产生的数据进行 排序 3 起泡排序模块 运用起泡排序法对伪随机产生的数据进行排序 4 直接插入排序模块 运用直接插入排序法对伪随机产生的数据进行 排序 5 希尔排序模块 运用希尔排序法对伪随机产生的数据进行排序 6 快速排序 运用快速排序法对伪随机产生的数据进行排序 7 归并排序 运用归并排序法对伪随机产生的数据进行排序 8 条形图表示比较结果 统计 6 种排序算法的比较结果 用条形图表 示出来 4 详细设计详细设计 4 1 数据结构定义数据结构定义 typedef struct int key 数据结构课程设计 4 ElemType 关键字 typedef struct ElemType elem int length SqList 分配顺序存储结构 4 2 伪随机产生数据模块伪随机产生数据模块 伪随机产生数据模块可实现伪随机产生不同数目的数据以供排序 运用顺 序存储结构来实现的 该模块具体实现程序流程如图 2 所示 开始 结束 int i 输入要要比较 的数据个数 n 20000 printf 超出范围 重新输入 n L elem ElemType malloc LIST INIT SIZE sizeof ElemType L elem exit 0 L length 0 i 1 i20000 L length Y N Y N Y N Y N i 数据结构课程设计 5 图图 2 2 伪随机产生数据模块伪随机产生数据模块 4 3 简单选择排序模块简单选择排序模块 简单选择排序模块可实现用简单排序法对产生的数据进行排序 该模块具 体实现程序流程如图 3 所示 开始 start t clock int i j k com 0 mov 0 i 1 k i i L length j i 1 j L length com L elem j key L elem k key k j j Y N N Y Y N i k L elem 0 key L elem i key L elem i key L elem k key L elem k key L elem 0 key mov 3 end t clock 输出com mov t0 double end t start t CLK TCK 输出排序用时t0 A 0 com B 0 mov C 0 t0 结束 Y N 数据结构课程设计 6 图图 3 3 简单选择模块简单选择模块 4 4 起泡排序模块起泡排序模块 起泡排序模块可实现运用起泡排序法对数据进行排序 该模块具体实现程 序流程如图 4 所示 开始 start t clock int i 0 j com 0 mov 0 i L length j 1 jL elem j 1 key Y N i end t clock t1 double end t start t CLK TCK 输出com mov t1 A 1 com B 1 mov C 1 t1 结束 数据结构课程设计 7 图图 4 4 起泡排序模块起泡排序模块 4 5 直接插入排序模块直接插入排序模块 直接插入排序模块可实现运用直接插入排序法对数据进行排序 该模块具 体实现程序流程如图 5 所示 开始 结束 start t clock int i j com 0 mov 0 L elem 0 key L elem i key mov i 2 i L length L elem i key L elem i 1 key j i 1 com L elem 0 key L elem j key L elem j 1 key L elem j key j mov com L elem j 1 key L elem 0 key mov end t clock t2 double end t start t CLK TCK 输出com mov t2 A 2 com B 2 mov C 2 t2 Y N N Y N Y i 图图 5 5 直接插入排序模块直接插入排序模块 数据结构课程设计 8 4 6 希尔排序模块希尔排序模块 希尔排序模块可实现运用希尔排序法对数据进行排序 该模块具体实现程 序流程如图 6 所示 开始 结束 start t clock int i d L length 2 j w 0 k com 0 mov 0 w 1 i w w d i i d i L length k i j j d j i d jL elem j key k j com i k L elem 0 key L elem i key L elem i key L elem k key L elem k key L elem 0 key mov 3 w d d 2 w 1 end t clock t3 double end t start t CLK TCK A 3 com B 3 mov C 3 t3 输出 com mov t3 N Y Y N N Y N Y N Y 图图 6 6 希尔排序模块希尔排序模块 数据结构课程设计 9 4 7 快速排序模块快速排序模块 快速排序模块可实现用快速排序法对数据进行排序 该模块具体实现程序 流程如图 7 所示 开始 结束 start t clock int pivotkey yd1 0 bj1 0 L elem 0 L elem low yd1 pivotkey L elem low key low high yd1 low pivotkey high L elem low L elem high bj1 yd1 low high L elem high L elem low bj1 yd1 L elem low L elem 0 yd1 return low end t clock t4 double end t start t CLK TCK 输出yd1 bj1 t4 A 4 bj1 B 4 yd1 C 4 t4 Y N Y N N Y 图图 7 7 快速排序模块快速排序模块 数据结构课程设计 10 4 8 归并排序模块归并排序模块 归并排序模块可实现用归并排序法对数据进行排序 该模块具体实现程序 流程如图 8 所示 开始 结束 start t clock int i low j m 1 k low yd1 0 bj1 0 i m R1 k R i yd1 i k bj1 R1 k R j yd1 j k i m R1 k R i yd1 i k R1 k R j yd1 j k j high N Y N Y Y N Y N end t clock t5 double end t start t CLK TCK 输出bj1 yd1 t5 图图 8 8 归并排序模块归并排序模块 数据结构课程设计 11 4 9 条形图模块条形图模块 条形图模块可用星号显示出各种算法排序的比较结果 该模块具体实现程 序流程如图 9 所示 开始 结束 long int d 6 int i n i 0 d i sqrt A i A 5 i 5 n 0 i 0 printf n 归并 排序 printf 选择 排序 n 0 i 1 n d i printf printf 冒泡 排序 n d i printf 其他排序同理 Y N N Y N Y n n 图图 9 9 条形图模块条形图模块 数据结构课程设计 12 5 调试调试与测试与测试 5 1 调试调试 调试过程主要是运行编制好的程序 然后遇到错误后根据系统的提示 找 到相关的问题所在 本系统调试过程中遇到的主要问题 原因和解决方法如下 面介绍 1 问题 用条形图表示时 不能根据数据而表示出星号的多少 解决办法 选择要表示的数据最小的一种排序作为基数 每种排序所要比 较的数据可运用数学运算计算出是基数的多少倍 从而输出几个星号 2 问题 输入数据数目为 2 个时程序运行错误 原因 待比较的数据为 2 个时 作为基数的那种排序的数据为 0 不能做 分母 所以会出现运行错误 解决方法 输入较大的数 使要用条形图表示出来的数据不为 0 即可 5 2 测试测试 软件测试是软件生存期中的一个重要阶段 是软件质量保证的关键步骤从 用户的角度来看 普遍希望通过软件测试暴露软件中隐藏的错误和缺陷 所以 软件测试应该是 为了发现错误而执行程序的过程 或者说 软件测试应该根 据软件开发各阶段的规格说明和程序的内部结构而精心设计一批测试用例 即 输入数据及其预期的输出结果 并利用这些测试用例去运行程序 以发现程序 错误或缺陷 过度测试则会浪费许多宝贵的资源 到测试后期 即使找到了错 误 然而付出了过高的代价 测试数据过程如下 1 输入功能测试 输入数据 1 100 预期结果 输出各排序算法的比较次数 移动次数和排序用时 随后 输出数据比较所对应的条形图 运行结果 输出各排序算法的比较次数 移动次数和排序用时 随后 输出数据比较所对应的条形图 说明 预期和运行结果相同 输入数据 2 25000 数据结构课程设计 13 预期结果 输出各排序算法的比较次数 移动次数和排序用时 随后 输出数据比较所对应的条形图 运行结果 超出范围重新输入 说明 不能输入比 25000 大的数 2 输出功能测试 输入数据 1 200 预期结果 输出各排序算法的比较次数 移动次数和排序用时 随后 输出数据比较所对应的条形图 运行结果 输出各排序算法的比较次数 移动次数和排序用时 随后 输出数据比较所对应的条形图 说明 预期和运行结果相同 输入数据 2 4 预期结果 输出各排序算法的比较次数 移动次数和排序用时 随后 输出数据比较所对应的条形图 运行结果 在输出移动次数比较的条形图时出现运行错误 说明 不能输入比 5 小的数 6 结论结论 经过这一段时间的程序设计 该课设任务书中题目所要求的功能也都一一 实现 可以伪随机产生不同的数据 六种内部排序算法对其数据进行排序 记 录比较次数 移动次数和排序用时 并用条形图直观的表示出不同算法的优劣 不过本程序还可以添加细节 例如 可输出个选择排序方法的菜单 挑选不同 排序方法对数据进行比较 也可以再循环选择并用条形图表示出来 结束语结束语 为期两个星期的课程设计终于顺利完成 这段时间让我对数据结构这门课 程有更多的了解和认识 同时也从编程中所遇到的挫折和困难中吸取更多有价 值的经验 编程需要耐心和信心 要有缜密的心思来全面考虑问题 否则编出 的程序不能完全满足题目要求或运行错误 通过这次课设 我更深入了解了六 种内部排序算法的排序方法和时间复杂度 从而还算顺利的完成了本次课程设 数据结构课程设计 14 计 编程的道路不好走 不过我会更加努力的学习 让编程不再那么困难辛苦 让以后自己能有信心的轻松面对 参考文献参考文献 1 谭浩强 C 语言程序设计 第三版 清华大学出版社 2007 2 姜灵芝 余健 C 语言课程设计案例精编 清华大学出版社 2008 3 吴伟民 严蔚敏 数据结构 清华大学出版社 2008 4 吕映芝 编译原理 清华大学出版社 2008 数据结构程序设计 15 附录附录 1 用户手册 用户手册 点击运行 首先出现的是要输入伪随机产生数据的数目 如图 9 所示 图图 9 9 输入界面输入界面 输入数据个数然后回车 可显示出不同排序算法的比较次数 移动次数和 排序用时 如图 10 所示 图图 1010 显示比较结果界面显示比较结果界面 显示比较次数的条形图 如图 11 所示 数据结构课程设计 16 图图 1111 比较次数条形图界面比较次数条形图界面 显示移动次数条形图 如图 12 所示 图图 1212 移动次数条形图界面移动次数条形图界面 显示排序用时条形图 如图 13 所示 图图 1313 排序用时条形图界面排序用时条形图界面 数据结构课程设计 17 附录附录 2 源程序 源程序 主要模块源代码清单 include include include include include define LIST INIT SIZE 30000 int bj1 yd1 n com mov long int A 5 B 5 double t0 t1 t2 t3 t4 t5 C 5 clock t start t end t typedef struct int key ElemType typedef struct ElemType elem int length SqList void addlist SqList a printf 请输入你要输入的个数 scanf d if n 20000 printf 超出范围重新输入 n goto a L elem ElemType malloc LIST INIT SIZE sizeof ElemType if L elem exit 0 数据结构课程设计 18 L length 0 for i 1 i20000 goto b L length void SelectSort SqList int i j k com 0 mov 0 for i 1 i L length i k i for j i 1 j L length j com if L elem j key L elem k key k j if i k L elem 0 key L elem i key L elem i key L elem k key L elem k key L elem 0 key mov 3 end t clock printf 比较次数为 d 移动次数为 d n com mov t0 double end t start t CLK TCK printf 排序用时为 f n t0 A 0 com 数据结构课程设计 19 B 0 mov C 0 t0 void bubblesort SqList int i 1 j com 0 mov 0 while i L length for j 1 jL elem j 1 key L elem 0 key L elem j key L elem j key L elem j 1 key L elem j 1 key L elem 0 key mov 3 i end t clock printf 比较次数为 d 移动次数为 d n com mov t1 double end t start t CLK TCK printf 排序用时为 f n t1 A 1 com B 1 mov C 1 t1 void InsertSort SqList 数据结构课程设计 20 int i j com 0 mov 0 for i 2 i L length i if L elem i key L elem i 1 key L elem 0 key L elem i key mov j i 1 com while L elem 0 key L elem j key L elem j 1 key L elem j key j mov com L elem j 1 key L elem 0 key mov end t clock printf 比较次数为 d 移动次数为 d n com mov t2 double end t start t CLK TCK printf 排序用时为 f n t2 A 2 com B 2 mov C 2 t2 void xier SqList int i d L length 2 j w 0 k com 0 mov 0 while w d 数据结构课程设计 21 w 1 for i w i L length i i d k i for j i d jL elem j key k j com if i k L elem 0 key L elem i key L elem i key L elem k key L elem k key L elem 0 key mov 3 w d d 2 w 1 end t clock printf 比较次数为 d 移动次数为 d n com mov t3 double end t start t CLK TCK printf 排序用时为 f n t3 A 3 com B 3 mov C 3 t3 数据结构课程设计 22 void BeforeSort yd1 0 bj1 0 void display int m int n printf 比较次数为 d 移动次数为 d n m n int Partition SqList L int low int high 快速排序 int pivotkey L elem 0 L elem low yd1 pivotkey L elem low key while low high yd1 while low pivotkey high L elem low L elem high bj1 yd1 while low high L elem high L elem low bj1 yd1 L elem low L elem 0 数据结构课程设计 23 yd1 return low void QSort SqList if low high pivotloc Partition L low high QSort L low pivotloc 1 QSort L pivotloc 1 high void QuickSort SqList BeforeSort QSort L 1 L length display bj1 yd1 end t clock t4 double end t start t CLK TCK printf 排序用时为 f n t4 A 4 bj1 B 4 yd1 C 4 t4 void Merge ElemType R ElemType R1 int low int m int high 归并排 序 int i low j m 1 k low while i m R1 k R i yd1 i k else bj1 R1 k R j yd1 j k while i m R1 k R i yd1 i k while j high R1 k R j yd1 j k void MergePass ElemType R ElemType R1 int length int n int i 0 j 数据结构课程设计 25 while i 2 length 1 n Merge R R1 i i length 1 i 2 length 1 i i 2 length if i length 1 n 1 Merge R R1 i i length 1 n 1 else for j i j n j R1 j R j void MSort ElemType R ElemType R1 int n int length 1 while length n MergePass R R1 length n length 2 length MergePass R1 R length n length 2 length void MergeSort SqList BeforeSort MSort L elem L elem L length display bj1 yd1 end t clock t5 double end t start t CLK TCK printf 排序用时为 f n t5 A 5 bj1 B 5 yd1 数据结构课程设计 26 C 5 t5 void printf SqList int i n printf n 比较次数 n printf n n for i 0 i 5 i d i sqrt A i A 5 printf n 归并排序 printf n n printf 选择排序 for n 0 i 0 n d i n printf printf n n printf 冒泡排序 for n 0 i 1 n d i n printf printf n n printf 直插排序 for n 0 i 2 n d i n p