1

我正在做作业，并完成了递归快速排序，但是它没有以正确的方式排序。似乎它没有正确交换。

这是我的代码

#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
4

3 回答 3

3

你必须：

1) 不要使用 size 而是 size-1 值

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

2) Pivot 不是 (left+right)/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）第二次测试我的j值（你的r）并在返回枢轴之前进行交换（i值）：

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;
 }
于 2012-04-16T19:52:34.550 回答
0

看看这个：快速排序实现

于 2012-04-16T19:19:25.447 回答
0 
 while (text[right]>val)
      r--;

这似乎不太可能。你正在递减r，但你测试的条件永远不会改变（应该取决于r，可能......）

还

return l;

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

另一个，您使用封闭间隔（看看为什么不应该），这意味着您正在访问越界的字符串（即 UB）。

于 2012-04-16T19:28:56.447 回答