堆排序(Heap Sort)是一种效率较高的选择排序算法. 它是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它通过堆来进行选择数据.
有关堆还不了解的朋友可以先移步这篇文章:【数据结构】什么是堆?
它的基本思想是:
算法动图演示: 1.向下调整建堆 逻辑结构:
物理结构:
2.堆排序(升序) 逻辑结构:
物理结构:
算法实现步骤:(以升序为例)
搞清实现步骤后,代码的实现就比较简单了,堆排序代码如下:
//交换函数
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//向下调整建堆
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;//默认是左孩子
while (child < n)//孩子走到叶子就可以停止了
{
//选出左右孩子中大的那个
if (child + 1 < n && a[child + 1] > a[child])//如果右孩子存在且大于左孩子
{
child++;
}
//向下调整重新使堆有序
if (a[child] > a[parent])//建大堆
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//堆排序(升序
void HeapSort(int* a, int n)
{
for (int i = (n - 1 - 1) / 2; i >= 0; i--)//先向下调整建堆
{
AdjustDown(a, n, i);
}
int end = n - 1;
while (end > 0)
{
Swap(&a[end], &a[0]);//将堆顶元素和待排区间的最后一个元素交换
AdjustDown(a, end, 0);
end--;
}
}
堆排序方法对数据数较少的序列排序的效果并不很好,但对n较大的序列还是很有效的. 因为它的运行时间主要耗费在建初始堆和调整建堆时进行的反复"筛选"上. 对深度为k的堆,筛选算法中进行的关键字比较次数至多为2(k-1)次,则在建含n个元素,深度为h的堆时,总共进行的关键字比较次数不超过4n.又因为n个结点的完全二叉树的深度为
,则调整建新堆时调用向下建堆函数过程n-1次,总共进行的比较次数不超过下式:
因此,堆排序在最坏的情况下,其时间复杂度也为O(nlogn),这是相对快排,堆排的最大优点.