代码

void swap(unsigned &x,unsigned &y)
{
    int t=x;
    x=y,y=t;
}

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();
    }

};

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();
}
	

评测结果