快速排序的Python排序麻烦

2017-12-27 414 views 3 likes

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))

它未能对一些测试，例如快速排序的Python排序麻烦

input: 
3 
8 21 22 
output: 
21 22 8

如何提高代码？

来源

2017-12-27 Denis K

你输入'mas'包含字符串，而不是整数。因此你有一个词典编排：'2'在'8'之前。 – MrT

注意：您的'n'变量未被使用。也许'mas = input（）。split（）[：n]'？或者'mas = [int（item）for input in（）。split（）[：n]]'还包含解决方案吗？ – CristiFati

回答

您的代码可能工作得很好。我还没有测试它。（但现在我看起来正确）

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

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

你只需要一个输入。

此外，要排序的字符串，不一定是数字，所以你可以希望做到这一点：

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

来源

2017-12-27 14:06:20 quamrana

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

附注：不要忘记，枢轴选择策略在快速排序算法中非常重要。你的“第一个元素作为枢轴”方案类似于Lomuto partition scheme，对于有序或几乎有序的序列，其容易降解为O(n^2)。

来源

2017-12-27 14:06:12 DAle

快速排序的Python排序麻烦

回答

相关问题