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

Question

我试图解决在线裁判系统中的一个问题: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();
    }
}

在我所有的测试用例中，它都没有任何问题，但在线法官一直给我提交的 WAs(错误答案)。有人可以给我一些线索吗？非常感谢!

Answer 1

您在比较函数中的意图实际上没有任何问题，它是使用原始排序将不稳定排序转换为稳定排序的完全有效解决方案。

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

可能名称中可能包含空格，这会搞砸您的输入法，但 (1) 测试描述似乎并未指明； (2) 这会使输入变得更加困难，至少对于作业似乎针对的水平而言是这样。

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

您可能应该满足这一点，因为在比较函数中您要遵循的一条规则是一致性，如果 a > b然后 b < a .所以，两个规则，真的:-)

此外，我会建议的一件事是尽量减少对遗留 C 语言的使用，例如 printf和 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();
    }
}

您甚至可能还想考虑放弃旧版 C qsort因为 C++ 提供了内置的稳定排序，特别是 stable_sort在 <algorithm> 中找到.