C ++快速排序字符串文本 [英] c++ quicksort sort string text

问题描述

我正在做作业，并且完成了递归快速排序，但是排序方式不正确。

I am doing my homework, and completed quicksort recursive, however it doesn't sort in a correct way. Seems to be it doesn't swap correctly.

这是我的代码

#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

推荐答案

您必须：

1）不要使用大小，而是使用大小为1的值

1) Don't use size but size-1 value

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

2）Pivot不是（left + right）/ 2，但这是quick_sort_help返回的值，pivottwo不是必需的：

2) Pivot is not (left+right)/2 but it's the value returned by quick_sort_help, and pivottwo is not necessary:

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值）之前进行交换：

3) Test my j value (your r) in the second while and make the exchange before returning the pivot (the i value):

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;
 }

这篇关于C ++快速排序字符串文本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！