2014-05-31|1366阅|作者：空心|举报 摘要:template void Sort::HeapSort(T* array, int size) { int lastP = size / 2; //从最后一个有孩子的结点开始建初始堆 for(int i = lastP - 1; i >= 0; i
template
void Sort::HeapSort(T* array, int size)
{
int lastP = size / 2;
//从最后一个有孩子的结点开始建初始堆
for(int i = lastP - 1; i >= 0; i--)
{
HeapAjust(array, i, size);
}
int j = size;
//将堆顶元素和无序区间的最后一个元素交换，再调整堆
while(j > 0)
{
Swap(array, 0, j - 1);
j--;
HeapAjust(array, 0, j);
}
}
//调整堆
template
void Sort::HeapAjust(T *array, int toAjust, int size)
{
int pos = toAjust;
while((pos * 2 + 1) < size)
{
int lChild = pos * 2 + 1;
if(array[lChild] > array[pos])
{
pos = lChild;//左孩子大
}
int rChild = lChild + 1;
if(rChild < size && array[rChild] > array[pos])
{
pos = rChild;//右孩子更大
}
if(pos != toAjust) //父结点比其中一个孩子小
{
Swap(array, toAjust, pos);
toAjust = pos;
}
else
{
break;
}
}
}
