最大堆(二叉)排序分几个步骤：

1.maxheap(),维护最大堆的性质，即节点的值大于子节点的值，时间复杂度O(lgn)

2.bulid_max_heap(),从无序数组中构造最大堆，时间复杂度O(n)

3.heap_sort(),对无序数组进行排序，时间复杂度O(nlgn)

代码有注释

1 #include 
     
       2 using std::cout; 3  4 void max_heapify(int *a,int len,int i) 5 { 6     //以0开始的数组，左孩子为2i+1，右孩子为2i+2 7     int l=2*i+1,r=2*i+2,largest; 8  9     //选出最大值，记录其指针到largest10     if(l
      
       a[i])largest=l;11     else largest=i;12     if(r
       
        a[largest])largest=r;13     if(largest!=i)14     {15         {
   int temp=a[i];a[i]=a[largest];a[largest]=temp;}16 17         //节点有变化，所以要对有变化的节点进行heapify18         //因为heapify是在其子节点heapify之后进行的19         max_heapify(a,len,largest);20     }21 }22 void bulid_max_heap(int *a,int len)23 {24     //len/2,len/2+1...是叶节点，不用heapify25     for(int i=len/2;i>=0;i--)max_heapify(a,len,i);26 }27 void heapsort(int *a,int len)28 {29     int temp;30     bulid_max_heap(a,len);31     for(int i=len-1;i>=1;i--)32     {33         //将堆顶（最大值）放到数组尾34         {temp=a[0];a[0]=a[i];a[i]=temp;}35         36         //数组长度-1，heapify根节点，又成为了最大堆37         len--;38         max_heapify(a,len,0);39     }40 }41 42 43 int main()44 {45     int a[]={
   12,8564,445,56,8,54,6,4,5,4};46     heapsort(a,10);47     for(int i=0;i<10;i++)cout<
        
         <<"  ";48 49     return 0;50 }