使用 qsort() 进行稳定排序？

我试图解决在线法官系统中的一个问题：https://acm.cs.nthu.edu.tw/problem/11519/它需要一个整数 n，后跟 n 行姓名和年级。 问题是使用稳定的排序算法按等级对它们进行排序。 我使用 qsort() 并在 compar() 中给出该人的顺序以稳定 qsort()。这是我的代码：

class People{
    public:
        char name[11];
        int grade;
        int order;
        void print(){ printf("%s %d\n", name, grade); }
};

int compar(const void *a, const void *b){
    People *A = (People*)a;
    People *B = (People*)b;
    if(A->grade > B->grade) return 1;
    else if(A->grade < B->grade) return -1;
    else if(A->order > B->order) return 1;
    else if(A->order < B->order) return -1;
}

int main(){
    int n;
    scanf("%d", &n);
    People *p = new People[n];
    for(int i=0;i<n;i++){
        scanf("%s %d", p[i].name, &p[i].grade);
        p[i].order = i;
    }
    qsort(p, n, sizeof(People), compar);
    for(int i=0;i<n;i++){
        p[i].print();
    }
}

在我所有的测试用例中，它都没有任何问题，但在线法官一直给我提交的四个WA（错误答案）。有人可以给我一些关于这方面的线索吗？非常感谢！

其实你的并没有什么问题intent在比较函数中，使用原始排序将不稳定排序变为稳定排序是一种完全有效的解决方案。

所以，为什么它被拒绝，我无法确定，至少在无法访问正在使用的测试数据的情况下。

It's possible名称可能包含空格，这会搞乱您的输入法，但是（1）测试描述似乎没有指出； （2）这会使输入变得更加困难，至少对于作业所针对的水平而言是如此。

然而，尽管你可能认为这不太可能，但is排序算法可能在某个时刻将对象与其自身进行比较的可能性。这意味着它将返回一些任意值，因为您假设它们总是不同的，考虑到添加的order检查。

您可能应该考虑这一点，因为您在比较函数中要遵循的一个规则是一致性，并且如果a > b then b < a. So, two规则，真的:-)

另外，我还说一件事would建议是尽量减少对旧 C 内容的使用，例如printf and scanf其中 C++ 提供了更好的设施。

为此，我相信你最好这样做：

#include <iostream>
#include <cstdlib>

struct People {
    char name[11];
    int grade;
    int order;
    void print() { std::cout << name << " " << grade << std::endl; }
};

int compar(const void *a, const void *b) {
    People *A = (People*)a;
    People *B = (People*)b;

    // Use grade if different.

    if (A->grade > B->grade) return 1;
    if (A->grade < B->grade) return -1;

    // Otherwise, use order, unique in different objects.

    if (A->order > B->order) return 1;
    if (A->order < B->order) return -1;

    // But cater for the possibility you may compare an object with itself.

    return 0;
}

int main() {
    int n;
    std::cin >> n;

    People *p = new People[n];

    for (int i = 0; i < n; i++) {
        std::cin >> p[i].name >> p[i].grade;
        p[i].order = i;
    }

    qsort(p, n, sizeof(People), compar);

    for (int i = 0; i < n; i++) {
        p[i].print();
    }
}

您甚至可能还想考虑放弃传统的 Cqsort因为 C++ 提供了内置的稳定排序，特别是stable_sort在发现<algorithm>.