排序算法总结之堆排序

堆排序算是选择排序，即按照最小堆的方式，一个一个弹出来，不过这样子需要额外的数组来存放弹出来的数据。浙江大学陈越老师的方法，不需要额外的数组，如下

利用数组的方式建立一个最大堆

它的工作方式是：每次把最大堆的根节点和下标最大的结点（不一定是数值最小）交换，这样下标最大的结点即为最大值，如图所示，a和b交换，a在根节点而b交换到了堆伟。然后把堆的规模减1，如图即把下边为3的结点断了与这个堆的联系。这样最大值就已经放在了排序数组中它应该在的位置。下一次交换之前先进行下滤，即让堆重新变为最大堆再次进行交换，一次类推。具体实现代码如下

void Swap( ElementType *a, ElementType *b )
{
     ElementType t = *a; *a = *b; *b = t;
}

void PercDown( ElementType A[], int p, int N )
{ /* 改编代码4.24的PercDown( MaxHeap H, int p )    */
  /* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */
    int Parent, Child;
    ElementType X;

    X = A[p]; /* 取出根结点存放的值 */
    for( Parent=p; (Parent*2+1)<N; Parent=Child ) {
        Child = Parent * 2 + 1;
        if( (Child!=N-1) && (A[Child]<A[Child+1]) )
            Child++;  /* Child指向左右子结点的较大者 */
        if( X >= A[Child] ) break; /* 找到了合适位置也可能一次也不需要交换 */
        else  /* 下滤X */
            A[Parent] = A[Child];
    }
    A[Parent] = X;
}

void HeapSort( ElementType A[], int N ) 
{ /* 堆排序 */
     int i;

     for ( i=N/2-1; i>=0; i-- )/* 建立最大堆 */
         PercDown( A, i, N );

     for ( i=N-1; i>0; i-- ) {//i=N-1因为是从小标0开始的
         /* 删除最大堆顶 */
         Swap( &A[0], &A[i] ); /* 见代码7.1 */
         PercDown( A, 0, i );//这里知道0结点不是最大值即对0结点下滤
     }
}