堆排序及算法分析

堆排序及算法分析 前言前言 记得在学习数据结构的时候一味的想用代码实现算法 重视的是写出来的代码有一个正确 的输入 然后有一个正确的输出 那么就很满足了 从网上看了许多的代码 看了之后貌 似懂了 自己写完之后也正确了 但是不久之后就忘了 因为大脑在回忆的时候 只依稀 记得代码中的部分 那么的模糊 根本不能再次写出正确的代码 也许在第一次写的时候 是因为参考了别人的代码 看过之后大脑可以进行短暂的高清晰记忆 于是欺骗了我 以 为自己写出来的 满足了成就感 可是代码是计算机识别的 而我们更喜欢文字 图像 所以我们在学习算法的时候要注重算法的原理以及算法的分析 用文字 图像表达出来 然后当需要用的时候再将文字转换为代码 记忆分为三个步骤 编码 存储和检索 就以 学习为例 先理解知识 再归纳知识 最后巩固知识 为了以后的应用而方便检索知识 堆排序过程堆排序过程 堆分为大根堆和小根堆 是完全二叉树完全二叉树 大根堆的要求是每个节点的值都不大于其父节点 的值 即 A PARENT i A i 在数组的非降序排序中 需要使用的就是大根堆 因为 根据大根堆的要求可知 最大的值一定在堆顶 既然是堆排序 自然需要先建立一个堆 而建堆的核心内容是调整堆 使二叉树满足堆的 定义 每个节点的值都不大于其父节点的值 调堆的过程应该从最后一个非叶子节点最后一个非叶子节点开 始 假设有数组 A 1 3 4 5 7 2 6 8 0 那么调堆的过程如下图 数组下标从 0 开始 A 3 5 开始 分别与左孩子和右孩子比较大小 如果 A 3 最大 则不用调整 否则和孩 子中的值最大的一个交换位置 在图 1 中是 A 7 A 3 A 8 所以 A 3 与 A 7 对换 从 图 1 1 转到图 1 2 所以建堆的过程就是 1 for i headLen 2 i 0 i 2 3 do AdjustHeap A heapLen i 调堆 如果初始数组是非降序排序 那么就不需要调堆 直接就满足堆的定义 此为最好 情况 运行时间为 1 如果初始数组是如图 1 5 只有 A 0 1 不满足堆的定义 经过 与子节点的比较调整到图 1 6 但是图 1 6 仍然不满足堆的定义 所以要递归调整 一直到 满足堆的定义或者到堆底为止 如果递归调堆到堆底才结束 那么是最坏情况 运行时间 为 O h h 为需要调整的节点的高度 堆底高度为 0 堆顶高度为 floor logn 建堆完成之后 堆如图 1 7 是个大根堆 将 A 0 8 与 A heapLen 1 交换 然后 heapLen 减一 如图 2 1 然后 AdjustHeap A heapLen 1 0 如图 2 2 如此交换堆的第一个元 素和堆的最后一个元素 然后堆的大小 heapLen 减一 对堆的大小为 heapLen 的堆进行 调堆 如此循环 直到 heapLen 1 时停止 最后得出结果如图 3 1 2 输入 数组 A 堆的长度 hLen 以及需要调整的节点 i 3 功能 调堆 4 5 6 void AdjustHeap int A int hLen int i 7 8 int left LeftChild i 节点 i 的左孩子 9 int right RightChild i 节点 i 的右孩子节点 10 int largest i 11 int temp 12 13 while left hLen right hLen 14 15 if left hLen 18 19 20 if right hLen i 51 52 AdjustHeap A hLen i 53 54 55 56 57 输入 数组 A 待排序数组的大小 aLen 58 功能 堆排序 59 60 void HeapSort int A int aLen 61 62 int hLen aLen 63 int temp 64 65 BuildHeap A hLen 建堆 66 67 while hLen 1 68 69 temp A hLen 1 交换堆的第一个元素和堆的最后一个 元素 70 A hLen 1 A 0 71 A 0 temp 72 hLen 堆的大小减一 73 AdjustHeap A hLen 0 调堆 74 75 性能分析性能分析 调堆 调堆 上面已经分析了 调堆的运行时间为 O h 建堆建堆 每一层最多的节点个数为 n1 ceil n 2 h 1 因此 建堆的运行时间是 O n 循环调堆 代码循环调堆 代码 67 74 因为需要调堆的是堆顶元素 所以运行时间是 O h O floor logn 所以循环调堆的运行时间为 O nlogn 总运行时间 T n O nlogn O n O nlogn 对于堆排序的最好情况与最坏情况的运行 时间 因为最坏与最好的输入都只是影响建堆的运行时间 O 1 或者 O n 而在总体时间中 占重要比例的是循环调堆的过程 即 O nlogn O 1 O nlogn O n O nlogn 因此 最好或者最坏情况下 堆排序的