编辑代码

#include <stdlib.h>
#include <iostream>

using std::cout;
using std::endl;

#define N 10
#define M 100
#define SWAP(x,y) {int tmp=x; x=y; y=tmp;}

void print(int *a)
{
    for(int i=0; i<N; ++i)
    {
        printf("%3d", a[i]);
    }
    printf("\n");
}
void adjustMaxHeap(int *a, int pos, int len)
{
    int dad = pos;
    //son表示挑战的孩子下标
    int son = 2*dad+1;
    while(son < len)
    {
        if(son+1 < len && a[son] < a[son+1])
        {
            //右孩子存在且大于左孩子
            son = son+1;
        }
        if(a[dad] < a[son])
        {
            //父亲结点与孩子结点交换，向下继续循环
            SWAP(a[dad], a[son]);
            dad = son;
            son = 2 * dad + 1;
        }
        else
        {
            //如果不交换，循环终止
            break;
        }
    }
}
void heapSort(int *a)
{
    //N/2-1 表示最后一个父亲结点下标
    for(int i=N/2-1; i>=0; --i)
    {
        //i表示要调整树的下标
        adjustMaxHeap(a, i, N);
    }
    SWAP(a[0], a[N-1]);
    for(int i=N-1; i>1; --i)
    {
        //i表示堆的规模
        adjustMaxHeap(a, 0, i);
        SWAP(a[0], a[i-1]);
    }
}
int main()
{
    srand(time(NULL));
    int *a = (int*)malloc(sizeof(int)*N);
    
    for(int i=0; i<N; ++i)
    {
        a[i] = rand() % M;
    }
    print(a);
    
    heapSort(a);
    
    print(a);
    
    free(a);
    return 0;
}