算法----堆排序(heap sort)

算法实现：

调整堆：

?void sort::sink(int* a, const int root, const int end)
{
?int i=root;
?while(2*i +1? <= end)
?{
? int k = 2*i+1;
? if(k+1<=end && a[k]? ?k++;
? if(a[k] < a[i])
? ?break;
? swap(a,k,i);
? i=k;
?}
}

堆排序：

void sort::heap_sort(int* a, const int n)
{
?for(int i=(n-1)/2; i>=0; i--)
? sink(a,i,n-1);
?for(int i=n-1; i>0;)
?{
? swap(a,0,i);
? i--;
? sink(a,0,i);
?}
}

上述是堆排序的简单介绍。具体的优化以及应用稍后奉上。