c++ - QuickSort 程序不工作

Question

我只是想在字符串上实现快速排序，但它不起作用。输出结果与输入相同，而不是排序后的字符串。我已经检查了很多次，但找不到任何错误。请帮帮我。

下面是快速排序函数。

void quicksort(string str1, int si, int ei)
{
    if (si < ei)
    {
        int pi = partition(str1, si, ei);
        quicksort(str1, si, pi-1);
        quicksort(str1, pi+1, ei);
    }
}

分区函数。

int partition(string str2, int si, int ei)
{
    int i = si-1;
    char x = str2[ei];
    int j;
    for (j = si ; j <= ei-1 ; j++)
    {
        if (str2[j] <= x)
        {
            i++;
            exchange(&str2[i], &str2[j]);
        }
    }
    exchange(&str2[ei], &str2[i+1]);
    return i+1;
}

和交换功能。

void exchange(char *a, char *b)
{
    char temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

主要功能如下。

int main()
{
    int l1;
    string str;
    cout << "Enter the string to be sorted";
    cin >> str;
    l1 = str.length();
    quicksort(str, 0, l1-1);
    cout << str;
    return 0;
}

Answer 1

quicksort 按值获取 str1，然后递归地将其复制到其子问题中。每个实例都在一个单独的、不相关的字符串上运行，并对其本地拷贝进行修改。

您需要通过引用传递str:

void quicksort(string& str1, int si, int ei)

分区也是如此:

int partition(string& str2, int si, int ei)