c++ - 我可以在我的代码中更改什么以使我的 Quicksort 功能正常工作？ (使用结构和数组对姓氏进行排序)

Question

我正在尝试使用快速排序按字母顺序对结构数组中的姓氏进行排序，但我的代码似乎有点不对劲，因为我的输出有时是错误的，它通常按正确的顺序对名称进行排序，但它并不总是，我不知道为什么。谁能帮我找出我的代码中的错误？任何反馈都有帮助，谢谢。

void nameSort(Person* array, int size) {
    quickSort(array, 0, size-1);
}

我添加了下面的函数来帮助我的 nameSort 函数，它使用快速排序从我的数组中按字母顺序对姓氏进行排序(如果姓氏相同，则按名字排序)。

void quickSort(Person* array, int left, int right) {
    int i, j;
    const char *x;
    const char *y;
    struct Person temp;
i = left;
j = right;
x = array[(left+right)/2].last.c_str();
y = array[(left+right)/2].first.c_str();

do {
    if (array[i].last == array[j].last) {
        while ((strcmp(array[i].first.c_str(), y) < 0) && (i < right)) i++;
        while ((strcmp(array[j].first.c_str(), y) > 0) && (j > left)) j--;
    }
    while ((strcmp(array[i].last.c_str(), x) < 0) && (i < right)) i++;
    while ((strcmp(array[j].last.c_str(), x) > 0) && (j > left)) j--;
    if (i <= j) {
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
        i++; j--;
    }
}
while (i <= j);
if (left < j) quickSort(array, left, j);
if (i < right) quickSort(array, i, right);

Answer 1

除非家庭作业(或订单上的某些东西)需要它，否则您不应该使用 strcmp做你的比较，你也不应该写你自己的 Quicksort .

如果你想对一些结构进行排序，你可能想使用 std::sort :

struct person { 
    std::string first;
    std::string last;
    // ... probably more stuff here

    bool operator<(person const &other) const { 
       if (last == other.last)
           return first < other.first;
       return last < other.last;
    }
};

std::vector<person> people;

// code to put some people's names into `people` goes here

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

// print out the sorted list:
for (auto const &p : people)
    std::cout << p.last << ", " << p.first << "\n";

如果您提供重载 operator<对于正在排序的类型，std::sort将默认使用它(通过 std::less<T> )。如果想按其他字段排序，您可以指定希望如何进行比较:

struct person {
    std::string first;
    std::string last;
    time_t birth;
};

// sort the people by age/birthday:  
std::sort(people.begin(), people.end(), 
     [](auto const &a, auto const &b) { return a.birth < b.birth; });