heapsort.h

随机产生个整数n=100

template<class T>
void FilterDown(T a[],int i,int N,int&KCN,int&RMN)
{
    int child=2*i+1 ;
    T temp=a[i];
    while(child<N)
    {
        if(child<N-1&&a[child]<a[child+1])child++;
        if(++KCN&&temp>=a[child])break ;
        //不需调整，结束调整
        a[i]=a[child];
        RMN++;
        i=child ;
        child=2*i+1 ;
    }
    a[i]=temp ;
    RMN++;
}
template<class T>
void HeapSort(T a[],int N,int&KCN,int&RMN)
{
    int i ;
    for(i=(N-2)/2;i>=0;i--)FilterDown<T>(a,i,N,KCN,RMN);
    //生成最大堆
    for(i=N-1;i>0;i--)
    {
        swap(a[0],a[i]);
        RMN+=3 ;
        FilterDown(a,0,i,KCN,RMN);
    }
}