快速排序不正确的结果

debugcn 发表于 Dev

用户8401

我有这个要解决的快速排序代码。我在分区中更改了此代码。尝试选择枢轴元素作为数组的中位数。但是仍然不能给我正确的输出。在这里，我动态创建了四种类型的数组，并尝试对它们进行排序。快速排序应用了四次。

int counter=0, comparison=0;
void QUICKSORT(int *,int,int);
int PARTITION(int * ,int,int);
int values(float l);

int main(){

    int i,n,q;
    cout<<"Enter number of elements:";
    cin>>n;
    int* a = new int[ n ];
    for(int p=1;p<=n;p++)
    {
        q = rand() % (n*100) ;
        a[p]=q;
    }
    cout<<"\nThe elements od the original array are:\n\n";
    for(i=1;i<=n;i++)
        cout<<a[i]<<"  ";
    clock_t tStart = clock();
    QUICKSORT(a,1,n);
    cout<<"\nThe elements of the sorted array are:\n\n";
    for(i=1;i<=n;i++)
        cout<<a[i]<<"  ";


}


// function for the generation of random poisson values. This function is called as many times
// as the array size decided by the user

int values(float l)
{

    for (int i=0;i<1000;i++)
    {
    float L=exp(-l);
    float k=0;
    float p=1;
    //begin while
    do{
    k=k+1;
    double u = rand() / (double)RAND_MAX;
    p=p*u;

    }   while (p>L);
    return k-1;
    }
}


//}
void QUICKSORT(int *a,int p,int r){
    int q;
    if(p<r){
        q=PARTITION(a,p,r);
        QUICKSORT(a,p,q-1);
        QUICKSORT(a,q+1,r);
    }
}
int PARTITION(int *a,int p,int r){
    counter++;
//    cout<<" first a " <<a[p]<<endl;
//    cout<<" second a : "<<a[r-1]<<endl;
    int x=(a[r]+a[p])/2;
    //int x=a[r];
    int i = p-1,temp,j;
    for(j=p;j<=r-1;j++){
        if(a[j]<=x){
            i=i+1;
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
    }
    temp=a[i+1];
    a[i+1]=a[r];
    a[r]=temp;
    return(i+1);
}

约瑟夫·马克

乍看上去..