在字符串上实现快速排序

Question

我正在尝试对一串字符执行快速排序。输出应该给我输入的字母顺序版本，但是现在它只是给我原始输入。这是尝试将伪代码从 Intro to Algorithm 3rd edition 翻译到 Quicksort。

非常感谢任何帮助，谢谢！

Here's the pseudo code of quicksort from the book

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

using namespace std;

int partition_str(string A, int start, int finish){
    char x = A[finish], temp;
    int i = start - 1;
    for (int j = start; j <= finish -1; j++){
    if (A[j] <= x){
        i ++;
        temp = A[i]; A[i] = A[j]; A[j] = temp;
    }
    temp = A[i+1]; A[i+1] = A[finish]; A[finish] = temp;
    return i+1;
    }
   }

 string quicksort_char(string A, int start, int finish)
{
if (start < finish)
{
    start = partition_str(A, start, finish);
    quicksort_char(A, start, finish -1);
    quicksort_char(A, start+1, finish);
}
return A;
}

int main(){
    string test = "gsgkdsdkjs";
    string result = quicksort_char(test, 0, 10);
    cout << result << endl;
    return 0;
}

Answer 1

在pseudocode you linked, it mentions that partition() alters subarrays in place. This insinuates that you need to pass by reference, rather than by value。请注意我在函数签名中添加的符号 (&)。您的代码按值传递，因此它正在复制输入字符串，而不是就地更改它。在您的 quicksort() 函数中，您编写了预期 A 将被该函数更改的代码。

我在这里稍微清理了你的代码，目的是让它更清晰，看起来更像伪代码...

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

void exchange(char& a, char& b)
{
    char value_of_a = a;
    char value_of_b = b;

    a = value_of_b;
    b = value_of_a;
};

int partition(string& A, int p, int r)
{
    char x = A[r];
    int i = p-1;

    for (int j=p; j<=(r-1); ++j)
    {
        if (A[j] <= x)
        {
            i++;
            exchange(A[i], A[j]);
        }
    }
    exchange(A[i+1], A[r]);

    return i+1;
};

void quicksort(string& A, int p, int r)
{
    if (p < r)
    {
        int q = partition(A, p, r);
        quicksort(A, p, q-1);
        quicksort(A, q+1, r);
    }
};

int main()
{
    string input = "gsgkdsdkjs";

    cout << "input string: " << input << endl;

    quicksort(input, 0, input.size());

    cout << "sorted string: " << input << endl;

    return 0;
}

在您的 partition_str() 函数中，您按值传入字符串 A，这会生成 A 的副本，而不是使用您传入的同一个 A。然后它会执行一些操作并 returns一个整数。 A 的副本然后被丢弃，并且您的原始 A 变量从未被修改。这意味着如果你想改变你的变量A，你必须通过引用传递。

此外，不要被函数参数命名所混淆。您的 partition_str() 函数签名是：

int partition_str(string A, int start, int finish)

'string A' 被定义为参数并不意味着它与代码中名为 'A' 的任何其他变量相关。它只是一种引用传入的特定参数的方式。

在字符串上实现快速排序

Implementing quicksort on strings

c++

quicksort