堆排序相对冒泡排序、选择排序效率很高，不再是O（n^2）.


假若将一个序列升序排序好，那么我们来考虑最大堆还是最小堆来排序。假若是最小堆的话，堆的顶端必定是堆中的最小值，这样貌似可以。但是，如果是它的（一边或）子树左子树的节点数据值大于（一边或）右子树的节点数据值，直接打印肯定是错误的，而且对于此时的堆我们也无法操控来调整好正确的顺序了。


那我们换成最大堆来实现升序想，当我们把序列调整成为最大堆后，最大堆顶端的数据值是最大的，然后我们将这个最大值与堆的最后一个叶子节点值来进行交换，再将交换后的顶端值进行调整，换到合适的位置处……重复这样的工作，注意：进行第2次交换就要将顶端元素值与倒数第2个节点元素值交换了，且调整顶端元素位置也不能一直调整到size-1处。（因为：size-1处的值已经是最大）


代码如下：

#define_CRT_SECURE_NO_WARNINGS1#include<iostream>usingnamespacestd;#include<assert.h>voidAdjustDown(int*a,intparent,intsize){intchild=2*parent+1;while(child<size){if(child+1<size&&a[child]<a[child+1]){++child;}if(a[child]>a[parent]){swap(a[child],a[parent]);parent=child;child=2*parent+1;}else{break;}}}voidPrint(int*a,intsize){cout<<"升序序列为："<<endl;for(inti=0;i<size;i++){cout<<a[i]<<"";}cout<<endl;}voidHeapSort(int*a,intsize){assert(a);//建成最大堆for(inti=(size-2)/2;i>=0;i--){AdjustDown(a,i,size);}//交换顺序for(inti=0;i<size;i++){swap(a[0],a[size-i-1]);AdjustDown(a,0,size-i-1);}}voidTest(){intarr[]={12,2,10,4,6,8,54,67,100,34,678,25,178};intsize=sizeof(arr)/sizeof(arr[0]);HeapSort(arr,size);Print(arr,size);}intmain(){Test();system("pause");return0;}


时间复杂度：

（n-2）/2*lgn+n*(1+lgn)--->O(n).