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的PID(其中PRI> 0)移动到数组顶部，同时根据PRI保持它们的数字顺序，最快和最合乎逻辑的方法是什么?

谢谢

Answer 1

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

一个简单的方法是在进行比较之前将PRI值转换为unsigned。当转换为无符号数时，负值将被取模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一起工作，并且(假设您正确地进行比较)不需要稳定的排序。只有当您决定采用(几乎总是较慢的)先对一个字段排序，然后对另一个字段进行第二次(单独的)排序，而不是在一次比较中对所有相关字段进行比较时，才需要稳定的排序。

Answer 2

可以按PRI降序对数组进行排序。或者不使用-1，您可以像这样定义无效的PRI:

const int INVALID_PRI = INT_MAX;

并对PRI列上的数组进行排序。