2017-12-27 358 views
3
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 

如何提高代碼?

+1

你輸入'mas'包含字符串,而不是整數。因此你有一個詞典編排:'2'在'8'之前。 – MrT

+1

注意:您的'n'變量未被使用。也許'mas = input()。split()[:n]'?或者'mas = [int(item)for input in()。split()[:n]]'還包含解決方案嗎? – CristiFati

回答

1

您的代碼可能工作得很好。我還沒有測試它。 (但現在我看起來正確)

你的錯誤是你放棄了你的第一個輸入。所以,你應該使用你自己的代碼:

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

你只需要一個輸入。

此外,要排序的字符串,不一定是數字,所以你可以希望做到這一點:

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

您的快速排序實現似乎是正確的,但您忘記將輸入轉換爲整數。你正在排序字符串。

附註:不要忘記,樞軸選擇策略在快速排序算法中非常重要。你的「第一個元素作爲樞軸」方案類似於Lomuto partition scheme,對於有序或幾乎有序的序列,其容易降解爲O(n^2)