快速排序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

你的代码可能很有用。我还没有测试它。（但现在我知道了，这似乎是正确的）

你的错误是你放弃了你的第一个输入。所以，你应该使用你自己的代码如下：

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

你只需要一个输入。你知道吗

此外，您正在排序字符串，不一定是数字，因此您可能希望执行以下操作：

mas = input().split()
print(*quicksort([int(item) for item in mas]))

Answer 2

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

作为旁注：不要忘记在快速排序算法中，轴心选择策略是非常重要的。您的“第一个元素作为轴心”方案类似于Lomuto partition scheme，对于有序或几乎有序的序列，它很容易退化为O(n^2)。你知道吗