c - 冒泡排序二维数组

Question

我有一个如下所示的二维数组；

0. PID: 0, PRI:-1
1. PID: 0, PRI:-1
2. PID: 0, PRI:-1
3. PID: 15, PRI:4
4. PID: 209, PRI:5
5. PID: 0, PRI:0
6. PID: 0, PRI:0
7. PID: 0, PRI:0
8. PID: 0, PRI:0
9. PID: 0, PRI:0

将具有有效 PRI(其中 PRI > 0)的 PI​​D 移动到数组顶部，同时根据 PRI 保持它们的数字顺序的最快、最合乎逻辑的方法是什么。

谢谢

Answer 1

至少从您的描述来看，您只关心按 PRI 值排序，但希望负值位于正值之后(但正值按顺序排列)。

一种简单的方法是在进行比较之前将 PRI 值转换为无符号。当转换为无符号时，负值将减少模 2^N-1，因此(例如)-1 将转换为 UINT_MAX(更重要的是，所有负数将转换为大于的无符号数任何以正号开始的数字)。

typedef struct { 
    int PID;
    int PRI;
} proc;

int cmp(void const *a, void const *b) { 
    proc const *aa = (proc const *)a;
    proc const *bb = (proc const *)b;

    if ((unsigned)(bb->PRI) < (unsigned)(aa->PRI))
        return -1;
    if ((unsigned)(aa->PRI) < (unsigned)(bb->PRI))
        return 1;
    return 0;
}

最后，您可能还想添加 PID 的比较，而不是仅根据 PRI 值相等返回 0，因此 PRI 值相等的项目将按 PID 排序。我暂时把它放在一边，因为你还没有说过你真的需要/想要它(这使得代码有点长，并且可能更难理解，特别是如果你不希望它在那里的话)。

编辑:如果不清楚，此比较函数旨在与 qsort 一起使用，并且(假设您正确进行比较)不需要稳定排序。如果您决定首先对一个字段进行排序(几乎总是较慢)，然后对第二个字段进行第二次(单独)排序，而不是在一次比较中对所有相关字段进行比较，则只需要稳定的排序。