第二部分,排序和顺序统计学
在笔记一中, 我们实现了两个排序算法:插入排序和归并排序。
第六章是堆排序。现在就是第六章。
这里的堆,不是堆栈的堆,那个一般是指一块动态分配的内存:)
这里的堆是一个数据结构,它是一个二叉树(二叉堆),可以存在数组中
像这样:
16
/ \
14 10
/ \ / \
8 7 9 3 -> 16 14 10 8 7 9 3 2 4 1
/ \ /
2 4 1
根要比左右两个结点要大,并且左右子树也是一个堆--> 是一个递归定义
可以用这样的代码来表示上述定义
boolean isHeap(int[] a, int i) {
int n = a.length;
if (i >= n) {
return true;
}
int left = 2 * i + 1; // 左节点
int right = 2 * i + 2; // 右节点
if (left < n && a[left] > a[i]) { // 比左右都要大,否则不行
return false;
}
if (right < n && a[right] > a[i]) {
return false;
}
return isHeap(a, left) && isHeap(a, right); // 左右子树也是堆
}
然后写一个测试运行一下:
@Test
public void testIsHeap() {
int[] a = { 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 }; // 就是上述图示数据
assertTrue(isHeap(a, 0));
}
显然, 根节点就是最大的。那么堆排序就是基于这个特性:每次选出"最大的", 再建,再选, 直到排好:)
算法像这样:
void heapSort(int[] a) {
buildHeap(a); // 首先,建一个堆, 此时a[0] 就是最大的元素
for (int i = a.length - 1; i > 0; i--) { // 每次"选出"最大的元素, 共需要进行 n - 1 次
swap(a, 0, i); // 在这之后, i 以及后面的元素都是有序的
heapify(a, 0, i - 1); // 根元素由于被交换过,所以需要进行一次“调整”,
// 让他再变成堆
}
}
算法很简单, 但是编译还是不通过的:) 因为有三个方法还没有完成。
swap:交换数组元素, 这个很容易,属于"模板代码" (PS:晚上喝了好些杨梅酒, 希望不要错)
void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
再来 heapify, 这个比较容易些:)
// 此时 i 的左右子树都是堆 (j 后面的元素不管,不属于堆), 我们要把他调整成堆
void heapify(int[] a, int i, int j) {
int left = i * 2 + 1;
int right = i * 2 + 2;
if (left > j) { // 没有左子树? 那就好了
return;
}
int large = left; // large 是大的这个
if (right <= j && a[left] < a[right]) {
large = right;
}
if (a[i] < a[large]) { // 根元素比 large 小? 交换根和 large
swap(a, i, large);
heapify(a, large, j); 此时 large 树 又可能不是堆了, 那就继续努力:)
}
}
建堆是这样滴
void buildHeap(int[] a) {
int n = a.length;
for (int i = n / 2 - 1; i >= 0; --i) { // n / 2 - 1, 就是最后一个有子节点的元素
heapify(a, i, n - 1); // 偶们从这开始,不断调整,直到整个数组变成堆
}
}
现在完工了, 然后再写一个测试代码测试它---证明比较累, 无情的测试相对容易些
可以测试空数组,一个元素,两个元素, 一万个元素的随机数组, 测试一万次。 都green, 就米问题了:)
@Test
public void testHeapSort() {
for (int i = 0; i < 10000; i++) {
int[] array = genRandAry(i);
heapSort(array);
assertTrue(isSorted(array));
}
}
以上 genRandAry 以及 isSorted , 见“算法笔记1”
程序要跑起来,算法要写出来。。否则变成纯思维,很纠结
照惯例,要看看算法的复杂度。对于排序而言, 就是看看比较次数,因为排序的主要操作就是比较(这里的排序是基于比较的)
下面,我们要修改heapSort, 现在不是排序,而是求heapSort的比较次数
由于heapify是基本操作, 先来分析它:)
目标是,要把下面方法重构成 计算比较次数
void heapify(int[] a, int i, int j) {
int left = i * 2 + 1;
int right = i * 2 + 2;
if (left > j) {
return;
}
int large = left;
if (right <= j && a[left] < a[right]) { // 这里是一次元素比较
large = right;
}
if (a[i] < a[large]) { // 这里又是一次比较
swap(a, i, large); // 这个不管它
heapify(a, large, j); // 这个? 递归调用而已
}
}
所以, 上面的方法可以重构成这样
int heapify2(int[] a, int i, int j) { // modify the return type to int
int left = i * 2 + 1;
int right = i * 2 + 2;
if (left > j) {
return 0; // 没有子树,比较次数为0
}
int times = 2; // added
int large = left;
if (right <= j && a[left] < a[right]) {
large = right;
}
if (a[i] < a[large]) {
swap(a, i, large);
times += heapify2(a, large, j); // modified
}
return times; // added
}
下面要删掉无关的代码, large 就是 left(因为和排序没关系) ,left 就是 i * 2 + 1
所以:
int heapify2(int[] a, int i, int j) {
// int left = i * 2 + 1;
// int right = i * 2 + 2;
if (i * 2 + 1 > j) {
return 0;
}
int times = 2;
int large = i * 2 + 1;
// if (right <= j && a[left] < a[right]) {
// large = right;
// }
// if (a[i] < a[large]) {
// swap(a, i, large);
times += heapify2(a, large, j);
// }
return times; // added
}
}
整理一下:
int heapify2(int[] a, int i, int j) {
if (i * 2 + 1 > j) {
return 0;
}
return 2 + heapify2(a, i * 2 + 1, j);
}
和 a 无关
int heapify2(int i, int j) {
if (i * 2 + 1 > j) {
return 0;
}
return 2 + heapify2(i * 2 + 1, j);
}
比较容易看出,以上heapify2可以优化为迭代版本, 预示着heapify 代码也可以使用迭代 代替 递归。
如果对n个数进行调整,此时 i = 0, j = n
int heapifyN(int n) {
return heapify2(0, n);
}
在算法笔记二中,我们有一个工具可以用来看看复杂度,现在试一下:)
往charts目录中加一个文件: HeapifyN.rb
module Charts
class HeapifyN
def name
'heapfy(n)'
end
def fun(x)
return nil unless x >= 0
x = x.to_i
heapfy(0, x);
end
def heapfy(i, j)
if i * 2 + 1 > j
return 0
end
return 2 + heapfy(i * 2 + 1, j)
end
end
end
运行,就能绘出如下图
绿的就是 heapify(n) , 蓝的是 log(x) 黄的是 log10(x)
所以 它的复杂度和 log(n) 相当的
下面是buildHeap, 它的代码是这样的:
void buildHeap(int[] a) {
int n = a.length;
for (int i = n / 2 - 1; i >= 0; --i) {
heapify(a, i, n - 1);
}
}
重构成求比较次数,差不多是这样:
int buildHeap2(int n) {
int times = 0;
for (int i = 0; i < n / 2; i++) {
times += heapify2(i, n - 1);
}
return times;
}
OK, 这个复杂度不会大于 nlog(n), 因为heapify2 是 log(n), 循环了 n / 2 次, 但是 是否为 nlog(n)呢?(因为有一半元素不需要 heaify, 而且每次heapify 的规模也不一样)
我们再来画画图:)
蓝线是 nlog(n), 黑线是 buildHeap。
书中经过数学推导,证明其复杂度是 O(n), 图中黑线很“直”,所以应该是线性的
还有最后一个heapSort, 这个是多少呢? 不过肯定比 buildHeap 要大,因为一开始就要buildHeap.
然后还要进行 n-1次heapify。
还是再画图吧:)
其实画buildHeap时就比较累了, 当横坐标为2000时,等了好几秒。 现在 heapSort 就更慢了, 横坐标为1000时也等了好久:) 不过可以对计算结果进行适当的缓存,就可很大提高计算的速度:)
- 大小: 4.6 KB
- 大小: 6.2 KB
- 大小: 8.5 KB
分享到:
相关推荐
麻省理工算法导论全套笔记 ,英文版,看好再下哦。
我做的算法导论读书笔记。请大家提供意见和建议,也欢迎大家一起交流。
算法导论上的堆排序c++源程序||学习分享
我做的算法导论读书笔记,这是第三个了。请大家提供意见和建议,也欢迎大家一起交流。 关于该系列读书笔记的详情和进展请看我的博客http://blog.csdn.net/PowerRock
算法导论读书笔记,整理别人的,不算抄袭吧。。
《算法导论》读书笔记_附录A习题解答 学习C C++ 资料
算法导论 学习笔记
从第二到第八章的总结
算法导论大作业:股票买卖最佳时期系列问题 南开大学 算法导论源码算法导论大作业:股票买卖最佳时期系列问题 南开大学 算法导论源码算法导论大作业:股票买卖最佳时期系列问题 南开大学 算法导论源码算法导论大作业...
参考《算法导论》这本书写的一个堆排序的代码,我个人是用Visual studio写的。只要一个积分哦
麻省理工的关于算法导论的笔记,英文版 希望对学习算法导论的朋友能有帮助
更多内容请关注http://blog.csdn.net/PowerRock/
算法导论 快速排序 堆排序 算法导论上的算法实现更加精简高效 代码可编译运行测试 加了测试用例 加了注释
山东大学软件学院算法导论课程的复习笔记。文件里面包含了五份笔记,涵盖BFS、DFS、SCC、Topological、MST、ShortestPath、maxflow。主要是对PPT的内容的整理概括。个人整理不易,其中的图片都是自己绘制的,就是...
实现算法导论中的堆排序,区别数组以0作为根,算法导论中的实现是以数组1作为根
算法导论课堂笔记。 英文版。 Word文档。
麻省理工学院算法导论_笔记 算法导论,学习计算机必备
自学算法导论中前几章,并自己写的排序算法源码包括gtest的测试用例。 详细介绍看我博客 http://blog.csdn.net/ceofit 一、选择法排序、冒泡排序、插入法排序 http://blog.csdn.net/ceofit/article/details/7397020 ...
包括麻省理工学院算法课的教材《算法导论》中英文版,麻省理工的课堂讲义,练习,以及课后答案,值得学习算法的学生研究。
算法导论讲义\算法导论讲义 算法导论讲义\算法导论讲义 算法导论讲义\算法导论讲义 MIT教师的课堂讲义 很有价值