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

堆排序是利用堆進行排序的高效算法，其能實現O(NlogN)的排序時間復雜度，具體算法分析可以點擊堆排序算法時間復雜度分析。 http://www.linuxidc.com/Linux/2014-11/109819.htm

算法實現：

調整堆：

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]<a[k+1])
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);
}
}

上述是堆排序的簡單介紹。具體的優化以及應用稍後奉上。