C++中的快速排序實現

-4

我在下面粘貼了我的quicksort算法的實現。經過一些調試後，我發現函數quicksort（）的遞歸似乎不會終止。但在我看來，我的算法很好，我無法修復這個bug。C++中的快速排序實現

/* 
quicksort 
*/ 
int a[20]; 
int partition(int left,int right, int*a) 
    { 
     //chose some pivot element- in this case i choose the middle one 
     int pivot=(left+right)/2; 
     int b[10],c[10],i=left,j=0; 
     int k=0; 
     int pivot_element=a[pivot]; 

     //b is the left side ,c is the right side 
     while(i<=right) 
     { 
      if(a[i]!=pivot_element) 
      { 
       if(a[i]<a[pivot]) 
       { 
        b[j++]=a[i]; 
       } 
       else 
       { 
        c[k++]=a[i]; 
       } 
      }  
      i++; 

     } 


     //combine 
     i=left; 

     for(int q=0;q<j;q++) 
     a[i++]=b[q]; 

     a[i++]=pivot_element; 

     for(int p=0;p<k;p++) 
     a[i++]=c[p]; 


     return j; //return the new position of the pivot 
    } 


    void quicksort(int left,int right,int *a) 
    { 

     int index=partition(left,right,a); 
     if(index-left>0) 
     quicksort(left,index,a); 
     if(right-index+1>0) 
     quicksort(index+1,right,a); 

    } 


    int main() 
    { 
     int size; 
     cin>>size; 
     for(int i=0;i<size;i++) 
     cin>>a[i]; 

     quicksort(0,size-1,a); 

     for(int i=0;i<size;i++) 
     cout<<a[i]<<" "; 

     return 0; 
    }**

來源

2016-01-17 pooja

你可能會發現這有幫助：http://ericlippert.com/2014/03/05/how-to-debug-small-programs/（Eric Lippert，「如何調試小程序」，2014-03-05 ）。 – ruakh

調試並查看發生了什麼。我覺得'partition'函數每次都返回相同的數字 –

另外，你想要排序的數字是多少？很多時候，我們會收到像你這樣的帖子，而海報無法弄清楚的原因是他們要麼使用太多的數字進行排序，要麼是隨機數字，因此從來沒有機會確定問題容易。嘗試排序5，也許6 *已知的*號碼，並按照你的代碼。 – PaulMcKenzie

-1

您的遞歸缺乏停止標準。

來源

2016-01-17 07:50:28 cdonat

是的。當right == index + 1和index == left時，將不會有遞歸調用。 –

在你partition功能，這一點：

return j;

應該是這樣的：

return left+j;

您可以通過測試功能已經檢測到這個錯誤，寫調用它的其他代碼之前。

來源

2016-01-17 08:37:19 Beta

C++中的快速排序實現

回答

相關問題