帶負數的排序列表

我試圖在不修改現有列表或使用內置函數（如sort或sorted）對列表進行排序。遇到負數時遇到問題。例如列表進行排序，帶負數的排序列表

[7,1,-5,18]

產生

[1, -5, 7, 18]

，而不是

[-5, 1, 7, 18]

我的代碼：

lst = [7,1,-5,18] 
b = list() 
init = lst[0] 
for i in range(len(lst)): 
    b.append(lst[i]) 
    if b[i]<init: 
     tmp = init 
     b[i-1] = b[i] 
     b[i] = tmp 

print b

來源

2016-05-12 martinbshp

它的排序'[2,1， 0,3]'正確嗎？你已經跳到一個結論（你的程序不工作，如果列表包含負數），這是不保證。 –

由於排序的最佳方法是'O（logn）'，它不是桶排序，似乎無法在一次循環迭代中對列表進行排序，因此肯定會出現代碼錯誤。你想用什麼alghoritm？ –

@ m.antkowicz在O（log n）時間運行的排序算法？我不這麼認爲。 ;-)爲了對'n'元素上的序列進行排序，您應該至少查看每個元素一次以告訴它的發生位置，所以您不可能比'O（n）'更好（事實上，是這樣的算法，例如計數排序）。 –

您可以使用此選擇排序邏輯：

>>> l=[7,1,-5,18] 
>>> for i in range(len(l)): 
...  for j in range(i+1, len(l)): 
...   if l[j]<l[i]: 
...    l[i],l[j]=l[j], l[i] 
... 
>>> l 
[-5, 1, 7, 18]

來源

2016-05-12 07:31:50 ritesht93

謝謝ritesh93。這工作。 – martinbshp

這裏的問題是，你要追加值到列表的末尾，然後移動它們一個位置向左如果他們比以前的元素小。在更改列表中元素的位置後，您必須檢查是否需要再次移動。

一步一步來，這是發生了什麼：

remaining elements to sort | "sorted" list | what happens 
7,1,-5,18     []    
1,-5,18      [7]    first element enters the sorted list 
-5,18      [7,1]   2nd element enters the sorted list 
-5,18      [1,7]   7>1, so last element changes location 
18       [1,7,-5]  3rd element enters sorted list 
18       [1,-5,7]  7>-5, last element changes location 
[]       [1,-5,7,18]  instead of checking whether 1>-5, the 4th 
              element enters the list

這可以很容易地通過改變if的循環，像這樣被固定：

lst = [7,1,-5,18] 
b = list() 
for i in range(len(lst)): 
    b.append(lst[i]) 
    while i>0 and b[i]<b[i-1]: 
     b[i], b[i-1] = b[i-1], b[i] 
     i-= 1 

print b

來源

2016-05-12 07:39:29

帶負數的排序列表

回答

相關問題