C++ quicksort排序字符串文本

Question

我正在做我的功课，并完成了quicksort递归，但它没有以正确的方式排序。似乎它不能正确交换。

这里是我的代码

#include<iostream> 
#include<ctime> 
#include<string> 
using namespace std; 


int quick_sort_help(string &text,int left, int right, int pivot){ 


    char val = text[pivot]; 
    char temp; 

    //swap 
// temp =text[pivot]; 
    //text[pivot]= text[right]; 
    //text[right]=temp; 

    //swap(&text[left],&text[right]); 

    int l = left; 
    int r = right; 

    int i=left; 
    while (i<=r) 
    { 
     while (text[i]<val) 
      i++; 
     while (text[right]>val) 
      r--; 
     if (i<=r) 
     { 
      temp=text[i]; 
      text[i]=text[r]; 
      text[r]=temp; 
      i++; 
      r--; 
     } 
    } 


    return l; 
    } 


void quicksort(string &text,int left, int right){ 

     if (left < right){ 

      int pivot=(left+right)/2; 
      int pivottwo = quick_sort_help(text, left, right, pivot); 
      quicksort(text, left, pivottwo - 1); 
      quicksort(text, pivottwo + 1, right); 
      } 
} 
void quick_sort(string &text,int size){ 
       quicksort(text,0,size);} 


int main() 
{ 

    string text="this is a test string text,.,!"; 
    int size = text.length(); 
    float t1, t2; 
    t1 = clock(); 
    quick_sort(text,size); 

    t2=clock(); 
    cout<<"quicksort Sort: "<<(t2-t1)/CLK_TCK*1000<<" msec\n"; 
    cout<<text<<endl; 


    system("pause"); 
    return 0; 
} 

输出我得到：

hi a e e,g.nii,r!tssssxttttt 

Answer 1

你必须：

1）不要使用大小，但大小1值

void quick_sort(string &text,int size){ 
      quicksort(text,0,size-1);} 

2）Pivot是不是（左+右）/ 2，但它是由quick_sort_help返回的值和pivottwo是没有必要的：

void quicksort(string &text,int left, int right) 
{ 
    if (left < right) 
    { 
     int pivot = quick_sort_help(text, left, right); 
     quicksort(text, left, pivot - 1); 
     quicksort(text, pivot + 1, right); 
    } 
} 

3）返回枢轴（I值）之前在第二，而测试我Ĵ值（您R），使交流：

int quick_sort_help(string &text,int left, int right) 
{ 
    char val = text[right]; 
    char temp; 

    int j = right; 
    int i = left - 1; 

    while (true) 
    { 
    while (text[++i] < val); 

    while (text[--j] > val) { 
     if(j == left) 
      break; 
    } 

    if(i >= j) 
     break; 

    temp=text[i]; 
    text[i]=text[j]; 
    text[j]=temp; 
} 

temp=text[i]; 
text[i]=text[right]; 
text[right]=temp; 

return i; 
} 

Answer 2

在此请看：Quicksort implementation

Answer 3

while (text[right]>val) 
     r--; 

似乎也不太可能。你递减r，但你测试的条件不会改变（应取决于r，大概...）

而且

return l; 

看起来很可疑，因为调用函数似乎期望它成为枢轴的新位置，而它是旧的左边。

另一个，你使用闭区间（see why you shouldn't），这意味着你正在访问字符串越界（这是UB）。