quicksort.h

来自「随机产生个整数n=100」· C头文件 代码 · 共 34 行

template<class T>
int Partition(T a[],int left,int right,int&KCN,int&RMN)
{
    int pivotpos=left ;
    T pivot=a[left];
    //枢轴
    for(int i=left+1;i<=right;i++)
    if(++KCN&&a[i]<pivot&&++pivotpos!=i)
    {
        swap(a[i],a[pivotpos]);
        RMN+=3 ;
    }
    swap(a[left],a[pivotpos]);
    RMN+=3 ;
    return pivotpos ;
}
template<class T>
void QSRecurve(T a[],int left,int right,int&KCN,int&RMN)
{
    if(left<right)
    {
        int pivotpos=Partition<T>(a,left,right,KCN,RMN);
        QSRecurve<T>(a,left,pivotpos-1,KCN,RMN);
        QSRecurve<T>(a,pivotpos+1,right,KCN,RMN);
    }
}
template<class T>
void QuickSort(T a[],int N,int&KCN,int&RMN)
{
    KCN=0 ;
    RMN=0 ;
    QSRecurve<T>(a,0,N-1,KCN,RMN);
}