Python中的Quicksort工具運行無停止

這是我的快速排序算法。很簡單Python中的Quicksort工具運行無停止

x = 0 
def swap(list, a, b): 
    temp = list[a] 
    list[a] = list[b] 
    list[b] = temp 
    return list 
def quicksort2(list, left, right): 
    if right > left: 
     global x 
     x = x + 1 
     print x , list, left, right 
     l = left+1 
     r = right 
     while l <= r : 
      while list[l] < list[left]: 
       l = l + 1 
      while list[r] > list[left]: 
       r = r - 1 
      if l < r: 
       list = swap(list, l, r) 
     list = swap(list, left, r) 
     list = quicksort2(list, left, r-1); 
     return quicksort2(list, r+1, right); 
    return list

但是，當我運行測試用例

b = list([1, 2, 2, 3, 4, 5, 6, 12, 6, 32]) 
quicksort2(b, 0, len(b)-1)

結果是

1 [1, 2, 2, 3, 4, 5, 6, 12, 6, 32] 0 9 
2 [1, 2, 2, 3, 4, 5, 6, 12, 6, 32] 1 9

，並在此停... 任何人有任何理由...

來源

2013-03-22 Thinh VoXuan

您的嘗試是不是很簡單，你可能會想只是看這裏：http://en.literateprograms.org/Quicksort_(Python）你的代碼是很複雜以上 – jamylak 2013-03-22 02:46:28

在附註中，'list [a]，list [b] = list [b]，list [a]'是做交換的pythonic方式 – karthikr 2013-03-22 03:18:10

您是否試圖在調試器下跟蹤程序執行...？

的while l <= r循環將永遠運行下去，因爲r

left == 1
l == 2
r == 2

和

l不遞增，因爲list[2]不小於list[1]
r不減少任何更長的時間，因爲list[2]不超過list[1]
沒有交換做更大，因爲l不小於r
和循環將繼續，因爲l仍等於r .......

來源

2014-03-19 23:55:20 CiaPan

我si mply修改了你的代碼。發現了一些錯誤，一些已經被其他人提到了。其餘的我不會去經歷。但是，您不必返回修改後的列表，因爲Python中的列表總是按引用傳遞。

這應該是工作：

def quicksort2(list, low, high): 
    global x 
    x = x + 1 
    print x , list, low, high 

    l = low 
    r = high 
    mid = list[(r + l)/2] 
    while l <= r: 
     while list[l] < mid: l += 1 
     while list[r] > mid: r -= 1 
     if l <= r: 
     list[l], list[r] = list[r], list[l] #swap(r,l) 
     l += 1 
     r -= 1 

    if r > low: quicksort2(list, low, r); 
    if l < high: quicksort2(list, l, high); 


if __name__ == '__main__': 
    x = 0 
    b = [1, 2, 2, 3, 4, 5, 6, 12, 6, 32] 
    quicksort2(b, 0, len(b)-1) 
    print b

來源

2014-03-20 00:48:45 JHolta

Python中的Quicksort工具運行無停止

回答

相關問題