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

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

堆排序是利用堆进行排序的高效算法，其能实现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);
 }
}

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

本文永久更新链接地址：