给出数组A[1...n],我们可以将其中的元素用下面的方法以非降序有效地排序。
首先将A变换成堆,并使其具有这样的性质:每个元素的键值是该元素本身,即key(A[i])=A[i],1 ≤ i ≤ n。
转换成堆之后,由于A中各项的最大值存储在A[1]中,可以将A[1]和A[n]交换,使得A[n]是数组中的最大元素。这时A[1]中的元素可能小于存放在它的一个子节点中的元素,于是用过程Sift-down将A[1...n-1]转换成堆。接下来将A[1]和A[n-1]交换,并调整数组A[1...n-2]成为堆。交换元素和调整堆的过程一直重复,直到堆的大小变成1为止,这时,A[1]是最小的。
过程 HeapSort
输入 n个元素的数组A[1...n]
输出 以非降序排列的数组A
算法描述
for j ← n downto 2
互换 A[1]和A[j]
Sift-down(A[1...j-1], 1)
end for
注意这里算法描述的数组的索引都是1...n,而不是大家习惯的0...n-1。
创建堆需要Θ(n)的时间,Sift-down运算需要O(log n)时间,并且要重复n-1次,也就是用该算法给n个元素排序需要时间O(n log n)。
// heap[0]用来存储数组中堆数据的长度,堆数据heap[1]...heap[heapLength]
// 所以数组的实际长度是heapLength+1,我们只对从数组索引为1开始的heapLength个数据进行操作
void siftDown(int* heap, int siftDownTo, int index)
{
if (index < 1 || index * 2 > siftDownTo)
return;
bool done = false;
while(!done && index * 2 <= siftDownTo)
{
index *= 2;
if (index + 1 <= siftDownTo && heap[index + 1] > heap[index])
index += 1;
if (heap[index] > heap[index / 2])
{
int temp = heap[index];
heap[index] = heap[index / 2];
heap[index / 2] = temp;
}
else
{
done = true;
}
}
}
void heapSort(int* heap)
{
if (heap == NULL)
return;
int heapLength = heap[0];
int temp = 0;
for (int i = heapLength; i >= 2; i--)
{
temp = heap[1];
heap[1] = heap[i];
heap[i] = temp;
siftDown(heap, i - 1, 1);
}
}
我使用的数组是这样定义的:
const int HEAP_LENGH = 10;
int heap[HEAP_LENGH + 1] = { HEAP_LENGH, 20, 11, 9, 10, 5, 4, 5, 3, 7, 3 };
heapSort(heap);
更多内容请参考:
算法 之 堆 - 简介
算法 之 堆 - Sift-up和Sift-down
算法 之 堆 - 插入和删除
算法 之 堆 - 创建堆
分享到:
相关推荐
最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
常用的排序算法--堆排序,通过创建堆的方法进行排序
算法-理论基础- 排序- 堆排序(包含源程序).rar
排序算法:排序算法汇总--各类排序算法 冒泡,选择,插入,快排,归并,堆排
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
经典排序算法 - 堆排序Heap sort序 经典排序算法 - 地精排序Gnome Sort 经典排序算法 - 奇偶排序Odd-even sort 经典排序算法 - 梳排序Comb sort 经典排序算法 - 耐心排序Patience Sorting 经典排序算法 - 珠...
该资源提供了Java中实现堆排序的全面指南。文档中涵盖了堆排序的基本概念,包括如何对数组进行排序以及如何在Java中实现堆排序。此外,文档还包括一个逐步指南,介绍了如何在Java中实现堆排序,包括详细的代码示例和...
该资源是一个入门级别的C++算法练习,旨在帮助读者学习和理解堆排序算法。文档中包含了堆排序的基本原理和实现方法,并提供了详细的代码示例和解析。 通过学习和完成这个练习,读者将能够掌握堆排序算法的思想和...
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
详解Java常用排序算法-堆排序
简单的堆排序算法:以定长数组为例,动态数组等可以以此类推
此文件为数据结构中的九种排序算法,包含一些排序方法的过程,其九种排序包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,基数排序!
c语言实现堆排序。代码实现的是建立大根堆
自己看书时写的排序算法:堆排序 CPP文件
各类排序算法整理--C语言描述--本人编写 排序算法种类有: 冒泡 快速排序 堆排序 希尔排序 插入排序 选择排序 二路归并排序
排序算法之堆排序算法,用C++语言实现堆排序算法
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
// 堆排序 #include typedef int InfoType; // 定义其它数据项的类型 #include "compare.h" #include "sort.h" typedef SqList HeapType; // 堆采用顺序表存储表示 void HeapAdjust(HeapType &H,int s,int m) // ...
排序算法中的堆排序的代码,其他排序算法的代码可以私信我~