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++中的快速排序实现

回答

相关问题