堆排Heap Sort

[c language=”++”]
#define LeftChild(i) (2*(i)+1)
void PercDown(vector<int>&num, int i, int n)
{
int child;
int tmp;
for (tmp = num[i]; LeftChild(i) < n; i = child)
{
child = LeftChild(i);
//如果右儿子存在，且值大于左儿子，则取右儿子
if (child != n – 1 && num[child + 1] > num[child])
child++;
//如果父亲的值小于儿子，则继续下沉
if (tmp < num[child])
num[i] = num[child];
else//否则，退出循环
break;
}
num[i] = tmp;
}
//先建立堆
for (int i = n / 2; i >= 0; i–)
PercDown(numCopy, i, n);
for (int i = n – 1; i>0; i–)
{//进行堆排
swap(numCopy[0], numCopy[i]);
PercDown(numCopy, 0, i);
}

[/c]