如何在原地Quicksort中实现列表的列表的多规则比较逻辑？

你的代码存在以下几个关键问题：

• 输入读取错误：当前read_input函数将所有元素存入一维列表，而我们需要的是列表的列表（每个元素为[name, score1, score2]子列表）；同时score1和score2需转为整数，否则字符串比较会与数值比较结果冲突（比如字符串"100"会被判定为小于"80"）。
• 比较函数逻辑错误：compare函数第三个条件存在笔误（l1[0] > l1[0]），且判断逻辑与name升序的规则不符，正确判断应为l1[0] < l2[0]。
• 快排递归调用位置错误：递归调用应在分区循环结束后执行，而非每次交换元素后立即递归，否则会导致重复递归、降低效率甚至出错。

import random

def compare(l1, l2):
    # 按规则判断l1是否应排在l2前面
    if l1[1] > l2[1]:
        return True
    elif l1[1] == l2[1]:
        if l1[2] < l2[2]:
            return True
        elif l1[2] == l2[2]:
            # name升序，字典序小的在前
            return l1[0] < l2[0]
    return False

def quicksort(A, l=0, r=None):
    if r is None:
        r = len(A) - 1
    if l >= r:
        return
    # 随机选择基准元素，避免最坏情况
    pivot_idx = random.randint(l, r)
    q = A[pivot_idx]
    # 将基准元素移到末尾，简化分区逻辑
    A[pivot_idx], A[r] = A[r], A[pivot_idx]
    i = l - 1
    # 遍历分区，将小于等于基准的元素移到左侧
    for j in range(l, r):
        if compare(A[j], q):
            i += 1
            A[i], A[j] = A[j], A[i]
    # 将基准元素放到正确位置
    A[i+1], A[r] = A[r], A[i+1]
    # 递归排序左右子数组
    quicksort(A, l, i)
    quicksort(A, i+2, r)
    return A

def read_input():
    k = int(input())
    values = []
    while k > 0:
        n = input().split()
        # 转为[name, 整数score1, 整数score2]的子列表
        values.append([n[0], int(n[1]), int(n[2])])
        k -= 1
    return values

# 测试执行
if __name__ == "__main__":
    arr = read_input()
    quicksort(arr)
    for item in arr:
        print(item[0])

方式1：利用元组的比较特性 #

Python中元组会按元素顺序依次比较，我们可以为每个元素生成排序键元组，通过比较键元组判断顺序。针对你的排序规则，键元组可定义为(-score1, score2, name)：

• -score1：通过负号实现score1降序（元组默认升序，负号后大的score1对应键更小，会排在前面）
• score2：直接使用原值实现升序
• name：直接使用原值实现升序

修改后的compare函数更简洁：

def compare(l1, l2):
    key1 = (-l1[1], l1[2], l1[0])
    key2 = (-l2[1], l2[2], l2[0])
    # 键小的元素优先级更高，应排在前面
    return key1 < key2

方式2：返回数值型比较结果（类似传统cmp函数） #

让compare函数返回-1、0、1，分别表示l1在l2前、两者相等、l1在l2后，再在快排分区逻辑中根据返回值判断：

def compare(l1, l2):
    if l1[1] > l2[1]:
        return -1  # l1优先级更高，排在前面
    elif l1[1] < l2[1]:
        return 1
    else:
        if l1[2] < l2[2]:
            return -1
        elif l1[2] > l2[2]:
            return 1
        else:
            if l1[0] < l2[0]:
                return -1
            elif l1[0] > l2[0]:
                return 1
            else:
                return 0

对应的快排分区逻辑需调整：

# 当q应排在A[i]前面时，i后移
while compare(q, A[i]) < 0:
    i += 1
# 当A[j]应排在q前面时，j前移
while compare(A[j], q) > 0:
    j -= 1

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