如何优化基于自定义compare/sort函数的Python大表排序

原代码用了两层全量循环，时间复杂度是O(n²)，当n到10000的时候要执行1亿次操作，效率自然崩了。要适配大规模数据，必须换时间复杂度更低的排序算法，比如快速排序或者归并排序，它们的平均时间复杂度是O(n log n)，操作次数会比原方案少几个数量级。

快速排序实现思路（适配现有函数） #

快速排序的核心是选基准、分区、递归排序子数组，完全可以用给定的compare和sort函数实现：

• 选一个基准索引，遍历数组把比基准小的元素移到左边，大的留在右边
• 递归处理左右两个子区间
• 所有比较逻辑用compare(x,y)，交换逻辑直接调用sort(x,y)（因为sort内部已经做了compare判断，不满足才交换，刚好符合排序需求）

示例代码 #

def quick_sort(A, low, high):
    if low < high:
        pivot_pos = partition(A, low, high)
        quick_sort(A, low, pivot_pos - 1)
        quick_sort(A, pivot_pos + 1, high)

def partition(A, low, high):
    pivot_idx = high  # 取区间最后一个元素当基准
    left_ptr = low - 1
    for j in range(low, high):
        # 如果当前元素比基准小，就移到左指针的下一个位置
        if compare(j, pivot_idx):
            left_ptr += 1
            sort(left_ptr, j)
    # 把基准元素放到正确的分区位置
    sort(left_ptr + 1, pivot_idx)
    return left_ptr + 1

# 调用方式：传入数组A和首尾索引
quick_sort(A, 0, len(A)-1)

效率对比 #

以n=10000为例，原方案需要1000010000=1e8次操作，而快速排序只需要约10000log₂(10000)≈1.4e5次操作，效率提升几百倍，完全能避免超时问题。

如果你的数据有大量重复元素，或者本身接近有序，还可以用三路快速排序进一步优化，但基础版快速排序已经足够应对绝大多数大规模场景。

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