如何适配插入排序算法对含字符串与整数的嵌套列表排序？

要实现你需要的排序规则——按子列表整数降序排列，整数相同时按字符串升序排列，只需调整插入排序中的比较逻辑即可。插入排序的核心是将未排序元素逐个插入到已排序序列的正确位置，关键在于判断「当前元素应该插在哪里」的条件。

调整后的插入排序代码 #

def custom_insertion_sort(lst):
    # 从第二个元素开始处理未排序部分
    for i in range(1, len(lst)):
        current_item = lst[i]
        j = i - 1
        # 核心判断逻辑：向前遍历已排序序列，找到插入位置
        # 满足以下任一条件时，将已排序元素后移：
        # 1. 已排序元素的整数 < 当前元素的整数（降序要求）
        # 2. 整数相等，但已排序元素的字符串 > 当前元素的字符串（升序要求）
        while j >= 0 and (lst[j][1] < current_item[1] or (lst[j][1] == current_item[1] and lst[j][0] > current_item[0])):
            lst[j + 1] = lst[j]
            j -= 1
        # 插入当前元素到正确位置
        lst[j + 1] = current_item
    return lst

# 测试示例列表
user_list = [
    ['Jo Marat', 3],
    ['titi toto', 3],
    ['Mr DoD', 6],
    ['Zebrra Benda', 1]
]

sorted_list = custom_insertion_sort(user_list)
print(sorted_list)

代码说明 #

• 外层循环遍历从索引1开始的所有元素（第一个元素默认属于已排序序列）。
• 内层while循环的条件是实现自定义排序的关键：
  • 当已排序元素的整数小于当前元素的整数时，说明当前元素应该排在更前面，因此将已排序元素后移。
  • 当两者整数相等时，比较字符串：如果已排序元素的字符串比当前元素大，当前元素应该排在前面，同样后移已排序元素。
• 当退出while循环时，j+1就是当前元素的正确插入位置，完成插入操作。

运行上述代码后，输出结果与你期望的完全一致：

[['Mr DoD', 6], ['Jo Marat', 3], ['titi toto', 3], ['Zebrra Benda', 1]]

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