前一章的“概率分析与随机算法”实在伤脑子,好在看过去了,现在正在看的是排序部分;
堆排序,这次说的是最大推排序(和最小堆原理也是相同的,最小堆实现),和原文中的思路也是一样的,后序有补充也会贴出来的;
最大堆...即是父节点的值大于孩子的值,若不满足条件,则经过调节使其满足条件:
维护堆:
书本中的伪码:
思想则是访问父节点,若是存在孩子节点的值大于父节点的值,则将最大的孩子节点的值与父节点进行交换,为了避免交换后的节点继续不满足条件,再次调用函数,使其满足条件,如对以下节点(不清晰部分为4):
其中父节点3,4,5皆满足条件,到2父节点时,不满足最大堆,即进行调节:
此时则发现节点4又不满足条件了,继续调节:
调节的过程就是这样;
建堆:
我们知道,当用数组来存储n个元素的堆时,叶子节点的下标是[n / 2] + 1,[n / 2] + 2......n。如上中10个元素,6之后即为叶子节点;
这时建堆即可:
由n / 2开始向第一个元素进行建堆;
堆排序:
先构建一个最大堆,最后不断的将根节点提取出来,同时不断调节余下的节点保证是最大堆;
贴下代码:
#include <iostream>
#include <cstdlib>
using namespace std;
void MaxHeapIfy(int A[], int length, int i) //维护
{
int left = i * 2; //节点i的左孩子
int right = i * 2 + 1; //节点i的右孩子节点
int largest = i; //默认父节点
if (left <= length && A[largest] < A[left]) //左孩子比父节点大
{
largest = left;
}
if (right <= length && A[largest] < A[right]) //右孩子最大
{
largest = right;
}
if (i != largest) //最大值不是父节点
{
int temp = A[largest]; //exchange
A[largest] = A[i];
A[i] = temp;
MaxHeapIfy(A, length, largest); //继续维护
}
}
void BuildMaxHeap(int A[], int length) //建堆
{
for (int i = length / 2; i >= 1; i--)
{
MaxHeapIfy(A, length, i);
}
}
void HeapSort(int A[], int length) //堆排
{
int temp;
BuildMaxHeap(A, length); //建堆
/*
cout<<"建堆情况:"; //
for(int i = 1; i <= length; i++)
cout<<A[i]<<" ";
cout<<endl;
*/
for(int i = length; i >= 2;)
{
temp = A[i]; //交换堆的第一个元素和堆的最后一个元素
A[i] = A[1];
A[1] = temp;
i--; //堆的大小减一
MaxHeapIfy(A, i, 1); //调堆
}
}
int main()
{
int A[] = {0, 4, 1, 23, 3, 2, 16, 9, 10, 14, 8, 7}; //0只做填充,填充A[0]
/*int* A = new int[1001];
A[0] = 0;
for(int i = 1; i <= 1000; i++)
A[i] = rand()%10000 + 1;*/
int length = sizeof(A) / sizeof(int); //
//int length = 1001;
HeapSort(A, length - 1);
for(int i = 1; i < length; i++) //cout
cout<<A[i]<<" ";
cout<<endl;
return 0;
}
ps:按照书中伪码写成,元素由1开始,故数组中第一位A[0]为填充,并不算在排序中。
下一篇最大堆进阶即是将元素开始修改为下标0,最小堆同样实现;
o(∩_∩)o
分享到:
相关推荐
算法导论上的堆排序c++源程序||学习分享
ps:按照书中伪码写成,元素由1开始,故数组中第一位A[0]为填充,并不算在排序中。 for(int i = length; i >= 2;) { temp = A[i]; //交换堆的第一个元素和堆的最后一个元素 A[i] = A[1]; A[1] = temp; i--; //...
参考《算法导论》这本书写的一个堆排序的代码,我个人是用Visual studio写的。只要一个积分哦
实现算法导论中的堆排序,区别数组以0作为根,算法导论中的实现是以数组1作为根
上个资源的有效排序下标是由1开始的,0只做了填充作用,这次则由下标0为根节点: for(int i = length; i >= 1;) //最后一个肯定是最小的 { temp = A[i]; //交换堆的第一个元素和堆的最后一个元素 A[i] = A[0]; ...
堆排序的源程序--编译、运行成功的。 其基本算法思想参照《算法导论》。 有点编译器需去掉-system("pause");
算法导论上堆排序算法的vc6.0下的Test实例。
php堆排序(算法导论)
根据算法导论第六章实现的堆排序
自学算法导论中前几章,并自己写的排序算法源码包括gtest的测试用例。 详细介绍看我博客 http://blog.csdn.net/ceofit 一、选择法排序、冒泡排序、插入法排序 http://blog.csdn.net/ceofit/article/details/7397020 ...
算法导论 快速排序 堆排序 算法导论上的算法实现更加精简高效 代码可编译运行测试 加了测试用例 加了注释
主要是对算法导论中堆排序的实现
算法导论中第二章所有排序的自己模拟,快速排序,堆排序,计数排序,最大最小数,选择第n个数等等
算法导论第三版第六章内容,作者使用C#与C++两种编程语言实现
《算法导论(原书第3版)》选材经典、内容丰富、结构合理、逻辑清晰,对本科生的数据结构课程和研究生的算法课程都是非常实用的教材,在it专业人员的职业生涯中,本书也是一本案头必备的参考书或工程实践手册。...
第六章 堆排序(Heapsort) 第七章 快速排序(Quicksort) 第八章 线性时间中的排序(Sorting in Linear Time) 第九章 中值与顺序统计(Medians and Order Statistics) 第三部分(Part III) 数据结构...
请参考算法导论第三版英文版Introduction to Algorithms 3rd Edition,本程序为第一章到第八章重要...堆排序 快速排序(2中分割方法) 随机化快速排序 TAIL-RECURSIVE-QUICKSORT Counting sort Radix sort 二分法搜索
排序算法(插入、选择、归并、冒泡、堆排序)实现代码C++ ----根据《算法导论》中的伪代码,自己写的C++代码实现;
第六章 堆排序(Heapsort) 第七章快速排序(Quicksort) 第八章 线性时间中的排序(Sorting in Linear Time) 第九章 中值与顺序统计(Medians and Order Statistics) 第三部分(Part III) 数据结构(Data ...
算法导论之堆排序,C语言实现版