Python中同时排序两个列表：按a排序，相等时按b排序，如何避免临时列表？

问题描述 #

我有两个列表a和b，需要同时对它们排序——优先按a的元素排序，当a中元素相等时，再按b的元素排序。目前使用以下代码实现需求：

a = [1,2,1,3]
b = [5,0,0,1]
z = sorted(zip(a,b))
a, b = zip(*z)

但sorted()会创建一个包含所有元素元组的额外临时列表，由于需要频繁执行该排序操作，希望找到能避免这类大临时列表的高效实现方式。

解决方案：基于索引排序的原地修改 #

核心思路是通过排序索引而非直接排序元素元组，仅创建一个占用空间极小的索引列表，再根据排序后的索引原地调整原列表的元素，避免生成包含大量元素元组的临时列表。

基础实现 #

a = [1,2,1,3]
b = [5,0,0,1]

# 生成索引列表并按(a[i], b[i])的规则排序
indices = sorted(range(len(a)), key=lambda i: (a[i], b[i]))

# 原地修改原列表，无需创建新的列表对象
a[:] = [a[i] for i in indices]
b[:] = [b[i] for i in indices]

性能优化：使用operator.itemgetter（可选） #

如果追求极致性能，可以用operator.itemgetter替代lambda表达式（它是C语言实现，比Python层面的lambda更快）：

from operator import itemgetter

indices = sorted(range(len(a)), key=lambda i: itemgetter(i)(a, b))

原理说明 #

• 索引列表indices仅存储整数索引，内存占用远小于包含元素元组的临时列表（尤其是当a、b的元素是大型对象时）。
• 使用切片赋值a[:] = ...是原地修改原列表，不会创建新的列表对象，减少了对象创建与销毁的开销。
• Python内置的sorted()采用Timsort算法，本身需要O(n)的空间，但此处仅用该空间存储索引，而非元素元组，整体内存开销大幅降低。

注意：完全零临时空间的排序是不现实的（除非使用效率极低的原地冒泡排序），但此方案已将临时空间开销降至最小，同时保证了Timsort的高效排序性能。

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