快速排序邏輯無法正常工作

Question

以下是快速排序的代碼，我做..但有一些錯誤，這給了我錯誤的輸出。對於整數陣列[65,70,75,80,85,60,55,50,45]，我得到的輸出是 [45 50 55 65 60 70 75 80 85]，這顯然是錯誤的。

int partition(int *b,int r,int s) 
{ 
    int pivot=b[r]; 
    int i,j; 
    i=r; 
    j=s; 
    while(i<=j) 
    { 
     while(b[i]<=pivot) 
      i++; 
     while(b[j]>=pivot) 
      j--; 
     if(i<j) 
     { 
      int temp; 
      temp=b[i]; 
      b[i]=b[j]; 
      b[j]=temp; 
     } 
    } 
    b[r]=b[j]; 
    b[j]=pivot; 
    return j; 
} 
void quicksort(int *a,int p,int q) 
{ 

    if(p<q) 
    { 
     int j; 
     j=partition(a,p,q); 
     quicksort(a,p,j-1); 
     quicksort(a,j+1,q); 

    } 
} 
int main() 
{ 
    int arr[9]={65,70,75,80,85,60,55,50,45}; 
    quicksort(arr,0,8); 
    for(int i=0;i<9;i++) 
     printf("%d ",arr[i]); 
    getch(); 
    return 0; 
} 

有人可以提出我的錯誤嗎？

Answer 1

你應該檢查你是不是出界。 另外我認爲你應該使用嚴格的比較。你目前的代碼將無法排序[1, 2]（最後一個交換會搞砸）。

最後一次交換看起來有點武斷，不應該需要。