堆排序

2016-03-14  本文已影响44人  __小二杰
#define LeftChild(i) (2*(i)+1) //由于数组是从0开始的,因此儿子节点的索引要多加一个

 

void PercDown(int A[], int i, int N) //下滤,将堆顶的元素下滤到适当位置

{

   int Child;

   int Temp;

   for(Temp = A[i]; LeftChild(i) < N; i = Child)

   {

     Child = LeftChild(i);

     if(Child != N-1 && A[Child+1] > A[Child]) //选取儿子中值较大的一个

     {

       Child++;

     }

     if(Temp < A[Child]) //如果temp的值小,则将child上滤

     {

       A[i] = A[Child];

     }

     else //如果temp的值大于孩子的值,则退出for循环,temp就安放在此

       break;

   }

 A[i] = Temp;

}

 

void HeapSort(int A[], int N)

{

   int i;

   for(int i = N/2; i >= 0; --i) //对一个普通数组建立堆序性,堆顶的值最大

   {

     PercDown(A, i, N);

   }

   for(i = N-1; i>=0; --i) //将堆顶元素放到最后,最后一个元素放到堆顶,对除最后的那个元素外的//堆建立堆序性,这样就相当于删除了最大的元素,放到最后,知道删除所有元素则排序完成。

   {

     int temp;

     temp = A[0];

     A[0] = A[i];

     A[i] = temp;

     PercDown(A, 0, i);

   }

}
上一篇 下一篇

猜你喜欢

热点阅读