排序算法性能分析.doc

1 实践教学实践教学 兰州理工大学兰州理工大学 计算机与通信学院 2011 年春季学期 数据结构数据结构课程设计课程设计 题 目 专业班级 姓 名 学 号 指导教师 成 绩 2 目目 录录 摘要 3 前言 4 正文 5 1 1 采用类采用类C C语言定义相关的数据类型语言定义相关的数据类型 5 5 2 2 各模块的伪码算法各模块的伪码算法 5 5 3 3 函数的调用关系图函数的调用关系图 6 6 4 4 调试分析调试分析 7 7 a a 调试中遇到的问题及对问题的解决方法调试中遇到的问题及对问题的解决方法 7 7 b b 算法的时间复杂度和空间复杂度算法的时间复杂度和空间复杂度 7 7 5 5 源程序源程序 8 8 总结 13 参考文献 14 致 谢 15 3 摘要摘要 排序是计算机程序设计中的一种重要操作 各种部排序算法的时间复杂度 分析结果只给出了算法执行时间的阶 或大概执行时间 关键字 排序 性能分析 4 前言前言 排序是计算机程序设计中的一种重要操作 它的功能是将一个数据元素的任 意序列 重新排列成一个按关键字有序的序列 内部排序的方法很多 但是就 其全面性能而言 很难 提出一种被认为是最好的方法 每一种方法都有各自的 优缺点 适合在不同的环境下使用 如果按排序过程中依据的不同原则对内部 排序方法进行分类 则大致可分为插入排序 交换排序 选择排序 归并排序 和记数排序等五类 这几种排序算法是在顺序存储结构上实现的 因此在排序过程中需要进行 大量记录的移动 当记录很大时 时间耗费很大 此时可采用静态链表作存储 结构 但是有的排序方法 无法实现表排序 在这种情况下可以进行地址排序 即另设一个地址向量指示相应记录 5 正文 1 1 采用类采用类 c c 语言定义相关的数据类型语言定义相关的数据类型 int 整型 char 字符型 2 2 各模块的伪码算法各模块的伪码算法 1 插入排序伪码算法 void InsertSort Splisti L length i if LT L r i key L r i 1 key 须将 r i 插 入有序子表 L r 0 L r i 复制为哨兵 L r i L r i 1 For j i 2 LT L r 0 key L r j key j L r j 1 L r j 记录后移 L r j 1 L r 0 插入到正确位置 InsertSort 2 希尔排序 void shllInsert Splist i0j dk L r j dk L r j 记录后移 L r j dk L r 0 插入 shellsort void shllsort Splist k t k shllInsert L data k shellsort 3 快速排序 int part sqlist 6 while loe high While low pivotkey high L r low L r high while low pivotkey low L r low L r high return low partition 4 选择排序 void selectsort splisti L length i j selectMinKey L i if i j L r i L r j selectsort 5 其泡排序 void bubblesort sqlist r int n int I j w for i 1 i i 1 j if r j key r j 1 key 比较 W r j R j r j 1 R j 1 w 3 3 函数的调用关系图函数的调用关系图 Main Insertion sort quick sort bubble sort selection sort shell sort Output quick 7 4 4 调试分析调试分析 a 调试中遇到的问题及对问题的解决方法 刚开始进行输入时 对有些排序不能实现 我就对不能实现的排序 进行分析 对产生的语法错误进行了及时的改正 以至所有的排序算法能 够顺利的实现 b 算法的时间复杂度和空间复杂度 算法的时间复杂度分别是O n2 O nlog2n O log2n 测试结果 23 45 6 13 81 8 32 12 45 3 9 46 37 100 20 0 5 5 源程序源程序 include include define N 100 定义数组最大为 100 const int t 3 定义希尔排序次数 int d 3 4 3 1 定义希尔排序比较量 int qmt 快速排序的移动次数 int qct 快速排序的比较次数 void output int n int a int ct int mt 内部排序中调用的输出函数 int i printf n 排序结果 for i 0 i n i printf d a i 输出各排序完成的数组 printf n 比较次数 d n ct 输出各排序比较次数 9 printf 移动次数 d n n mt 输出各排序移动次数 void bubble sort int n int A 冒泡排序 int mt 0 移动次数 mt movetime int ct 0 比较次数 ct cmdtime int i j temp int a N for i 0 i n i a i A i 使数组 a 与数组 A 完全相同 对数组 a 进行 操作 不改动 A 可以使 A 被其他函数调用 for i 0 i n 1 i for j 0 j n 1 i j ct if a j 1 a j 前后比较 temp a j a j a j 1 a j 1 temp mt 3 关键字交换计为 3 次移动 printf 冒泡排序 output n a ct mt void selection sort int n int A 选择排序 int mt 0 移动次数 movetime int ct 0 比较次数 cmdtime int i j temp k int a N for i 0 i n i a i A i 使数组 a 与数组 A 完全相同 对数组 a 进行 操作 不改动 A 可以使 A 被其他函数调用 for i 0 i n 1 i k i for j i 1 ja j k j temp a i a i a k 10 a k temp mt 3 关键字交换计为 3 次移动 printf 选择排序 output n a ct mt void quick int a int low int up 快速排序递归算法 int i j temp if low up i low j up temp a low qmt while i j qct while itemp j qct if i j a i a j qct qmt while i j if i j a j a i qct qmt a i temp qmt quick a low j 1 quick a i 1 up void quick sort int n int A 快速排序 通过调用快速排序递归算法完成 int i 11 int a N for i 0 i n i a i A i 使数组 a 与数组 A 完全相同 对数组 a 进行 操作 不改动 A 可以使 A 被其他函数调用 quick a 0 n 1 调用快速排序递归算法 printf 快速排序 output n a qct qmt void insertion sort int n int A 插入排序 int mt 0 移动次数 movetime int ct 0 比较次数 cmdtime int i j temp int a N for i 0 i n i a i A i 使数组 a 与数组 A 完全相同 对数组 a 进行 操作 不改动 A 可以使 A 被其他函数调用 for i 1 i 0j ct a j 1 a j mt a j 1 temp mt printf 插入排序 output n a ct mt void shell sort int n int A 希尔排序 int mt 0 移动次数 movetime int ct 0 比较次数 cmdtime int i j k h y int a N for i 0 i n i a i A i 使数组 a 与数组 A 完全相同 对数组 a 进行 操作 不改动 A 可以使 A 被其他函数调用 for i 0 i t i h d i 12 for j h j 0k h a k h a k a k h y printf 希尔排序 output n a ct mt void main int n int i int A N printf 请输入数组大小 小于 100 scanf d 输入所需排序数组大小 for i 0 i n i printf 请输入数组 a d i scanf d 依次输入数组 A 0 A n bubble sort n A 冒泡排序 insertion sort n A 插入排序 selection sort n A 选择排序 quick sort n A 快速排序 shell sort n A 希尔排序 13 总结总结 在这三周的数据结构课程设计中 我的题目是 排序算法性能分析 这三周 课程设计中 通过该题目的设计过程 我加深了对排序算法的理解 对排序算法上 基本运算的实现有所掌握 对课本中所学的各种数据结构进一步理解和掌握 学 会了如何把学到的知识用于解决实际问题 锻炼了自己动手的能力 一个人要完成所有的工作是非常困难和耗时的 在以后的学习中我会更加 注意各个方面的能力的协调发展 在课程设计时遇到了很多的问题 在老师的 帮助 和对各种资料的查阅中 将问题解决 培养了我自主动手 独立研究的 能力 为今后在学习工作中能更好的发展打下了坚实的基础 三周的课程设计很短暂 但其间的内容是很充实的 在其中我学习到了很 多平时书本中无法学到的东西 积累了经验 锻炼了自己分析问题 解决问题 的能力 并学会了如何将所学的各课知识融会 组织 来配合学习 三周中我 收益很大 学到很多 14 参考文献参考文献 1 严蔚敏 吴伟民 数据结构 C 语言版 清华大学出版社 2 严蔚敏 吴伟民 数据结构题集 C 语言版 清华大学出版社 3 DATA STRUCTURE WITH C William Ford William Tcpp