基于数组的堆排序(二)

#include <stdio.h>

//下标x取到在数组中的位置
#define LEFT(x) ((x << 1) + 1)            
#define RIGHT(x) ((x + 1) << 1)
#define PARENT(x) (((x + 1) >> 1) - 1)

/*************************************************
函数名称:Swap
参 数:int num1,num2(两个整数)
功 能:交换两个整数
*************************************************/
void Swap(int & num1, int & num2)
{
    int temp;
    temp = num1;
    num1 = num2;
    num2 = temp;
}

/*************************************************
函数名称:MaxHeapify
参 数:Ary 数组
         nIndex 下标
         nHeapSize 堆的大小
功 能:使堆中的某个结点满足最大堆的要求()
         这里需要理解这里的某个结点,只是将相关的变动
         的地方设置明白,变动到根结点就是最大值了
**************************************************/
void MaxHeapify(int Ary[], int nIndex, int nHeapSize)
{
    int nL = LEFT(nIndex);    
    int nR = RIGHT(nIndex);    
    int nLargest;                //取到最大值的下标

    if (nL <= nHeapSize && Ary[nIndex] < Ary[nL])
    {
        nLargest = nL;
    }
    else
    {
        nLargest = nIndex;
    }
    
    if (nR <= nHeapSize && Ary[nLargest] < Ary[nR])
    {
        nLargest = nR;
    }
    if (nLargest != nIndex)
    {
        Swap(Ary[nLargest], Ary[nIndex]);
        //调整后可能仍然违反堆性质需要继续调整
        MaxHeapify(Ary, nLargest, nHeapSize);
    }
}

/*************************************************
函数名称:ShowAry
参 数:Ary 数组
         nCount 数组的大小
功 能:打印出数组中的元素
**************************************************/
void ShowAry(int Ary[], int nCount)
{
    for (int i = 0; i < nCount; i++)
    {
        printf("%5d",Ary[i]);
    }
    printf("\n");

}

/*************************************************
函数名称:BuildMaxHeap
参 数:Ary 数组
         nHeapSize 堆的大小
功 能:建立最大堆
**************************************************/
void BuildMaxHeap(int Ary[], int nHeapSize)
{
    for (int i = PARENT(nHeapSize); i >= 0; --i)
    {
        MaxHeapify(Ary, i, nHeapSize);
    }
}

/*************************************************
函数名称:HeapSort
参 数:Ary 数组
         nCount 数组的大小
功 能:对数组中的数据进行排序
**************************************************/
void HeapSort(int Ary[], int nCount)
{
    int nHeapSize = nCount - 1; 
    BuildMaxHeap(Ary, nHeapSize);

    for (int i = nHeapSize; i >= 1; --i)
    {
        Swap(Ary[0], Ary[i]);            //将最大值置于数组最后

        --nHeapSize;
        MaxHeapify(Ary, 0, nHeapSize);    //对其余的数组依旧进行堆排序

    }
}

int main()
{
    int Ary[] = {16,14,10,8,7,9,3,2,4,1,33};
    MaxHeapify(Ary, 0, sizeof(Ary)/sizeof(int));
    printf("%5d", Ary[0]);
    return 0;
}