如何对含任意深度子列表的整数-列表混合结构进行自定义排序？

需求与示例 #

输入示例1 #

[[5, [2, 1], 3], [3, [8, 7], [2, 1, 3], 2], [[3, 2, 1], 3, -1]]

排序规则 #

• 整数需排在所有子列表之前
• 整数按常规升序排序
• 子列表比较规则：首个元素小的列表更小；首个元素相同时依次比较后续元素；前缀元素相同但长度更短的列表更小（如[1, 2] < [1, 2, 3]）

预期输出1 #

[[-1, 3, [1, 2, 3]], [2, 3, [1, 2], [7, 8]], [3, 5, [1, 2]]]

输入示例2 #

[1, 4, 3, [[5, 7, 1, 2], 2, 5, 10, 2], 8, [2, 5, [5, 3, 3]], [2, 5, 10, 2, [1, 2, 5]]]

预期输出2 #

[1, 3, 4, 8, [2, 2, 5, 10, [1, 2, 5]], [2, 2, 5, 10, [1, 2, 5, 7]], [2, 5, [3, 3, 5]]]

问题原因 #

直接使用递归函数作为sorted的key会触发TypeError，因为Python默认不支持整数与列表直接比较。我们需要将所有元素转换为可统一比较的结构，同时递归处理嵌套子列表。

解决方案 #

通过递归函数将每个元素转换为带类型标记的元组，确保整数与列表可按规则比较，同时完成子元素的内部排序：

def sort_key(element):
    if isinstance(element, int):
        # 用(0, 数值)标记整数：0确保整数排在列表（标记为1）之前，数值用于升序比较
        return (0, element)
    else:
        # 递归处理每个子元素，得到可比较的结构
        processed_items = [sort_key(item) for item in element]
        # 对子元素排序：先按类型标记（整数在前），再按内容排序
        sorted_processed = sorted(processed_items, key=lambda x: (x[0], x[1]))
        # 用(1, 排序后的子元素结构)标记列表
        return (1, sorted_processed)

# 测试示例1
input1 = [[5, [2, 1], 3], [3, [8, 7], [2, 1, 3], 2], [[3, 2, 1], 3, -1]]
result1 = sorted(input1, key=sort_key)
print(result1)

# 测试示例2
input2 = [1, 4, 3, [[5, 7, 1, 2], 2, 5, 10, 2], 8, [2, 5, [5, 3, 3]], [2, 5, 10, 2, [1, 2, 5]]]
result2 = sorted(input2, key=sort_key)
print(result2)

方案说明 #

1. 类型标记：整数转换为(0, num)，列表转换为(1, sorted_substructure)，利用元组比较规则（先比较第一个元素，0<1）确保整数排在所有列表之前。
2. 递归处理：子列表内部的每个元素都会被递归转换，再统一排序，保证子列表内部符合“整数在前、升序排列”的规则。
3. 列表比较：两个列表的key是(1, [...])结构，元组会自动按内部排序后的子元素依次比较，完全符合“首元素优先、短列表更小”的规则。

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