Python的快速排序沒有排序右側

這是我輸入：Python的快速排序沒有排序右側

[3, 9, 8, 4, 6, 10, 2, 5, 7, 1]

這裏是我的代碼（這還沒有實現的另一個原因名爲count）：

def Count(num_list): 
global comparisons 


if len(num_list) > 1: 
    pivot = num_list[0] 
    print "Pivot value is: %s, current list is: %s" % (pivot, num_list) 
    i = 1 
    j = 1 

    for j in range(len(num_list)): 
     if num_list[j] < pivot: 
      print "Swapping %s and %s" % (num_list[i], num_list[j]) 
      num_list[i], num_list[j] = num_list[j], num_list[i] 
      print "List is now: %s" % (num_list) 
      i += 1 


    num_list[0], num_list[i-1] = num_list[i-1], num_list[0] 
    print "List before next recursive step: %s" % num_list 

    Count(num_list[:(len(num_list)/2)]) 
    Count(num_list[(len(num_list)/2):]) 

print "List at the end of function: %s" % (num_list)

我得到以下結果如下：

[1, 2, 3, 4, 6, 10, 9, 5, 7, 8]

當我看到所有我所做的調試打印語句時，我發現它並沒有將右半部分放在一起它左側的方式，但我無法弄清楚。

來源

2016-12-15 Richard Rubalcava

http://codexpi.com/quicksort-python-iterative-recursive-implementations/在谷歌上30秒。 – Pythonista

@Pythonista這不是他的問題，因爲這將脫離主題。他的問題是關於他的具體實施。 – Natecat

您的代碼只會將列表分成兩部分，一部分高於主鍵，另一半低於主鍵。它不排序列表。 – Natecat

@Natecat和@rcgldr謝謝你指點我正確的方向。我的代碼只是第一次排序，因爲遞歸調用正在排序從未返回的數組的分片副本。這違背了快速排序的定義，即排序。我更新到以下，它的工作原理。

def Count(num_list, first, last): 
    if first < last: 
     global comparisons 
     comparisons += len(num_list)-1 

     pivot = num_list[first] 
     i = first + 1 

     # quick sort 
     for j in range(first+1,last): 
      if num_list[j] < pivot: 
       num_list[i], num_list[j] = num_list[j], num_list[i] 
       i += 1 

     # swap pivot with border index 
     num_list[first], num_list[i-1] = num_list[i-1], num_list[first] 

     # recurse 
     Count(num_list, first, i-1) 
     Count(num_list, i, last)

來源

2016-12-15 16:42:35

Python的快速排序沒有排序右側

回答

相關問題