使用 C 中的冒泡排序按多个标准对结构数组进行排序

Question

我正在尝试为具有多个排序标准的结构数组实现冒泡排序。

基本上，该程序计算用户有多少关注者以及该用户正在关注多少其他用户。

结果应按以下标准排序：

1. 按关注者数量从最高到最低对用户进行排名。
2. 如果关注者数量相等，则排名为关注者数量从高到低。
3. 如果条件 1 和 2 具有相同的数字，则将用户“索引”从最低到最高排序（如用户 0 和 3 的情况）。

我已经设法提出排序，但它只按 1 个属性排序，这在代码中显示，它仅按关注者数量排序。我不太确定下一步是什么。

另外，我试图使排序成为 main() 之外的单独函数，但它需要访问 u[i].node、u[i].nFollower 和 u[i].nFollow。而且我不知道正确的方法是什么。您能否显示正确的语法来执行此操作，因为我对 C 非常陌生

。非常感谢！

输入：

Enter the number of users: 6
Enter a user (follower): 0
Enter a user (followed by 0): 1
Enter a user (follower): 1
Enter a user (followed by 1): 5
Enter a user (follower): 3
Enter a user (followed by 3): 5
Enter a user (follower): 5
Enter a user (followed by 5): 0
Enter a user (follower): 2
Enter a user (followed by 5): 5
Enter a user (follower): 1
Enter a user (followed by 5): 3
Enter a user (follower): #
Done.

不排序的输出

5 has 3 followers(s) and follows 1 user(s).
0 has 1 followers(s) and follows 1 user(s).
3 has 1 followers(s) and follows 1 user(s).
1 has 1 followers(s) and follows 2 user(s).
4 has 0 followers(s) and follows 0 user(s).
2 has 0 followers(s) and follows 1 user(s).

期望的输出：

5 has 3 followers(s) and follows 1 user(s).
1 has 1 followers(s) and follows 2 user(s).
0 has 1 followers(s) and follows 1 user(s).
3 has 1 followers(s) and follows 1 user(s).
2 has 0 followers(s) and follows 1 user(s).
4 has 0 followers(s) and follows 0 user(s).

#include <stdio.h>
#include "WGraph.h"

typedef struct User {
    int node;
    int nFollower;
    int nFollow;
} User;

int main (void) {
    Edge e = {0, 0, 1};
    int nUsers;

    printf("Enter the number of users: ");
    scanf("%d", &nUsers);
    
    Graph g = newGraph(nUsers);

    printf("Enter a user (follower): ");
    while (scanf("%d", &e.v) == 1) {
        printf("Enter a user (followed by 0): ");
        scanf("%d", &e.w);
        insertEdge(g, e);
        printf("Enter a user (follower): ");
    }
    printf("Done.\n");

    //showGraph(g);


    int nV = numOfVertices(g);
    int countFollower;
    int countFollow;
    User u[nV];
    printf("Ranking by follower base:\n");
    for (int i = 0; i < nV; i++) {
        countFollow = 0;
        countFollower = 0;
        u[i].node = i;
        for (int j = 0; j < nV; j++) {
            if (adjacent(g, j, i) != 0) {
                countFollower++;
            }

            if (adjacent(g, i, j) != 0) {
                countFollow++;
            }
        }
        u[i].nFollower = countFollower;
        u[i].nFollow = countFollow;
    }
    
    //Sort and update array of struct
    int temp1;
    int temp2;
    int temp3;
    for (int i = 0; i < nV; i++) {
        for (int j = 0; j < nV; j++) {
            if (u[i].nFollower > u[j].nFollower) {
                temp1 = u[j].nFollow;
                temp2 = u[j].nFollower;
                temp3 = u[j].node;
                u[j].nFollow = u[i].nFollow;
                u[i].nFollow = temp1;
                u[j].nFollower = u[i].nFollower;
                u[i].nFollower = temp2;
                u[j].node = u[i].node;
                u[i].node = temp3;
            }
        }
    }

    for (int i = 0; i < nV; i++) {
        printf("%d has %d followers(s) and follows %d user(s).\n", u[i].node, u[i].nFollower, u[i].nFollow);
    }

    //freeGraph(g);
    return 0;
}

Answer 1

只需在冒泡排序中排序时检查条件即可，

for (int i = 0; i < nV; i++) {
                for (int j = 0; j < nV; j++) {
                        if ((u[i].nFollower > u[j].nFollower) || \
                                        (u[i].nFollower == u[j].nFollower && u[i].Follow > u[j].Follow) || \ 
                                        (u[i].nFollower == u[j].nFollower && u[i].Follow == u[j].Follow && i < j)) {
                                temp1 = u[j].nFollow;
                                temp2 = u[j].nFollower;
                                temp3 = u[j].node;
                                u[j].nFollow = u[i].nFollow;
                                u[i].nFollow = temp1;
                                u[j].nFollower = u[i].nFollower;
                                u[i].nFollower = temp2;
                                u[j].node = u[i].node;
                                u[i].node = temp3;
                        }
                }
        }

这里我们迭代 n-1 次，每次迭代时我们都会跳过顺序正确的元素。我没有使用临时变量，而是使用 xor 运算符来交换元素。

 for (int i = 0; i < nV-1; i++) {
                for (int j = 0; j+1 <= nv-1-i; j++) {
                        if ((u[j].nFollower > u[j+1].nFollower) || \
                                        (u[j].nFollower == u[j+1].nFollower && u[j].Follow > u[j+1].Follow)) {

                                u[j].nFollow ^= u[j+1].nFollow;
                                u[j+1].nFollow ^= u[j].nFollow;
                                u[j].nFollow ^= u[j+1].nFollow;

                                u[j].nFollower ^= u[j+1].nFollower;
                                u[j+1].nFollower ^= u[j].nFollower;
                                u[j].nFollower ^= u[j+1].nFollower;

                                u[j].node ^= u[j+1].node;
                                u[j+1].node ^= u[j].node;
                                u[j].node ^= u[j+1].node;
                        }
                }
        }