C语言如何通过镜像效果按一个数组的顺序对另一数组排序

问题核心 #

你当前的代码实现的是「同下标的输入值和输出值绑定」逻辑：排序时将left[i]和right[i]作为整体移动，因此排序后输出数组的第i位始终是原输入数组第i位对应的输出值。但结合你的业务场景描述，你实际需要的是「保留输入序列到输出序列的重排规则」：即先从原有箭头中提取重排置换规则，再将该规则作用在排序后的输入序列上，得到符合预期的输出序列。

实现思路（适配排列类箭头场景） #

你的业务中输入输出为相同数字的排列，可按以下步骤实现：

1. 保存原输入数组副本，建立输入值到原下标的映射表，记录每个输入值在原输入数组中的位置
2. 提取重排置换数组：输出数组的第i位元素对应的原输入数组位置，就是置换规则的第i项
3. 排序输入数组得到升序结果
4. 按照置换规则，用排序后的输入数组生成新的输出数组

代码实现 #

#include <stdlib.h>
#include <string.h>

int cmp_int(const void *a, const void *b) {
    return *(const int *)a - *(const int *)b;
}

void order(int *left, int *right, int len) {
    // 先保存原输入数组的副本
    int *orig_left = malloc(len * sizeof(int));
    memcpy(orig_left, left, len * sizeof(int));
    
    int *pos_map = malloc(len * sizeof(int));
    int *perm = malloc(len * sizeof(int));
    
    // 步骤1：建立原输入值到原下标的映射
    for (int i = 0; i < len; i++) {
        pos_map[orig_left[i]] = i;
    }
    
    // 步骤2：提取置换规则
    for (int i = 0; i < len; i++) {
        perm[i] = pos_map[right[i]];
    }
    
    // 步骤3：排序输入数组
    qsort(left, len, sizeof(int), cmp_int);
    
    // 步骤4：生成新的输出数组
    for (int i = 0; i < len; i++) {
        right[i] = left[perm[i]];
    }
    
    free(orig_left);
    free(pos_map);
    free(perm);
}

原代码的问题说明 #

如果你确实需要使用「同下标值绑定」的逻辑（比如第一个示例的场景，输入输出为不同值的对应），原代码存在两个问题：

1. 两个数组长度不同时，combined结构体中未被赋值的字段是随机值，会导致排序异常
2. 排序长度取max(len1, len2)会导致短数组的有效数据被随机值覆盖

修复后的同下标绑定逻辑代码如下：

#include <stdlib.h>
#include <stdint.h>

struct Combined
{
    int a;
    int b;
    uint8_t a_valid;
    uint8_t b_valid;
};

int cmp(const void *a, const void *b)
{
    const struct Combined *x = (const struct Combined *)a;
    const struct Combined *y = (const struct Combined *)b;
    // 无效值排到末尾
    if (!x->a_valid) return 1;
    if (!y->a_valid) return -1;
    return x->a - y->a;
}

void order(int *left, int len1, int *right, int len2)
{
    unsigned int len = len1 > len2 ? len1 : len2;
    struct Combined *combined = calloc(len, sizeof(struct Combined));

    for (int i = 0; i < len1; i++) {
        combined[i].a = left[i];
        combined[i].a_valid = 1;
    }

    for (int i = 0; i < len2; i++) {
        combined[i].b = right[i];
        combined[i].b_valid = 1;
    }

    qsort(combined, len, sizeof(struct Combined), cmp);

    for (int i = 0; i < len1; i++) {
        left[i] = combined[i].a;
    }

    for (int i = 0; i < len2; i++) {
        right[i] = combined[i].b;
    }

    free(combined);
}

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