数据结构课程设计内部排序算法性能分析.doc

课程名称 课程名称 数据结构 本科学生课程设计 论文 本科学生课程设计 论文 题 目 内部排序算法性能分析 姓 名 学 号 104328318117680 学 部 计算机科学与技术 专业 年级 计科 1003 指 导 教 师 2011 年 12 月 24 日 摘 要 排序是计算机科学中基本的研究课题之一 其目的是方便记录的 查找 插入和删除 通过描述冒泡 选择 插入 堆和快速 6 种排序 算法 内部排序其算法灵活方便 因此成为了程序算法中一个必不 可少的应用 所以在应用之前要经过严谨的思考才不会出错 不会 造成计算机运算速度的延迟 才会完全发挥内部排序的性能 内部排序的方法种类繁多 但就其全面性能而言 很难提出一 种被认为是最好的方法 但就其全面性能而言 很难提出一种被认 为是最好的方法 每一种方法都有各自的优缺点 适合不同的环境 如记录的初始排序列状态等 下使用 如果安排序过程中依据的 不同原则对内部排序方法进行分类 则大致可分为插入排序 交换 排序 选择排序 归并排序和计数排序等五类 如果按内部排序过 程中所需要的工作量来区分 则可分为 3 类 1 简单的排序方法 该时间复杂度为 O n n 2 先进的排序方法 该时间复杂度为 O nlogn 3 基数排序 其时间复杂度为 O d n 主要介绍 非常实用而算法又容易接受的的这六类排序 由于很多人在使用的过程中 不知道那种排序适合他们的程度 设计 因此导致该算法没有得到充分的应用 起泡排序最简单的排 序 很容易写出代码 但运算时间复杂度稍长一些 直接排序能够 很快的最大和最小的数据 但假如数据较多 操作比较繁琐 简单 选择排序稳定比较次数与起泡排序一样 则相对之还要慢 快速排 序速度快 数据移动少 平均性能比较好 但是性能不稳定 希尔 排序是插入算法的改进 由于多次的插入造成了其稳定性不好 堆 排序在最坏情况下时间复杂度也为 O nlogn 并且它仅需一个记录 大小供交换用的辅助存储空间 但在记录数较少时不提倡使用 但本文主要介绍这 6 类排序 起泡排序 直接排序 简单选择 排序 快速排序 希尔排序 堆排序 一些优点和缺陷 对缺陷加 以改进 通过对传统算法的性能分析 发现其中的缺陷 对算法的 设想来弥补中间的不足 以致算法的性能有所提高 关键字 数据结构 内部排序 算法改进 性能分析 目目 录录 第 1 章 前 言 1 1 1 分析问题 1 1 2 研究背景 1 1 3 研究方向 2 1 4 研究方法 2 1 5 结构与安排 2 第 2 章 系统功能分析 3 2 1 需求分析及实现目标 3 2 1 1 应用现状及存在的问题 3 2 1 2 实现任务 3 2 2 可行性分析 4 2 2 1 技术可行性 4 2 2 2 工具可行性 4 2 2 3 经济可行性 4 2 2 4 操作可行性 4 第 3 章 总体设计 5 3 1 设计需求及描述 5 3 1 1 设计问题描述 5 3 1 2 设计需求分析 5 3 1 3 系统设计的实质功能 5 3 2 设计原理与设计内容 6 3 2 1 系统总体结构 6 3 2 2 内部操作过程 菜单设计原理如图所示 6 3 2 2 排序性能分析 菜单设计原理 7 3 2 3 设计内容 7 第 4 章 详细设计 9 4 1 冒泡排序 9 4 2 直接插入排序 10 4 3 希尔排序 11 4 4 简单选择排序 13 4 5 快速排序 14 4 6 堆排序 16 4 7 六种排序方法讨论 18 第 5 章 排序算法的改进 20 5 1 双向冒泡排序算法 20 5 2 双倍快速排序的算法 21 5 3 选择排序的算法 22 5 4 堆排序的改进算法 24 第六章 系统实现及数据测试 29 6 1 主界面 29 6 2 排序内部操作过程 菜单 29 6 2 1 当用户输入 0 6 的数字时则会随意的进入下一级子菜单 30 6 2 2 输入 2 进行 希尔 排序 30 6 3 性能分析 菜单 31 6 3 1 当用户输入 1 时进行 插入与希尔 排序之间的性能分析比较 31 6 3 2 当用户输入 1 时进行 插入与冒泡 排序之间的性能分析比较 32 总 结 33 参考文献 34 内部算法性能分析 第 1 章 前 言 1 第 1 章 前 言 1 1 分析问题 排序是指将一个数据元素序列排列成一个有序列的过程 排序是计算机的 一个重要的领域 并广泛应用于数据处理 情报检索 商业金融及企业管理等 许多方面 资料表明 在当今计算机系统中 花费在排序上的时间占了系统运 行的时间的很大比重 相当多的计算机中 有 50 以上的 CPU 时间是用在排序 数据上的 因此为了提高计算机系统的工作效率 研究和发展更有效的排序算 法的十分重要的 目前人们已经提出了许多不同的排序算法 然而如果在不适应的场合的应 用 那么其平均时间 averageTime 和最差时间 worstTime 就会不理想 其排序 算效率就会大大的降低 如国防系统和生命支持系统 如果排序方法性能低下 将会令我们大大的失望 另外用来衡量排序算法的标准是稳定性 在那些比较 复杂的排序中其稳定性不是很好 容易程序出错 就这样造成我们计算机的运 算时间加长和内存地址的浪费 1 2 研究背景 由于排序是数据结构中的重要的一个部分 也是在实际开发中易遇到的问 题 所以研究各种排序算法的时间消耗对于实际应用当中很有必要通过分析实 际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的 解决 该系统通过对各种内部排序算法如直接插入排序 冒泡排序 简单选择 排序 快速排序 希尔排序 堆排序等 以关键码的比较次数分析其特点 并 进行比较 估算每种算法的时间消耗 从而比较各种算法的优劣和使用情况 排序表的数据是多种不一样的情况 如随机产生数据 极端的数据如已是正序 或逆序数据 比较的结果用一个直方图来表示 然而在本文中我们将选择其中最基本也是最常用的 6 种内部排序 直接插 入排序 冒泡排序 简单选择排序 快速排序 希尔排序 堆排序 进行讨论 介绍它们的基本思想和实现过程 分析各种算法的时间 空间复杂性 比较次 数 移动次数以及稳定性 以期读者能够掌握这些算法及其特点中 在实际应 用中能够结合具体问题设计出正确而高效率的数据排序程序 内部算法性能分析 第 1 章 前 言 2 1 3 研究方向 排序算法其种类繁多 但还是有一些未解次的问题 例如 选择排序 快 速排序 希尔排序 堆排序仍然面临排序后的不稳定性 从而还面临一种稳定 的算法也可由不稳定的算法来实现 冒泡排序很容易实现 但是它的时间复杂 度和移动次数的问题仍然存在 更让人不可思议的是有些排序这两种缺点都存 在 同样每一种排序算法都有它的优缺点 适合于不同的环境 因此 在实际 应用中 应根据具体情况进行选择 首先 考虑排序对稳定性的要求 若要求 稳定 则只能在稳定的排序方法中选取 否则可以在所有的方法中选取 其次 要考虑待排序的序列记录数目 n 若 n 较大则可以在改进的方法中选取 否则 在简单方法中选取 然后再考虑其他因素 本文主要是通过排序来从中发现的 稳定性 比较次数以及移动次数等问题 从而从性能上分析得出不足并加以改 进 1 4 研究方法 基于 Visual C 6 0 平台编程是当今程序者的青睐 它有着强大的性能 完全丰富的工具及高速的处理速度和完备的兼容性 不仅可以简化编程的设计 并且算法应用灵活 使应用程序的开发更为简便 C 是为开发大型程序而研 制的 它比 C 语言困难得多 它功能丰富 表达能力强 使用灵活方便 应用 面广 目标程序效率高 可移植性好 既具有高级语言的优点 又具有低级语 言的许多特点 完全适合于编写系统软件 本人就利用上述 C 开发软件编写 了 内部排序算法性能分析系统 采用人机互动的操作模式 系统经过显示主 界面功能 然后用户的需要操作 实现了两种排序相互之间的优缺点 从而从 中获得一些性能分析结论让人们更好应用各种排序 1 5 结构与安排 本文主要是介绍六种排序的性能分析 首先 前言 对研究背景和研究目 的作了简单的介绍 其次 系统功能分析 对本系的说明和讲解 再次 总体 设计 对本系统做了一个简要引导 并且通过 总体设计 对该系统的运行懂 得差不多了 详细设计 就是对系统有了详细的设计过程 更进一步知道设 计原理 排序算法的改进 介绍传统算法的不足 经过设想对原算法加以改 进 系统实现及数据测试 不但让我们知道了系统的界面和一些操作的实施 让你知道整个算法的设计并且加以理解 内部算法性能分析 第 1 章 前 言 3 第 2 章 系统功能分析 2 1 需求分析及实现目标 2 1 1 应用现状及存在的问题 随着社会的发展 计算机科学技术应用又迈进了一大步 然而在很多的应 用过程中不时产生很多错误或延迟 尤其是在钢铁厂 天气预报的预测 火箭 的发射等一些大型的场所 这无疑处理器在处理的过程中不能出一些差错 因 此就要对那些已编制好的程序的算法要求比较严谨 排序就是其中之一 很多 人在运用的过程中对其算法不够了解或者考虑不周 因此给处理器造成了不必 的误时 就拿火箭发射来说 如果排序方法性能低下 将是非常危险的 我们 将会看到有几个排序算法能够提供某种保证机制 可以消除在最差情况下不可 接受的执行性能 另外存在一个比较大的问题就是排序的稳定性 稳定排序方法保持相等元 素的相关顺序 例如 假设有一个学生数组 其中的每一项由学生的姓和其品 质总分数组成 根据品质总分数排序 如果排序方法稳定 并且 balan 28 开始时位于比 wang 28 小的索引位置 排序后 balan 28 仍然位于比 wang 28 小的索引位置 稳定性可以简化工程开发 例如 假设上面提到的数组已经 根据排好序了 有一个根据品质总分数排序的应用程序调用 对于拥有同样品 质总分数的学生 他们的顺序还是按字母顺序 稳定排序不需要附加其他确保 相同品质总分数的学生按字母顺序排列的工作就可以完成了 因此 对于程序 员来说这是必备的重要技能 同时掌握它是他们当前一项急迫的任务 2 1 2 实现任务 排序数据是由系统随机产生 再通过用户根据自已所需的进行对这六种排 序的操作 简洁清晰 容易理解 提高了对该六种排序性能的应用 用户只需按界面上的提示操作 这六种排序的性能分析由系统自动的给予分析并且可以看到整个的排序过 程 如 移动的次数 比较的次数以及稳定性好坏 在系统随机产生数据是用户最好是多采用几组数据进行比较这样的正确率 要高 同时测试系统的性能好坏 内部算法性能分析 第 2 章 系统功能分析 4 2 2 可行性分析 所谓可行性分析就是用最小的代价在尽可能短的时间内确定问题是否能够 解决 这步工作的主要是要进行一次大大压缩简化了的系统分析和设计的过程 也就是在较高层次上以比较抽象的方式进行系统分析和设计的过程 可行性研 究的最根本任务是对以后的行动方针提出建议 以避免时间 资源 人力和金 钱的浪费 推荐一个较好的解决方案 并且为工程制定一个初步的计划 2 2 1 技术可行性 本系统采用人机操作进行管理 用 visual C 6 0 进行前台设计 系统随机 产生数据 用户通过界面操作 系统自动给予合理分析 由于 visual C 6 0 功 能强大 使用的灵活 良好的可扩展性 以及广泛实际应用 充分说明本系统 在技术方面的可行性 2 2 2 工具可行性 软件方面 信息时代对于软件的应用已不是人们的难题 人们在日常办公中用的计算 机操作的系统等都属于软件部分 硬件方面 计算机普及到今天 人们对于它的拥有已不少见 它的硬件设备完全能够 满足人们的需求 而价格也能被人们所接受 2 2 3 经济可行性 这是个超小型的性能分析系统 从投入的人力 财力与物力来讲是非常之 小的 只要一台电脑 一台打印机 这个系统就可以搞起来 考虑到学校里有 电脑 现只要购置一台打印机就可以了 从节省人力方面 可以让管理人员从 繁与复杂的工作中解脱出来 做更多的工作 可以给读者提高到更深的一个层 次 2 2 4 操作可行性 本系统设计清晰 有良好的用户接口 操作简洁 完全可以给用户解决 内部算法性能分析 第 2 章 系统功能分析 5 并达到操作过程中的直观 方便 实用 安全等要求 因此操作方面具有可行 性 第 3 章 总体设计 3 1 设计需求及描述 3 1 1 设计问题描述 设计一个测试程序比较起泡排序 直接排序 简单选择排序 快速排序 希尔排序 堆排序算法的关键字比较次数和移动次数以取得直观感受 待排序 表的表长不小于 10 表中数据随机产生 至少用 5 组不同数据作比较 比较指 标有 关键字参加比较次数和关键字的移动次数 关键字交换记为 3 次移动 最后输出比较结果 3 1 2 设计需求分析 用数组 S 来存放系统随机产生的 100 个数据 并放到 R 数组中 数据由程 序随机产生 用户只需查看结果 利用全局变量 times 和 changes 来分别统计起泡排序 直接排序 简单选择 排序 快速排序 希尔排序 堆排序算法的比较次数和移动次数 然后输出结 果 并在每一次统计之后 将 times 和 changes 都赋值为 0 在主函数中调用用户自定义函数 输出比较结果 本程序是对几种内部排序算法的关键字进行性能分析的程序 它分为以下 几个部分 a 建立数组 b 调用函数求比较和移动次数 c 输出结果 3 1 3 系统设计的实质功能 用户启动该系统进入主菜单 在主菜单中有三个菜单命令 可以按照用户 的意愿来选择他想要的命令 当你选择 排序内部操作过程 菜单时 即可进入一下子菜单 你可以看 到这六种排序的内部排序过程 并且可以知道这六种排序具体的移动次数 比 内部算法性能分析 第 3 章 总体设计 6 较次数以及稳定性的好坏 当你选择 排序性能分析 菜单时 马上进入下一级子菜单 你可以知道 这六种排序之间的一些性能相关的知识 这一级菜单是用户来安排 如果不知 道那两种排序的性能那种占优势好一些 你可以输入排序的编号 然后系统给 你分析 给出结论 3 2 设计原理与设计内容 3 2 1 系统总体结构 系统总体结构如图 4 1 所示 图 3 1 系统总体结构 3 2 2 内部操作过程 菜单设计原理如图所示 Switch 进行判断 partition 函数进行 快速排序 Heapsort 函数进行 堆排序 Selectsort 函数进行 简单选择 排序 Shllinsert 函数进行 希尔排序 Insertsort 函数进行 直接排序 子函数结束 Bubblesort 函数 进行直接 排序 Point 开 始 冒 泡 排 序 希 尔 排 序 直 接 插 入 排 序 堆 排 序 简 单 选 择 排 序 快 速 排 序 冒 泡 性 能 分 析 希 尔 性 能 分 析 插 入 性 能 分 析 选 择 性 能 分 析 快 速 性 能 分 析 堆 性 能 分 析 内部排序算法性能分析 排序过程模块性能分析模块 内部算法性能分析 第 3 章 总体设计 7 图 3 2 内部操作过程 菜单 3 2 2 排序性能分析 菜单设计原理 排序性能分析 菜单的算法是调用 内部操作过程 菜单的算法 根据 这一原理而成的 就不一一的介绍了 请读者自已去理解 内部操作过程 的 设计过程 3 2 3 设计内容 内部排序系统具体实现的功能包括 快速排序 冒泡排序 希尔排序 简 单选择排序 堆排序 直接排序等这六大排序的集成六个主要的函数如下 快速排序函数 partition 希尔排序函数 Shellsort 简单选择排序函数 selectsort 堆排序函数 heap 直接排序函数 insertsort 起泡排序函数 Bubblesort 排序数据类型定义 ADT paixu 数据对象 D aij aij属于 1 2 3 i j 0 数据关系 R ai 1 ai D i 2 n 基本操作 Insertsort 初始条件 数组已经存在 操作过程 将一个记录插入到已经排好序的有序列表中 从而得到了一个 新的 记录新增 1 的有序表 Bubblesort 初始条件 数组已经存在 内部算法性能分析 第 3 章 总体设计 8 操作过程 两两比较待排序记录的键值 并交换不满足顺序要求的那些偶 对 知道全部满足顺序要求为止 Shellsort 初始条件 数组已经存在 操作过程 先取定一个正整数 d1 n 把全部记录分成 d1 个组 所有距离为 d1 倍数的记录放在一组中 在各组内进行插入排序 然后取 d2 d1 重复上述分 组和排序工作 直至取 di 1 即所有记录放在一个组中排序为止 Selectsort 初始条件 数组已经存在 操作过程 每次从待排序的记录中选出键值最小 或最大 的记录 顺序 放在已经排序的记录序列的最好 直到全部排完 heapsort 初始条件 数组已经存在 操作过程 对一组待排序的的键值 首先是把它们按堆的定义排列成一个 序列 这就找到了最小键值 然后把最小的键值取出 用剩下的键值再重建堆 便得到次小键值 如此反复进行 知道把全部键值排好序为止 partition 初始条件 数组已经存在 操作过程 在待排序的 n 个记录中任取一个记录 以该记录的键值为基准 用交换的方法将所有记录分成两部分 所有键值比它小的放在一边 大的放另 一边 并把该记录放在中间 然后重复至完成 ADT 排序 内部算法性能分析 第 3 章 总体设计 9 第 4 章 详细设计 4 1 冒泡排序 冒泡排序 BubbleSort 是我们大家都熟知的排序 其基本概念是 依次比 较相邻的两个数 将小数放在前面 大数放在后面 即在第一趟 首先比较第 1 个和第 2 个数 将小数放前 大数放后 然后比较第 2 个数和第 3 个数 将 小数放前 大数放后 如此继续 直至比较最后两个数 将小数放前 大数放 后 至此第一趟结束 将最大的数放到了最后 在第二趟 仍从第一对数开始 比较 因为可能由于第 2 个数和第 3 个数的交换 使得第 1 个数不再小于第 2 个数 将小数放前 大数放后 一直比较到倒数第二个数 倒数第一的位置上 已经是最大的 第二趟结束 在倒数第二的位置上得到一个新的最大数 其实 在整个数列中是第二大的数 如此下去 重复以上过程 直至最终完成排序 由于在排序过程中总是小数往前放 大数往后放 相当于气泡往上升 所 以称作冒泡排序 用二重循环实现 外循环变量设为 i 内循环变量设为 j 外循环重复 9 次 内循环依次重复 9 8 1 次 每次进行比较的两个元素都是与内循环 j 有关 的 它们可以分别用 a j 和 a j 1 标识 i 的值依次为 1 2 9 对于每一个 i j 的值依次为 1 2 10 i 算法 for i 1 i i 1 j 内循环 进行每趟比较 times 比较次数 if R j R j 1 如果 R j 小于 R j 1 交换两者的位置 内部算法性能分析 第 4 章 详细设计 10 R 0 R j R j R j 1 R j 1 R 0 exchange TRUE changes 3 移动次数 冒泡排序的最好 最坏 平均情况下的时间复杂度都为 O n2 故算法 的平均时间复杂度也为 O n2 但是若在某趟排序中未发现气泡位置的交换 则 说明待排序的无序区中所有气泡均满足轻者在上 重者在下的原则 即为正序 则冒泡排序过程可在此趟扫描后就终止 在每趟排序过程中 无序区 R i n 的范围可能会有较大改变 而不是递减 对某些不对称性情况 在排序过程中 可改变其扫描方向 4 2 直接插入排序 直接插入排序 Straight Insertion Sort 是一种最简单的排序方法 它基本操作 是将一个记录插入到已排好序的有序表中 从而得到一个新的 记录数增 1 的 有序表 每次从无序表中取出第一个元素 把它插入到有序表的合适位置 使有序 表仍然有序 第一趟比较前两个数 然后把第二个数按大小插入到有序表中 第二趟把第 三个数据与前两个数从前向后扫描 把第三个数按大小插入到有序表中 依次 进行下去 进行了 n 1 趟扫描以后就完成了整个排序过程 直接插入排序是由两层嵌套循环组成的 外层循环标识并决定待比较的数 值 内层循环为待比较数值确定其最终位置 直接插入排序是将待比较的数值 与它的前一个数值进行比较 所以外层循环是从第二个数值开始的 当前一数 值比待比较数值大的情况下继续循环比较 直到找到比待比较数值小的并将待 比较数值置入其后一位置 结束该次循环 值得注意的是 我们必需用一个存储空间来保存当前待比较的数值 因为 当一趟比较完成时 我们要将待比较数值置入比它小的数值的后一位 插入排序 类似玩牌时整理手中纸牌的过程 插入排序的基本方法是 每步将一个待排序 的记录按其关键字的大小插到前面已经排序的序列中的适当位置 直到全部记 录插入完毕为止 算法 for i 2 i L i 内部算法性能分析 第 4 章 详细设计 11 if R i R i 1 R 0 R i j i 1 复制哨兵 while R 0 R j times changes R j 1 R j j 记录后移 R j 1 R 0 插入到正确位置 changes 按以上算法进行直接插入排序的过程如图4 1 所示 初始序列 i 1 46 58 15 45 90 18 10 62 i 2 46 58 15 45 90 18 10 62 i 3 15 46 58 45 90 18 10 62 i 4 15 45 46 58 90 18 10 62 i 5 15 45 46 58 90 18 10 62 i 6 15 18 45 46 58 90 10 62 i 7 10 15 18 45 46 58 90 62 i 8 10 15 18 45 46 58 62 90 图 4 1 直接插入排序过程 从算法的实现过程可见 在最坏情况下 线性插入排序每插入一个元素需 要进行 i 1 次比较 需要插入元素为 N 1 个 所以最大比较次数为 N N 1 2 该算法的时间复杂性为 O N N 空间复杂度为 O 1 因此 直接插入排序属于 稳定的排序 4 3 希尔排序 内部算法性能分析 第 4 章 详细设计 12 希尔排序 Shell Sort 又称 缩小增量排序 Diminishing Increment Sort 它 也是一种属于插入排序类的方法 但在时间效率上跟其他的几种排序方法有了 较大的改进 希尔排序基本思想 先将整个待排记录序列分割成为若干子序列分别进行 直接插入排序 待整个序列中的记录 基本有序 时 再对全体记录进行一次 直接插入排序 先看一下希尔排序的过程 初始关键字序列如下面所示 首先将该序列分 成 5 个子序列 R1 R6 R2 R7 R5 R10 如下面所示 分别对每个子序列 进行直接插入排序 排序完后 然后进行第二趟希尔排序 即分别对下列 3 个 子序列 R1 R4 R7 R10 R2 R5 R8 和 R3 R6 R9 进行直接插入排序 其结果 如第二趟排序所示 最后对整个序列进行一趟直接插入排序 至此 希尔排序 结束 整个序列的记录已按关键字非递减有序排列 如下图 4 2 所示 初始关键字 49 38 65 97 76 13 49 55 04 一趟排序结果 13 27 49 55 04 49 38 65 97 76 13 55 38 76 27 04 65 49 49 97 二趟排序结果 13 04 49 38 27 49 55 65 97 76 三趟排序结果 04 13 27 38 49 49 55 65 76 97 图 4 2 希尔排序过程 从上述排序过程可见 希尔排序的一个特点是 子序列的构成不是简单地 逐段分割 而是将相隔某个 增量 的记录组成一个子序列 如上例中 第 一趟排序时的增量为 5 第二趟排序时的增量为 3 第三趟排序时的增量为 1 由于在前两趟的插入排序中记录的关键字是和同一子序列中的前一个记录的关 键进行比较 到越后面排序的数变得越来越有序 为此算法如下 4913 3827 6549 9755 7604 内部算法性能分析 第 4 章 详细设计 13 for i d 1 i n i 将 R d 1 n 分别插入各组当前的有序区 if R i key0i L i n i for j i 1 j L j times if R j 1 i 将二叉树转换成堆 CreateHeap i L 建堆 for i L 1 k 1 i 1 i k temp R i 1 堆 heap 的 root 值和最后一个值交换 R i 1 R 1 R 1 temp changes 3 CreateHeap 1 i 内部算法性能分析 第 4 章 详细设计 18 从上述分析 堆 排序的时间 主要由建立初始 堆和反复重建堆这两部分 的时间开销构成 它们均是通过调用 CreateHeap 实现的 堆排序的最坏时间复杂度为 O nlogn 堆序的平均性能较接近于最坏性能 由于建初始堆所需的比较次数较多 所以堆排序不适宜于记录数较少的文件 堆排序是就地排序 辅助空间为 O 1 由它是不稳定的排序方法 4 7 六种排序方法讨论 综合比较上述的各种内部排序方法 大致有如下结果 见下表 表 4 1 时间复杂度 排序 方法 最少比较 次数 最多比较次 数 最少移 动次数 最多移动 次数 最坏情况最好情况平均情况 空间 复杂 度 稳 定 性 复 杂 度 直接 插入 排序 n 1 n 2 n 1 2 0 n 4 n 1 2O n n O n O n n O 1 是 简 单 简单 选择 排序 n n 1 2n n 1 2 0 3 n 1 O n n O n n O n n O 1 否 简 单 快速 排序 O nlogn n n 1 2 O nlogn n n 1 2O n n O nlogn O nlogn O log n 是 较 复 杂 希尔 排序 O nlogn O nlogn O 1 否 较 复 杂 冒泡 排序 n 1 n n 1 20 n n 1 2O n n O n O n n O 1 是 简 单 内部算法性能分析 第 4 章 详细设计 19 堆排 序 O nlogn O nlogn O nlogn O nlogn O 1 否 较 复 杂 附注 1 堆排序 冒泡排序 希尔排序和快速排序中 在待排序的数据已经基 本有序是 花费时间最多的反而是快速排序 此是最不利于发挥其特 长 2 在以比较为基础的排序方法中 比较关键字的大小 和 将关键字从 一个位置移动到另一个位置 这两种操作的次数决定了算法的时间复 杂性 它们是算法的时间复杂性的两项指标 3 在局部有序和待排序的关键字序列数目较小时 最佳的内部排序方法 是直接插入排序 4 在冒泡排序的每一趟中 只能将关键字最大或最小的元素移动到正确 的置 其他关键字有可能在交换的过程中朝着与最终排序相反方向移 动 快速排序的每一趟中 不仅能将枢轴的元素移动到正确的位置 而且其他关键字所移动的方向也与其最终排序的位置方向一致 5 设有一个堆 取出堆中最大元素后 将它重新调整为堆 所需要的时 间复杂度为 O nlogn 6 假设待排序的关键字序列有 n 例如 n 10000 个元素 若仅找出其 中最大的 k 例如 k 10 个元素 则采有堆排序最省时间 若仅找出 其中第 k 个最小元素 则采用快速排序最省时间 如何选择好的排序方法 没有哪一种排序方法是绝对好的 每一种排序方都有优缺点 适合于不同 的环境 因此 在实际应用中 应根据具体情况进行选择 首先 考虑排序对 稳定性的要求 若要求稳定 则只能在稳定的排序方法中选取 否则可以在所 有的方法中选取 其次要考虑待排序列的记录数目 n 若 n 较大 则可以在改 进的方法中选取 否则在简单方法中选取 然后再考虑其他因素 综上所述 可得以上结论 1 当待排序的序列的记录数目 n 较大 记录按关键字的值分布比较随机 并且 对排序稳定必不作要求时 宜选用快速排序 2 当待排序的序列的记录数目 n 较大 记录按关键字的值分布可能出现升序或 逆序的情况 并且对排序稳定性不作要求时 宜选用堆排序 3 当待排序的序列的记录数目 n 较小 记录的关键字的排列基本有序 分布比 较随机且对排序有稳定性要求时 宜选用插入排序 内部算法性能分析 第 4 章 详细设计 20 4 当待排序的序列的记录数目 n 较小 并且对排序有稳定性要求进 宜选用选 择排序 若记录的关键字的值不接近逆序 也可选用直接插入排序 第 5 章 排序算法的改进 5 1 双向冒泡排序算法 对于输入的子序列 L low High 看成竖着排列的 气泡 然后分别从上端 Low 向底端 High 扫描 在扫描的过程中时刻注意两个相邻元素的顺序 保 证上端的元素小于下端的元素 这样经过一趟扫描后就使较大的元素沉到下面 然后再从底端向上端扫描 由于在前一趟扫描过程中最大的元素已经沉到最底 端 所以这次扫描最大的元素不再参加排序 将剩下的元素进行排序 排序的过 程中保证使得底端元素大于顶端元素 这样反复的扫描 并不断缩小排序空间 直到整个序列有序位置 这样直观上看 双向冒泡排序法先让重的气泡沉到底 下 然后让轻的气泡浮上来 然后再让大的气泡沉下去 让次轻的气泡浮上来 依次反复 直到带排序列有序为止 算法是利用两个指针 low 和 high 记录带排序列区域 L low high 用指 针变量 t 记录在每趟扫描过程中最近一次交换记录的位置 在每次扫描开始 t 的初始值分别为 Low 或 high 并且在扫描结束后再让 t 和 low 或 high 进行比 内部算法性能分析 第 5 章 排序算法的改进 21 较 如果发现某次 t 值没有改变 则说明序列已经有序 并且用 break 跳出循环 提 前结束排序 代码实现 While low high t low t 指向带排序区间的离最底端 For i low i L i 1 m l i l i l i 1 l i 1 m t i 记录最近一次移动的关键字的位置 if t low break 检查是否待排关键字有序 如有序则退 出循环 结束排序 else high t 缩小待排序列的范围 for i high i low i if L i L i 1 m l i l i l i 1 l i 1 m t i 记录最近一次移动的关键字的位置 If t high break 检查是否排关键字有序 如有序则退出循环 结束排序 else low t 缩小待排序列的范围 算法分析 双向冒泡排算法是原地置换算法 并且由于 L i L i 1 或者 L i L i 1 时才进行交换 所以说该算法也是稳定的排序方法 但如 果改为 L i L i 1 或者 L i L i 1 时才进行交换 则改变其的 稳定性 该算法在执行一趟排序后同时确定两个记录的位置 即待排区域的最 大和最小的记录 而书中提到的冒泡排序在执行行一趟排序后仅能确定一个记 录的位置 即最大或最小的 显然该算法更可取 5 2 双倍快速排序的算法 快速排序的基本思想是基于分支策略的思想 即对于输入的子序列 L low High 如果规模足够小则直接进行排序 否则分三步处理 分解 Divide 设输入的序列 L low High 确定支点元素 L low 和 L High 并使 L Low key Ll High key 然后分解 Divide 将序列 L low High 划分成三个子序列 L Low L 1 L 1 H 1 和 L H 1 High 使 L low High 中元素的关系为 L Low L 1 L L L L 1 H 1 L H r high t r row 确保区间内第一个元素的值不大于区间内最后一个元素的值 r row r high r high t l low 小于区间内第一个元素的值数组边界下标 h high 大于区间内最后一个元素的值数组边界下标 for i low 1 i n i if r i r high t r i r i r high 1 r high t 大于区间内最后一个元素的值放置H 区内 i n 下一个比较位置不变 循环次数减一 t r L r L r low r low t 将小于区间内第一个元素的边界下标元素与第一个元素互换 t r H r H r high r high t 将大于区间内最后一个元素边界下标元素与最后一个元素互换 QSort L low L 1 对分解后的第一部分递归快速排序 QSort L L 1 H 1 对分解后的第二部分递归快速排序 内部算法性能分析 第 5 章 排序算法的改进 23 QSort L H 1 high 对分解后的第三部分递归快速排序 以上分析可知 Low 和 High 分别指向区间的第一个元素和最后一个元素 并保证 L Low L High L 和 H 两个折针所指向的元素分别是第一个和第 二个枢轴元素 同样保证 L L L H 经过一趟排序后 即确定了两个枢轴元 素的位置 然后对三个子序列分别进行递归分解 每分解一次就确定两个元素的 位置 直到整个序列有序为止 算法分析 双倍快速排序算法在经过一趟快速排序后可以同时确地两个元 素的位置 而快速排序算法经过一趟快速排序后只能确定一个元素的位置 前者 将带排序列分解成三个待排序列 而后者仅仅分解成两个序列 所以就这一点上 来看 对同数量级的序列 双倍快速排序在时间性能上要优于快速排序 空间性 能上 两者上相同的 只有一个辅助空间 双倍快速排序是一个快速原地置换排 序也是一个稳定排序法 5 3 选择排序的算法 该算法在一定程度上克服了传统排序算法交换次数过多的缺陷 但其效率 仍较为低下 能否在进行第 i 趟排序时 在第 i n 个项目中既选择一个关键字 最大的项目 又选择一个关键字最小的项目 然后将其交换至它们应在的位置以 进一步提高效率呢 易知 若需对第 1 n 个项目组成的序列采用改进后的选择法进行排序 无 需进行 n 1 趟排序 最多只需进行 n 2 趟排序 符号 n 2 指不大于 n 2 的最大整数 下同 第 i 趟排序前 关键字最大的 i 1 个项目及最小的 i 1 个项目已被交换至它们应在的位置 故第 i 趟排序仅需对剩下的第 i n i 1 个项目进行 在第 i 个项目的关键字与其后的第 i 1 n 个项目的关键字都 比较完后 选择第 i n 个项目中关键字最 大 项目交换至第 i 个项目的位置 并选择关键字第 i 小 的元素交换至第 n i 1 个项目的位置 所以改进后的选 择法排序的关键在于在进行第 i 趟排序时 在第 i n i 1 项目中找出关键 字最 大 的项目的下标序号 即位置 及关键字最 小 的项目的下标序号 然后 将关键字最 大 的项目及关键字最 小 的项目进行合理高效的移动 在进行第 i 趟排序时 容易做到在 i n i 1 项目中既找出关键字最 大 的项目的下标序号 max col 又找出关键字最 小 的项目的下标序号 mincol 但在进行将关键字最 大 的项目移至第 i 个项目的位置及将关键字最 小 的项 目移至第 n 1 i 个项目的位置的过程时却须仔细斟酌 尤其要注意移动项目 的顺序及项目移动过程中其下标序号 即位置 的动态变化 否则极易出现错误 下面让我们来深入分析 确定项 目移动过程的顺序 1 当剩余的未排序项目即 内部算法性能分析 第 5 章 排序算法的改进 24 第 i n i 1 项目中关键字最 大 的项目不是第 i 个项目 即其下标序号 max co l i 时 首先应将第 i 个项目与第 max co l 个项目相交换 然后 若第 i n i 1 项目中关键字最 小 者即是原来第 i 个项目 即 m inco l i 时 因原来第 个项目已交换至第 max col 个项目 故应将第 max co l 个项目与第 n i 1 个 项目相交换 若第 i n i 1 项目中关键字最 小 者不是原来第 i 个项目 即 mincol i 时 应将第 mincol 个项目与第 n i 1 个项目相交换 2 当剩余的 未排序项目即第 i n i 1 项目中关键字最 大 的项目即是第 i 个项目 即其 下标序号 maxcol i 时 故无需将第 i 个项目与第 max co l 个项目相交换 此时 若第 i n i 1 项目中关键字最 小 者不是原来第 n 1 i 个项目 即 mincol n 1 i 时 应将第 mincol 个项目与第 n i 1 个项目相交换 这样进 行项目的移动才可避免发生错误如上所述对传统的选择排序算法进行改进 可 使其效率得到一定程度的提高 根据其特点姑且将其命名为双向选择排序算法 当然若某一趟排序过程中项目间未进行交换操作 则意味着所有 n 个项目已排 好序 无需再进行下一趟排序 算法如下 for i 1 i n 2 i times 0 max array i m axco l imin array i mincol i fo r j i 1 j max max array j maxcol i times if array j 1 i shift i n 3 buildheap3 shift int i int n 3 将 k i k n 整理成堆 3 x k i j 23 i while j n if j n k i k j i j j 23 i k i x 3shift3 重新建堆 rebuild int x int n intdeep i 1 j 23 i d 0 while j n d d 1 if j n k i k j i j j 23 i while i 1 i n 2 k i x 3rebuild3 在堆深 h log2 n 时 此时堆中的元素一般说来已基本有序 重新建堆实 际上变成先通过 h 次比较降至堆底 然后再适当上升将尾结点放在正确的位置 heapsort buildheap for j n j 2 j x k j k j k 1 rebuild x j 1 log 2 n 算法分析堆排序算法因其比较和所需额外空间少而被广泛地采用 最坏的 内部算法性能分析 第 5 章 排序算法的改进 27 情况下有 11 222 22 1 1 log log log 1 1 22 1 nn ii h d t niiddid n d d nhd n d 当d 4时 有t n 5 4 nlog 2 n O n 为了确定 d 的最佳取值 通过对f d h h d d 求极限 可知当 d h时f d 有极小值 h 2 h 又通过对 求极限可知当 1 2 2 1 log 1 n i d t nid n d 时 t n 最小 再先取 1 1 2 2 log 1 22 1 1 n h i dinnhnh 以后每次重新建堆时都使用d值 dh 1 1 22 1 2 h h t nnhnhnhn hn h 所以可以得出结论 在最坏情况下改进算法的时间复杂度为 22 loglog 12t nnncnnc 当时 有 虽然不是一个常数 但相对 n 来说 16n 2 2 logt nnn 2 log n 其增长非常慢 所以时 所以n越大改进的效果就越明显 400 2n 2 log20n 5 5 2插入改进算法 对于数组 A 0 a low a start 1 a start a end a n 1 0 low start end n 1 其中 a 0 a low a start 1 为已排好序的部分 a start a end a n 1 为待插入的部分 在原来的插入算法中 当我们找到 待插入元素 a start 应该插入的位置 low 后 先将 a start 暂存 然后将 a low a start 1 后移一位 再将暂存的 a strat 插入 a low 处 在改进的插入算法 中 我们还要考察在 a start 之后 是否还存在一个序列 a start 1 a end 使得 a start a start 1 a end a low 如果确实存在这样的的一个序列 则我们可以一次性将 a start a end 插 入 a low 处 在原有的的基础上作一些改进得出如下算法 for start 1 start n start low 0 high start 1 内部算法性能分析 第 5 章 排序算法的改进 28 while low high moddle int low high 2 if a moddle a start low moddle 1 else high moddle 1 end start 1 while end n end newmove a low start end start end 新的循环移位插入算法如下 L start low p end low 1 n p m L r p m while r 0 n m m r r n m for i 0 i m i outpos i inpos i temp a i low while outpos inpos L p i a inpos low a outpos low inpos outpos a inpos low temp 性能分析 在比较插入过程中 若出现一次可插入的部分有序段 a start a end 设插入位置在 a low 开始位置处 则涉及移动的序为 a low a start a end 需插入的元素个数为 Q end start 1 涉及移动的元 素总数为 P end low 1 插入间距为 L start low 在原插入算法中 每插入一 内部算法性能分析 第 5 章 排序算法的改进 29 个元素需移动 start low 2 次 故总共需移动 start low 2 end start 1 次 而在改 进插入算法中 只需移动 end low m end start 1 start low m 1 次 其中 m gcd P L 两者比值为 改进插入算法动次数 1 1 原插入算法移动次数 Q P 一般情况下 插入间距 L 远大于待插入的元素个数 Q 所以上式主要取于 1 Q 由此可见 只要出现一次有 Q 个元素的可插入的部分有序段 该部分的 插入效率可提高 Q 倍 整个改进插入算法的效率提高取决于出现可插入的部分 有序段的概率和可插入的部分有序段的长度 而且后者比前者更为积极作用 改过算法的稳定性取决于找到有序的 a start a end 时的判断条件 如果我们采用 End n a end 1 a end 作为判断条件 则改进的算法是稳定的 如果为了一次尽可能多的插入元 素 提高排序速度采用 End n a end 1 a end 作为判断条件 则改进算是不稳定的 第六章 系统实现及数据测试 6 1 主界面 当用户启动该程序时进行测试 进入主菜单如图 6 1 所示 内部算法性能分析 参考文献 30 图 6 1 主菜单 6 2 排序内部操作过程 菜单 当用户输入 1 时进入 排序内部操作过程 菜单如图 6 2 所示 图 6 2 排序内部操作过程 菜单 6 2 1 当用户输入 0 6 的数字时则会随意的进入下一级子