堆排序很有意思。作为排序算法来讲,它和快速排序都是O(nlogn)的时间复杂度,都是就地排序,都是采用递归。两者差不多,既生瑜,何生亮?不过堆是一种很有用的数据结构,通过堆排序算法,可以学习堆这种数据结构,以后可能用得上。
堆排序算法思路很简单:
第一步,构建一个堆;
第二步,取出堆顶;
第三步,如果排序没完成,重复第一步。
堆分为最大堆和最小堆,表示堆的顶点元素是整个序列的最大值还是最小值。通常堆用数组来存储,数组的第一个元素表示堆顶。
堆排序代码如下:
void HeapSort (int Array[], int iNum) // iNum表示数组元素个数
{
if (iNum <= 1) // 防御性代码
return;
BuildMaxHeap (Array, iNum); // 建立最大堆
for (int i=iNum-1; i>0; i--) // 从数组尾部开始遍历,不断取出堆顶元素,放到数组尾端,并重新建立堆
{
int iTemp =Array[i]; // 取出数组尾部元素,并与堆顶元素交换。
Array[i] = Array[0]; //此时堆顶元素是最大元素(最大堆),已经被放在了合适的位置上——数组尾部,数组元素期望由小到大排列
Array[0] = iTemp; // 原数组尾部元素被临时放到堆顶
MaxHeapfy (0, i); // 调整数组元素,使之满足堆的条件
}
}
看起来很简单,只不过两个关键的函数没说,一个是堆调整函数MaxHeapfy,一个是建堆函数BuildMaxHeap。其实建堆函数也用到了堆调整函数。好,下文就说。
分享到:
相关推荐
1.对冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较; 2.待排序表的表长不小于100,表中数据随机产生,至少用5组不同的数据作比较,比较指标有:关键字比较次数和关键字移动次数...
包括基本算法分析原理,基本数据结构、抽象数据结构、递归和树等数据结构知识,选择排序、插入排序、冒泡排序、希尔排序、快速排序方法、归并和归并排序方法、优先队列与堆排序方法、基数排序方法以及特殊用途的排序...
包括基本算法分析原理,基本数据结构、抽象数据结构、递归和树等数据结构知识,选择排序、插入排序、冒泡排序、希尔排序、快速排序方法、归并和归并排序方法、优先队列与堆排序方法、基数排序方法以及特殊用途的排序...
包括基本算法分析原理,基本数据结构、抽象数据结构、递归和树等数据结构知识,选择排序、插入排序、冒泡排序、希尔排序、快速排序方法、归并和归并排序方法、优先队列与堆排序方法、基数排序方法以及特殊用途的排序...
包括基本算法分析原理,基本数据结构、抽象数据结构、递归和树等数据结构知识,选择排序、插入排序、冒泡排序、希尔排序、快速排序方法、归并和归并排序方法、优先队列与堆排序方法、基数排序方法以及特殊用途的排序...
本份资源包含本科数据结构各种排序代码,如快排,堆排等代码实现(C/C++),同时本代码可直接进行运行查看结果,欢迎各位朋友下载.
去做经过的时间,gnuplot,graphviz 堆排序 vs 合并排序 vs 快速排序优先队列桶排序订单统计开放散列霍夫曼编码Dijkstra 算法矩阵链乘法最长公共序列最近的点对收费公路重建张开的树其他待办事项包括覆盖代码贪心...
MATLAB代码设计路径 openWHURS 关于本仓库 本仓库提供武汉大学遥感信息工程学院(School of ...一个采用堆排序优化的最短路径程序。By Xiang Zheng By Wei Yu By Chen Dingzhi By Chen Dingzhi & Ma
7.5 堆排序 7.6 归并排序 7.7 快速排序 7.7.1 选取枢纽元 7.7.2 分割策略 7.7.3 小数组 7.7.4 实际的快速排序例程 7.7.5 快速排序的分析 7.7.6 选择问题的线性...
作 者:严蔚敏 李冬梅 吴伟民 出版时间:2011-2-1 0:00:00 ...8.4.2 堆排序 221 8.5 归并排序 226 8.6 基数排序 228 8.6.1 多关键字的排序 228 8.6.2 链式基数排序 228 8.7 小结 232 习题 233
书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找树算法、k-d树和配对堆等。本书适合作为计算机相关专业本科生的数据结构课程和研究生算法分析...
《数据结构——用C语言描述》以C语言为程序设计语言,采用系列式的叙述方式,引导读者循序渐进地掌握数组、链接表、栈和队列、树与森林、图和堆等不同的数据结构,并系统地介绍了查找和排序的各种实现方法。...
使用的参考材料:算法设计手册算法简介阶段I: 首先阅读提供的以下1-4种基本计算机科学材料。 这是一个基本的在线图书馆,... 基本类型数组弦乐链表堆栈和队列第三阶段: 二叉树堆排序正在搜寻哈希表二叉搜索树一元树
移除两章很少讲授的内容:二项堆和排序网络 修订了动态规划和贪心算法相关内容 流网络相关材料现在基于边上的全部流 由于关于矩阵基础和Strassen算法的材料移到了其他章 矩阵运算这一章的内容所占篇幅更小 修改...
书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找树算法、k-d树和配对堆等。《数据结构与算法分析:C++描述(第3版)》适合作为计算机相关专业本科...
书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找树算法、k-d树和配对堆等。《数据结构与算法分析:C++描述(第3版)》适合作为计算机相关专业本科...
书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找树算法、k-d树和配对堆等。《数据结构与算法分析:C++描述(第3版)》适合作为计算机相关专业本科...
书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找树算法、k-d树和配对堆等。《数据结构与算法分析:C++描述(第3版)》适合作为计算机相关专业本科...