QuickSort正在返回正確的值，但沒有排序

我很努力地理解爲什麼我的QuickSort 返回正確的排序值，但結果數組未正確排序。QuickSort正在返回正確的值，但沒有排序

def qSort(array): 
    n = len(array) 
    if (n == 1 or n ==0): 
      return array 
    p_index = partition(array) 
    p_value = array[p_index] 
    return(qSort(array[0:p_index]) + [p_value] + qSort(array[p_index+1:n])) 

def partition(array): 
    pivot = array[0] 
    i = 1 
    for j in xrange(1,len(array)): 
     print j 
     if array[j] < pivot: 
      tmp = array[j] 
      array[j] = array[i] 
      array[i]=tmp 
      i += 1 
    tmp = array[i-1] 
    array[i-1] = pivot 
    array[0] = tmp 
    return i-1

下面是一些示例輸出：

>>> q = [5,4,3,2,1] 
>>> qSort(q) 
[1, 2, 3, 4, 5] 
>>> q 
[1, 4, 3, 2, 5]

預先感謝您！

來源

2013-07-20 tonydx

這是因爲您正在編制return聲明中的新列表。

return(qSort(array[0:p_index]) + [p_value] + qSort(array[p_index+1:n]))

如果qSort函數達到鹼的情況下，它返回一個列表，該列表的值與[p_value]和返回作爲list。您不需要對list中的任何地方進行更改。

當你打電話給你qSort功能遞歸，你給它的列表的片段，函數返回的基本情況，你再追加到pivot和其他遞歸調用，從而產生一個新的列表清單。

看看是通過改變你的qSort功能發生在

def qSort(array): 
    n = len(array) 
    if (n == 1 or n ==0): 
      return array 
    p_index, array = partition(array) 
    p_value = array[p_index] 
    returnVal = qSort(array[0:p_index]) + [p_value] + qSort(array[p_index+1:n]) 
    print "Returning:", returnVal, "Original Array:", array 
    return returnVal

輸出 -

>>> q = [5,4,3,2,1] 
>>> qSort(q) 
Returning: [2, 3] Original Array: [2, 3] 
Returning: [2, 3, 4] Original Array: [2, 3, 4] 
Returning: [1, 2, 3, 4] Original Array: [1, 4, 3, 2] 
Returning: [1, 2, 3, 4, 5] Original Array: [1, 4, 3, 2, 5] 
[1, 2, 3, 4, 5]

以反映您最初的list的變化，你必須做q = qSort(q)的選項。

P.S - 設置一個隨機索引而不是第一個值對於您的快速排序功能會更好。請參閱Choice of Pivots上的here位。

來源

2013-07-20 08:07:28

這似乎不工作'q = qSort（array [0：p_index]）+ [p_value] + qSort（array [p_index + 1：n]）' 'return（q）' – tonydx

You're還在制定新的名單。如果您需要在原地排序列表，您需要在代碼中對其進行更改，或執行'q = qSort（q）'。 –

@tonydx：您需要在IDLE中執行'q = qSort（q）'。 –

應用函數回至q

Q =的qsort（Q）

來源

2013-07-20 08:08:49

在Python，切片和組合列表創建新的列表。如果您希望遞歸調用在單個列表中就地運行，請將列表和邊界傳遞給調用，並且不要從該函數返回任何內容。例如：

def qsort(array, low, high): 
    if high-low < 2: 
     return 

    # Choose pivot, do partition within bounds 

    if partition > low: 
     qsort(array, low, partition) 
    if partition < high: 
     qsort(array, partition+1, high)

然後只需撥打qsort(a, 0, len(a))對數組進行排序。

來源

2013-07-20 08:23:39

如果你想要返回數組並且排序合適，你應該在返回之前讓數組等於結果而不是新建一個。你可以通過改變你的return語句：

array[:] = qSort(array[0:p_index]) + [p_value] + qSort(array[p_index+1:n]) 
    return array

注意

array = qSort(array[0:p_index]) + [p_value] + qSort(array[p_index+1:n])

也不管用，因爲LHS變量將作爲局部變量進行處理。

來源

2013-10-08 13:21:23 Paul

QuickSort正在返回正確的值，但沒有排序

回答

相關問題