如何以低于O(n²)的时间复杂度按第二数组排序结果重排第一数组？

你当前的双层循环实现属于冒泡排序逻辑，时间复杂度O(n²)仅适合极小数据量场景，通用场景下可以优化到O(n log n) 时间复杂度，方案如下：

核心思路 #

• 将两个数组同下标的元素绑定为键值对，键为arr2的对应元素，值为arr1的对应元素
• 对键值对数组排序：排序规则为先按键升序，键相等时按值升序，完全匹配你现有逻辑
• 排序完成后将值回写至原数组即可

C++ 实现代码 #

#include <algorithm>
#include <utility>

void sort(int size, int arr1[], int arr2[]) {
    // 构造绑定两个数组元素的pair数组
    std::pair<int, int> *pairs = new std::pair<int, int>[size];
    for (int i = 0; i < size; ++i) {
        pairs[i] = {arr2[i], arr1[i]};
    }
    // 标准库sort平均时间复杂度O(n log n)，pair默认比较逻辑正好匹配需求
    std::sort(pairs, pairs + size);
    // 回写结果到原数组
    for (int i = 0; i < size; ++i) {
        arr2[i] = pairs[i].first;
        arr1[i] = pairs[i].second;
    }
    delete[] pairs;
}

上述代码用你提供的示例输入测试，输出结果和你给出的预期结果完全一致。

特殊场景额外优化 #

如果你的业务场景中arr2的取值范围非常小（比如arr2的取值只有1~10），可以用计数排序实现O(n + k) 时间复杂度（k为arr2的取值范围大小），性能比O(n log n)方案还要好：

1. 先按arr2的取值分组，收集每个arr2值对应的所有arr1元素
2. 对每个分组内的arr1元素单独做升序排序
3. 按arr2从小到大的顺序，把分组内容依次填充回arr1和arr2数组即可

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