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

如何提高代码质量？

- Denis K

---

你的输入 mas 包含字符串，而不是整数。因此你有一个字典排序：2 在 8 之前。 - Mr. T

注意：您的 n 变量未使用。也许可以使用 mas = input().split()[:n]？或者使用 mas = [int(item) for item in input().split()[:n]] 来包含解决方案？ - CristiFati

Answer 1

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

另外需要注意的是：在快速排序算法中，选择枢轴的策略非常重要。你的“以第一个元素作为枢轴”的方案类似于Lomuto partition scheme，在有序或接近有序的序列中很容易退化为O(n^2)。

- DAle

Answer 2

你的代码很可能可以工作。我还没有测试它。（但现在我已经测试了，似乎是正确的）

你的错误在于舍弃了第一个输入。因此，你应该像这样使用你自己的代码：

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

你只需要一个输入。 此外，你正在对字符串进行排序，并不一定是数字，所以你可能想要这样做：

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

- quamrana