代码

#include <algorithm>
using namespace std;

#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)

struct Heap                 //小根堆
{
    unsigned int a[10005];
    int tot;

    #define LE(x) ((x)<<1)
    #define RT(x) (((x)<<1)+1)
    #define DAD(x) ((x)>>1)

    Heap() {tot=0;}

    void modify(int x)
    {
        int mi;

        if(LE(x)>tot || x>tot) return;
        if(RT(x)>tot) mi=LE(x);
        
        else if(a[LE(x)]<a[RT(x)]) mi=LE(x);
        else mi=RT(x);

        if(a[x]>a[mi]) swap(a[x],a[mi]);
    }

    void ins(int x)
    {
        tot++;
        a[tot]=x;
        for(x=DAD(tot);x;x=DAD(x))
            modify(x);
    }

    int top()
    {
        return a[1];
    }

    void repair()
    {
        int mi,x;

        for(x=1;x<=tot;x=mi)
        {
            if(LE(x)>tot) break;
            if(RT(x)>tot) mi=LE(x);
            
            else if(a[LE(x)]<a[RT(x)]) mi=LE(x);
            else mi=RT(x);

            if(a[x]>a[mi]) swap(a[x],a[mi]);
            else break;
        }
    }

    void pop()
    {
        swap(a[1],a[tot]);
        tot--;

        repair();
    }

    void debug()
    {
        int i;
        printf("[%d] ",tot);
        for(i=1;i<=tot;i++) printf("%d ",a[i]);
        puts("");
    }
};

Heap s;

void sort(unsigned *a, int n) {
	int i;

    for(i=0;i<n;i++)
        s.ins(a[i]);
    for(i=0;i<n;i++)
        a[i]=s.top(),s.pop();
}

评测结果