如何在C语言中以指定数组为键对多个关联数组排序？

先明确需求：给定多个关联数组，以其中一个数组为键排序，其余数组的元素需随键的排序结果同步对应。比如示例：

int a[4] = {4, 3, 1, 2};
float b[4] = {1.0, 2.0, 3.0, 4.0};

排序后预期：

int a[4] = {1, 2, 3, 4};
float b[4] = {3.0, 4.0, 2.0, 1.0};

下面针对不同实现思路分析优劣，给出最优方案：

1. 索引排序法（性能最优首选） #

核心思路是排序索引而非原数组：先创建一个保存原数组下标的索引数组，基于键数组的值对索引排序，最后根据排序后的索引重新排列原数组（或直接通过索引访问，避免修改原数组）。

这种方法的优势是：

• 时间复杂度保持标准排序的O(nlogn)，无额外开销
• 完全避免大元素的内存拷贝（比如b是复杂结构体时，不需要移动结构体本身，只移动整数索引）
• 支持重复键的场景，不会丢失数据

代码示例 #

#include <stdio.h>
#include <stdlib.h>

// 比较函数：基于a数组的值排序索引
int compare_indices(const void *x, const void *y, void *arg) {
    int *a = (int*)arg;
    int idx1 = *(int*)x;
    int idx2 = *(int*)y;
    return a[idx1] - a[idx2];
}

int main() {
    int a[4] = {4, 3, 1, 2};
    float b[4] = {1.0, 2.0, 3.0, 4.0};
    int n = sizeof(a)/sizeof(a[0]);
    
    // 创建索引数组
    int indices[n];
    for (int i = 0; i < n; i++) {
        indices[i] = i;
    }
    
    // 对索引排序（使用qsort_r传递额外参数a；若用标准qsort，需将a设为全局变量）
    qsort_r(indices, n, sizeof(int), compare_indices, a);
    
    // 根据索引重新排列数组（若需修改原数组）
    int sorted_a[n];
    float sorted_b[n];
    for (int i = 0; i < n; i++) {
        sorted_a[i] = a[indices[i]];
        sorted_b[i] = b[indices[i]];
    }
    
    // 输出结果
    printf("sorted a: ");
    for (int i = 0; i < n; i++) printf("%d ", sorted_a[i]);
    printf("\nsorted b: ");
    for (int i = 0; i < n; i++) printf("%.1f ", sorted_b[i]);
    
    return 0;
}

如果不需要修改原数组，直接通过indices[i]访问对应元素即可，完全避免拷贝操作，这对大结构体数组尤其友好。

2. 结构体排序法（直观易用） #

将键和对应的关联值打包成结构体，排序结构体数组后再拆回原数组结构。

代码示例 #

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int key;
    float val;
} Pair;

int compare_pairs(const void *x, const void *y) {
    const Pair *p1 = (const Pair*)x;
    const Pair *p2 = (const Pair*)y;
    return p1->key - p2->key;
}

int main() {
    int a[4] = {4, 3, 1, 2};
    float b[4] = {1.0, 2.0, 3.0, 4.0};
    int n = sizeof(a)/sizeof(a[0]);
    
    Pair pairs[n];
    for (int i = 0; i < n; i++) {
        pairs[i].key = a[i];
        pairs[i].val = b[i];
    }
    
    qsort(pairs, n, sizeof(Pair), compare_pairs);
    
    // 拆回原数组
    for (int i = 0; i < n; i++) {
        a[i] = pairs[i].key;
        b[i] = pairs[i].val;
    }
    
    // 输出结果
    printf("sorted a: ");
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\nsorted b: ");
    for (int i = 0; i < n; i++) printf("%.1f ", b[i]);
    
    return 0;
}

优缺点分析：

• 优点：逻辑直观，代码易读，适合小数据量或关联元素体积较小的场景
• 缺点：如果关联元素是大结构体，排序时会频繁移动结构体数据，内存开销大，性能不如索引排序

3. 临时映射法（类似std::map思路，不推荐） #

C++中std::map可以快速实现键值映射，但它的性能并非最优：

• std::map基于红黑树实现，插入和遍历的时间复杂度是O(nlogn)，但缓存局部性远不如数组排序，实际运行速度比qsort慢不少
• 若存在重复键，std::map会自动覆盖旧值，无法保留原数组中的全部关联关系，不符合需求

在C中手动实现类似映射（比如红黑树或哈希表）复杂度高，且性能不如索引排序或结构体排序，因此不推荐这种方案。

关于O(n²)的实现 #

你提到的@daro的实现如果是通过冒泡排序等O(n²)算法同步交换数组元素，这种方法仅适用于极小数据量，大数据量下性能会急剧下降，完全不具备实用性，直接排除即可。

方案选择总结 #

• 大数据量/大体积关联元素：优先使用索引排序法，避免内存拷贝开销
• 小数据量/追求代码简洁：使用结构体排序法
• 无需修改原数组：直接通过排序后的索引数组访问元素，性能最优

内容的提问来源于stack exchange，提问作者Xu_ict