Python使用快速排序(quick sort)无法对数组排序问题求助

问题排查 #

你的代码存在两个核心问题导致无法正常完成排序：

• 递归调用逻辑错误：partition函数返回的j是基准元素最终落位的正确下标，该位置的元素已经无需再参与排序，因此左半段递归的右边界应为j-1而非j，否则会进入无限递归导致栈溢出。
• 冗余的哨兵元素未清理：你为了避免边界判断给数组追加了math.inf作为哨兵，但最终输出结果时没有删除这个额外元素，会导致排序结果多了无效的无穷大值。

修复后完整代码 #

# QUICK SORT 
import math

a = [34, 1, 3, 90, 34, -1, -4,78, 6, 55, 20, -65]
a.append(math.inf)

def partition(l,h,a):
    p = l
    i = l+1
    j = h
    while i<j:
        while a[i] < a[p]:
            i += 1
        while a[j] > a[p]:
            j -= 1
        if i<j:
            a[i],a[j] = a[j],a[i]
    a[p],a[j] = a[j],a[p]
    return j

def quick(l,h,a):
    if l<h:
        j = partition(l,h,a)
        # 修复点1：左半段递归边界调整为j-1
        quick(l,j-1,a)
        quick(j+1,h,a)

quick(0,len(a)-1,a)
# 修复点2：删除末尾追加的哨兵元素
a.pop()
print(a)

运行输出 #

[-65, -4, -1, 1, 3, 6, 20, 34, 34, 55, 78, 90]

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