找到quickSort算法的所有樞軸值

如果我想查找QuickSort的所有主軸值，我該在什麼時候停止分割子陣列？

QuickSort(A,p,r): 
    if p < r: 
     q = Partition(A,p,r) 
     Quicksort(A,p,q-1) 
     Quicksort(A,q+1,r) 

Partition(A,p,r): 
    x = A[r] 
    i = p-1 
    for j = p to r-1: 
    if A[j] ≤ x: 
     i = i + 1 
     swap(A[i], A[j]) 
    swap(A[i+1], A[r]) 
    return i+1

含義，如果我有一個數組： A = [9,7，5，11，12，2，14，3，10，6]

作爲快速排序打破了這種成其組成件...

A = [2,5，3] [12，7，14，9，10，11]

一個步驟以達到混亂的點...

A = [2,5] [7，12，14，9，10，11]

左側的子陣列在此停止嗎？還是它（quickSort）用5作爲最終的樞軸值進行最後一次調用quickSort？

對我來說，我們會繼續下去，直到所有的子陣列都是單個項目 - 但是我的一個同伴一直告訴我，這是有道理的。

來源

2017-10-17 Derp

所以，你只是想找到你的算法使用的樞軸值，直到它排序列表？ – gsamaras

@gsamaras是的！我想我已經擁有了它 - 但我想確定自己明白。我認爲他們是6,3,5,11,10,9,12 – Derp

@gsamaras這大多是一個*總體概念性問題，而不是一個編碼問題。 – Derp

樞軸爲你的例子將是：6, 3, 11, 10, 9, 12。關於

左側的子陣列在這裏停止嗎？

檢查源代碼總是最好的。當遞歸子陣列變爲[2, 5, 3]時，函數QuickSort將與p = 0和r = 2一起調用。讓我們繼續：Partition(A,0,2)將返回q = 1，所以接下來的兩個電話將是Quicksort(A,0,0)和Quicksort(A,2,2)。因此，Quicksort(A,0,1)永遠不會被調用，所以你永遠不會有機會檢查子陣列[2, 5] - 它已經被排序！

來源

2017-10-17 07:54:00

找到quickSort算法的所有樞軸值

回答

相關問題