我的quicksort实现有什么问题？

-4

下面的程序是用于使用快速排序C++排序的列表。下面所输入的代码已经成功地在代码编译::块和在http://cpp.sh/，但不幸的是它进入挂起中的元素之后，任何帮助将理解..我的quicksort实现有什么问题？

void quicksort(vector<int> v,int left_index,int right_index) 
{ 
    if(left_index>=right_index) 
     return; 
    int pivot=(right_index+left_index)/2; 

    int left=left_index; 
    int right=right_index; 
    while(left<=right) 
    { 
     while(v[left]<v[pivot]) 
      left++; 
     while(v[right]>v[pivot]) 
      right--; 
     if(left<=right) 
     { 
      swap(v,left,right); 
      left++;right--; 
     } 
    } 
    quicksort(v,left_index,right); 
    quicksort(v,left,right_index); 
}

来源

2016-10-11 Jeswin

解决此类问题的正确工具是您的调试器。在*堆栈溢出问题之前，您应该逐行执行您的代码。如需更多帮助，请阅读[如何调试小程序（由Eric Lippert撰写）]（https://ericlippert.com/2014/03/05/how-to-debug-small-programs/）。至少，您应该\编辑您的问题，以包含一个[最小，完整和可验证]（http://stackoverflow.com/help/mcve）示例，该示例再现了您的问题，以及您在调试器。 –

您应该了解[传递参数作为参考]和何时传递值。另请参阅http://stackoverflow.com/a/3399248/104774 – stefaanv

除了通过引用传递之外，我不认为您的实现会保证取得进展：如果其中一个分区为空，则递归会卡住并溢出堆栈或永远运行。 –

传递引用是必须的，正如别人指出的。
在分区期间保持枢轴不变。 pivot = v[pivot]确保。
外环范围从left<right更改为left<=right。

正在运行的代码。

#include <iostream> 
#include<vector> 
using namespace std; 

void print(const vector<int> &v) 
{ 
    cout<<"The sorted list is:"<<endl; 
    for(int i=0;i<(int)v.size();i++) 
     cout<<v[i]<<' '; 
    cout<<endl; 
} 
void swap(vector<int> &v,int left,int right) 
{ 
    int temp=v[left]; 
    v[left]=v[right]; 
    v[right]=temp; 
} 

void quicksort(vector<int> &v,int left_index,int right_index) 
{ 
    if(left_index>=right_index) 
     return; 
    int pivot=(right_index+left_index)/2; 

    pivot = v[pivot]; 
    int left=left_index; 
    int right=right_index; 
    while(left<right) 
    { 
     while(v[left]<=pivot) 
      left++; 
     while(v[right]>pivot) 
      right--; 
     if(left<right){ 
      swap(v,left,right); 
      left++; 
      right--; 
     } 
    } 
    quicksort(v,left_index,right); 
    quicksort(v,left,right_index); 
    print(v); 
} 

int main() 
{ 
    int no; 
    vector<int> v; 
    cout << "Please enter the elements in your list" << endl; 
    cout << "Enter 0 to exit..."<<endl; 
    while(cin >> no) 
    { 
     if(no==0) 
      break; 
     v.push_back(no); 
    } 
    quicksort(v,0,v.size()-1); 
    return 0; 
}

来源

2016-10-11 14:06:10 v78

非常感谢！你的建议，改变分区部分中的if（left Jeswin

我的quicksort实现有什么问题？

回答

相关问题