如何依据列表B的元素出现顺序对含重复值的列表A进行排序

问题场景 #

我们需要解决的场景如下：待排序列表A存在重复元素、顺序参考列表B的所有元素均唯一，要求按照元素在B中的出现顺序对A的元素完成排序。

示例说明 #

输入输出示例：

• 待排序列表A：A = [1, 2, 2, 2, 3, 4, 4, 5]
• 顺序参考列表B：B = [8, 5, 6, 2, 10, 3, 1, 9, 4]
• 期望排序结果：C = [5, 2, 2, 2, 3, 1, 4, 4]

实现思路 #

这个场景排序的核心是复用参考列表B的元素顺序，为了保证排序效率，我们可以先预先生成元素和对应顺序的映射：

• 遍历参考列表B，生成元素到下标的映射字典，单次查询复杂度为O(1)，避免排序过程中反复调用list.index()带来的额外开销
• 对列表A排序时，直接将元素在映射字典中对应的下标作为排序key即可

代码实现（Python） #

常规版本（要求A中所有元素都存在于B中）：

# 构建顺序映射
order_map = {val: idx for idx, val in enumerate(B)}
# 按指定顺序排序
sorted_A = sorted(A, key=lambda x: order_map[x])

兼容A存在B中没有的元素版本（不在B中的元素默认排到末尾）：

order_map = {val: idx for idx, val in enumerate(B)}
# 不存在的元素默认赋值无穷大，排到最后，如需排到最前可改为 float('-inf')
sorted_A = sorted(A, key=lambda x: order_map.get(x, float('inf')))

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