Python自定义归并排序merge函数如何在不依赖内置函数时用key参数自定义比较规则

很多人会把key参数的用法和min、sorted这类内置函数绑定，觉得只有把key传给内置函数才能生效。实际上所有支持key的排序逻辑，底层规则完全一致：

• 对每个参与排序的元素，调用一次key函数，生成这个元素对应的「排序比较权重值」
• 整个排序流程里的所有大小判断，都基于这个权重值完成，和原元素本身的原生属性没有直接关系
• 最终返回的排序结果始终是原始元素，不会返回转换后的权重值

针对merge函数的调整 #

当前的merge函数已经定义了key形参，但比较环节直接用了原元素的原生大小，没有接入key的转换逻辑，只需要替换比较环节的判断依据即可：

def merge(left, right, key=lambda x: x):
    ss = []
    while not (left == [] or right == []):
        # 计算两个队首元素对应的比较权重
        left_cmp_val = key(left[0])
        right_cmp_val = key(right[0])
        # 用权重值完成大小判断
        if left_cmp_val <= right_cmp_val:
            ss.append(left[0])
            left = left[1:]
        else:
            ss.append(right[0])
            right = right[1:]
    ss.extend(left)
    ss.extend(right)
    return ss

运行效果 #

和你之前写的selection_sort的行为完全对齐：

默认无自定义key的执行（按原元素升序）
merge([18, 23, 32], [7, 11, 55, 99])
输出：[7, 11, 18, 23, 32, 55, 99]

传入abs作为key（按元素绝对值升序）
merge([18, -23, 32], [7, -11, 55, 99], key=abs)
输出：[7, -11, 18, -23, 32, 55, 99]

传入lambda x: -x作为key（按元素值降序）
注意merge函数的输入前提：左右子列表本身必须已经按照对应key规则完成排序，传入符合要求的输入：
merge([32, 23, 18], [99, 55, 11, 7], key=lambda x: -x)
输出：[99, 55, 32, 23, 18, 11, 7]

补全归并排序的注意点 #

• 后续编写递归拆分、子列表排序的逻辑时，需要把同一个key参数从归并排序的入口函数一路透传到底层的merge比较环节，保证全流程的排序规则统一，避免出现拆分阶段用默认规则、合并阶段用自定义规则的逻辑错配。
• 不要把原元素替换成key转换后的值存入结果列表：我们只是借助key的转换结果完成比较判断，最终返回的是用户传入的原始元素，这一点和之前实现的selection_sort行为完全一致。

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