返回信息流今天看《算法导论》堆排序那章 看了很久没看懂
找一个完整的可编译通过的代码
网上找的都编译不过
求高人指点
这是一条镜像帖。来源：北邮人论坛 / cpp / #44761同步于 2010/10/13
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
【求助】关于堆排序
huangzz
2010/10/13镜像同步3 回复
订阅后，新回复会通过你的通知中心匿名送达。
3 条回复
#include <stdio.h>
int A[10] = {1, 3, 6, 9, 8, 2, 5, 4, 7, 10};
/*
* MaxHeapify, O(h), h = O(lgn)
* make the subtree rooted at i, compile to max
* heap property
*/
void MaxHeapify(int* A, int size, int i)
{
int left, right;
int largest;
int tmp;
left = (i<<1) + 1;
right = left + 1;
if ( (left < size) && (A[left] > A[i]) )
largest = left;
else
largest = i;
if ( (right < size) && (A[right] > A[largest]) )
largest = right;
if (largest != i)
{
tmp = A[largest];
A[largest] = A[i];
A[i] = tmp;
MaxHeapify(A, size, largest);
}
}
/*
* BuildMaxHeap, O(n) algorithm
* Make the array A, length of len, compile to a max heap
*/
void BuildMaxHeap(int* A, int size)
{
int start = (size >> 1) - 1;
for(; start>=0; start--)
{
MaxHeapify(A, size, start);
}
}
/*
* HeapSort
* A O(nlgn) in place sorting algorithm
*/
void HeapSort(int* A, int len)
{
int i, tmp;
BuildMaxHeap(A, len);
for(i=len; i>=2; i--)
{
tmp = A[0]; A[0] = A[len-1]; A[len-1] = tmp;
len--;
MaxHeapify(A, len, 0);
}
}
int main()
{
HeapSort(A, 10);
return 0;
}