快速排序遞歸

我試圖追溯這一快速排序算法：快速排序遞歸

https://pythonschool.net/data-structures-algorithms/quicksort/

但有不同的組數字 - [6,2,8,4,3,7,10]

我沒事，一旦算法的左側是排序的，但我不明白遞歸類。

一旦左側完成，start = 0和end = 0，以下行運行：

quicksort(myList, pivot+1, end)

當我打印出來的快速排序功能的啓動和終止值：

Start = 2 and End = 1 
Start = 3 and End = 2 
Start = 4 and End = 6

我不明白start和end如何更改爲這些值。

任何人都可以解釋如何和爲什麼？

來源

2017-02-23 afergie

您可能會考慮更容易實現快速排序。例如，

my_list = [52,8,45,43,6,56,76,36,54,12,34,98,41,30] 

def quicksort(arr): 
    high = [] 
    low = [] 
    pivot_list = [] 

    if len(arr) <= 1: 
     return arr 
    else: 
     pivot = arr[0] 
     for i in arr: 
      if i < pivot: 
       low.append(i) 
      elif i > pivot: 
       high.append(i) 
      else: 
       pivot_list.append(i) 
     high = quicksort(high) 
     low = quicksort(low) 

    return low + pivot_list + high 

print quicksort(my_list) 

[6, 8, 12, 30, 34, 36, 41, 43, 45, 52, 54, 56, 76, 98]

這個相當簡單的實現很容易解釋。您正在根據主鍵的任意選擇對列表進行分區。在這種情況下，arr[0] = 52。然後你遍歷整個列表，如果元素大於pivot（52），你把它放到'high'分區，如果它小於52，你就把它放到'low'分區。在通過一個運行後這一點（我們運行high = quicksort(high)之前），我們有

low = [8, 45, 43, 6, 36, 12, 34, 41, 30] 
high = [56, 76, 54, 98] 
pivot_list = [52]

然後，我們對「低」和「高」的分區上運行此快速排序功能。例如，對於高分區，pivot = arr[0] = 56。我們遍歷高分區，如果元素小於主分區（56），我們將它放在一個新的低分區組中，該分區組是高分區的子組。如果元素大於56，那麼我們把它放在新的高分區中，高分區是高分區的子組。你可以把它看作是從一個我們想要排序的列表開始，然後分成一個高分區和一個低分區，然後每個分區分支到他們自己的高分區和低分區。這就是遞歸進來的地方

來源

2017-02-23 15:12:14 Nemo

快速排序遞歸

回答

相關問題