cin 字符串到一个向量中并对它们进行快速排序

Question

Write a void function called string_list_sort() that reads in any number of strings (duplicates are allowed) from cin, stores them in a vector, and then sorts them. Don’t use the standard C++ sort function here — use the version of quicksort that you created.

我的问题是我尝试使用 strcmp() 但出现了很多错误，所以我尝试了这种方法，但我在使用 char val = v[end] 时遇到了问题。我不确定如何比较两个 std::string 值。 我将 char 更改为 string 并且它有效。现在我的问题是 v = {"apple", "car", "fox", "soap", "foz"};我得到的结果是 apple, soap, car, fox, foz 这不是按字母顺序排列的

#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <vector>
#include "error.h"

using namespace std;

void string_list_sort(vector<string> v){
  string line;
    while (getline(cin, line)){
        if (line.empty()){
            break; 
         }  
       v.push_back(line); 
    }
}

int partition(vector<string>&v, int begin, int end)
{
    char val = v[end];
    char temp;

    int j = end;
    int i = begin - 1;

    while (true)
    {
        while (v[++i] < val)
        while (v[--j] > val)
        {
            if (j == begin)
                break;
        }

        if (i >= j)
            break;

        temp = v[i];
        v[i] = v[j];
        v[j] = temp;
    }

    temp = v[i];
    v[i] = v[end];
    v[end] = temp;

    return i;
}

void quicksort(vector<string>& v, int begin, int end)
{
    if (begin < end)
    {
        int p = partition(v, begin, end);
        quicksort(v, begin, p - 1);
        quicksort(v, p + 1, end);
    }
}
void quick_sort(vector<string>& v)
{
    quicksort(v, 0, v.size() - 1);
}

int main()
{
    vector<string> v;
    v =
    {   " this is a test string,.,!"};
    string word;
    while (cin >> word)
    {
        v.push_back(word);
    }
    quick_sort(v);
    for (int i = 0; i < v.size(); i++)
    {
        cout << v[i] << " ";

    }
}

Answer 1

您可以使用 std::string::compare() 或关系运算符比较字符串。看起来你在这里尝试过使用关系运算符，但正如@user4581301 指出的那样，在第一行的 partition() 中，你有

char val = v[end];

但是，v[end] 是 'string' 类型，而不是 'char'。如果您将 val 和 temp 声明为 string 而不是 char，您可以使用您拥有的关系运算符对它们进行排序，我认为您会没事的。

compare() 文档：fttp://www.cplusplus.com/reference/string/string/compare/

关系运算符：http://www.cplusplus.com/reference/string/string/operators/

Answer 2

OP几乎都有排序功能了。有两个错误特别突出：

char val = v[end];
char temp;

v 是一个 vector<string> 所以 v[end] 将 return 一个 string.

string val = v[end];
string temp;

负责处理并使程序编译并成功排序。无需进入 strings 逐个字符进行比较。 string 对你有用吗。

第二个问题：Quicksort的分区函数应该是这样的(Looting from wikipedia here)

algorithm partition(A, lo, hi) is
    pivot := A[lo]
    i := lo – 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] < pivot

        do
            j := j – 1
        while A[j] > pivot

        if i >= j then
            return j

        swap A[i] with A[j]

并且 OP 的分区功能已经拾取了一堆额外的包袱，需要移除这些包袱才能从他们的导师那里获得最佳分数。查看上面的伪实现并将其与您的进行比较。您可能会以正确的方式看到错误，但如果没有，请站在巨人的肩膀上并将其翻译成 C++（提示：:= 在 C++ 中是普通的旧 =，您需要添加一些;s 和大括号）。根据需要调试结果。我不会翻译它，因为那几乎完全违背了作业的要点。

旁注（收集一些重要评论）：

编写测试驱动程序时，在确定算法有效之前不要接受用户输入。从易于可视化的预加载输入开始，如

int main()
{
    vector<string> v{"C","B","A"};
    quick_sort(v);
    for (size_t i = 0; i < v.size(); i++)
    {
        cout << v[i] << " ";

    }
}

当输出为 "A B C " 时，将输入更改为更复杂但仍易于可视化的内容

vector<string> v{"A","C","Q","B","A"};

当它奏效时，发疯并给它喂一些讨厌的东西。我喜欢彭赞斯海盗中的 Major General's Song。

cin 字符串到一个向量中并对它们进行快速排序

cin strings into a vector and quicksort them

c++

string

quicksort

stdvector