C++中的字符串快速排序

Question

我正在尝试在 C++ 中使用快速排序实现字母表排序，但我做不到:(

下面是我的代码：

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

int partition(string &str, int start, int end){
    int pivot = str[end-1];
    int i = start;
    for(int j=start; j<end-1 ; j++){
        if(str[j]<=pivot){
            swap(str[j], str[i]);
            i++;
        }
    }
    swap(str[i], str[end]);
    return i;
}

void quicksort(string &str, int start, int end){
    if(start<end){
        int pIndex = partition(str, start, end);

        quicksort(str, start, pIndex-1);
        quicksort(str, pIndex+1, end);
    }
}
int main()
{
    int t,k, end, start;
    string str;

    cin>>t;
    for(k=0;k<t;k++){
        cin>>str;
        end = str.size();

        quicksort(str, 0, end);
        for(int l=0; l<end; l++){
            cout<<str[l];
        }
        cout<< "\n";
    }


    return 0;
}

请大家看一下，帮我看看哪里做错了？ :(

提前致谢。

Answer 1

你的错误是在你的快速排序算法中，你只有 i 而没有 j，就像一个结束边界。

你真的要实施吗？你可以使用

std::sort(str.begin(), str.end());

所以，如果您决定编写自己的快速排序，您可以尝试这样的事情

#include <stdio.h>
#include <string>
#include <iostream>

void quickSort(std::string &str, int left, int right) {
          int i = left, j = right;
          int mid = str[(left + right) / 2];

          /* partition */
          while (i <= j) {
                while (str[i] < mid)
                      i++;
                while (str[j] > mid)
                      j--;
                if (i <= j) {
                      std::swap(str[i], str[j]);
                      i++; j--;
                }
          };

          /* recursion */
          if (left < j)
                quickSort(str, left, j);
          if (i < right)
                quickSort(str, i, right);
    }

int main()
{
    std::string str;
    std::cin >> str;
    quickSort(str, 0, str.size()-1);
    std::cout << str;
}

C++中的字符串快速排序

String quicksort in c++

c++

quicksort