快速排序的双向扫描结果出错

Question

int Partation2(int *a,int q,int r){
    int prior=a[q];
    int left=q+1;
    int right=r;
    while(left <= right){
    while((left <= right)&&a[left]<=prior)left++;
    while((left <= right)&&a[right]>prior)right--;
    if(left < right){
    int temp=a[left];
    a[left]=a[right];
    a[right]=temp;
    }
   }
   int temp=prior;
    prior=a[right];
    a[right]=temp;
    return right;    
}//Ë«ÏòɨÃè·¨ 

void QuickSort(int *a,int p,int r){
    if(p<r){
 
        int q=Partation2(a,p,r);
        QuickSort(a,p,q-1);
        QuickSort(a,q+1,r);
    } 
}

int main(){
    int a[5]={2,3,1,8,5};
    QuickSort(a,0,4);
    for(int i=0;i<5;i++){
        cout<<a[i]<<endl;
    }
}

求大神帮助看看，菜鸡有点头疼

Answer 1

您好！您的快速排序代码中的双向扫描结果出错了。在Partation2函数中，最后交换prior和a[right]的值时，应该交换a[q]和a[right]的值。正确的代码应该是这样的：

int Partation2(int *a,int q,int r){
    int prior=a[q];
    int left=q+1;
    int right=r;
    while(left <= right){
        while((left <= right)&&a[left]<=prior)left++;
        while((left <= right)&&a[right]>prior)right--;
        if(left < right){
            int temp=a[left];
            a[left]=a[right];
            a[right]=temp;
        }
    }
    int temp=a[q];
    a[q]=a[right];
    a[right]=temp;
    return right;    
}