python - Quicksort Python排序麻烦

Question

def quicksort(mas):
    if mas:
        mid = mas[0]
        menshe = [i for i in mas[1:] if i < mid]
        bolshe = [i for i in mas[1:] if i >= mid]
        return quicksort(menshe) + [mid] + quicksort(bolshe)
    else: 
        return mas

n = int(input())
mas = input().split()
print(*quicksort(mas))

它在某些测试中失败了，例如

input:
3
8 21 22
output:
21 22 8

如何改进代码？

Answer 1

您的快速排序实现似乎是正确的，但您忘记了将输入转换为整数。您正在对字符串进行排序。

附带说明:不要忘记枢轴选择策略在快速排序算法中非常重要。您的“第一个元素作为枢轴”方案类似于 Lomuto partition scheme对于有序或几乎有序的序列，它很容易退化为 O(n^2)。