算法----堆排序(heap sort)
浏览数：18 /
时间：2015年06月08日
堆排序是利用堆进行排序的高效算法，其能实现O(NlogN)的排序时间复杂度，具体算法分析可以点击堆排序算法时间复杂度分析。
算法实现：
调整堆：
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);
}
}上述是堆排序的简单介绍。具体的优化以及应用稍后奉上。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
