这篇博客讨论一下堆排序。

 

    堆排序就是利用堆这种数据结构来实现排序，堆具有堆序性，最小堆的最小值一定在开头，最大堆的最大值也在开头，因此，我们可以利用堆来排序。

 

    我们选用最大堆来排序，首先在原来的数组上构建一个最大堆，因此数组的开头就是最大值，我们把这个最大值和堆的最后一个元素交换位置，同时堆的大小减一，再整理堆，如此循环，最后的结果就是排好序的数组。

 

  代码如下：

 

#include
     
      using namespace std;int A[13] = {81,94,11,96,12,35,17,95,28,58,41,75,15};#define LeftChild(i) (2 * (i) + 1)    //标号从0开始，因此左儿子在2i + 1处//最大堆，最大值在开头void PercDown (int A[],int i, int N){   int Child;   int Tmp;   for(Tmp = A[i]; LeftChild(i) < N; i = Child)   {      Child = LeftChild(i);	  if(Child != N-1 && A[Child + 1] > A[Child])  //寻找较大的儿子		  Child++;	  if(Tmp < A[Child])		  A[i] = A[Child];	  else 		  break;   }   A[i] = Tmp;}void Swap(int &a, int &b){   int c;  c = a;  a = b;  b = c;}void Heapsort (int A[], int N){   int i;   for(i = N / 2; i >= 0; i--)    //在数组上构建最大堆	   PercDown(A,i,N);   for(i = N - 1; i > 0; i--)   {      Swap(A[0],A[i]);   //开始排序，把最大值换到后面去	  PercDown(A,0,i);   //整理堆，剩下元素的最大值会回到开头   }}int main (){	Heapsort (A, 13);	for(int i = 0; i != 13; ++i)    {       cout << A[i] << "  ";    }    cout << endl;    return 0;}
     

　　堆排序相对来说还是比较快的排序方法。

 

    夜深了，，，

   

   推荐一首歌 《塘桥夜话》