快速排序樞軸

Question

排序下面陣列的使用快速排序，

[6, 11, 4, 9, 8, 2, 5, 8, 13, 7] 

樞軸應選擇爲第一和最後一個元素，即(a[0] + a[size - 1])/2 (rounded down)的算術平均值。

顯示所有重要步驟，例如分區和對算法的遞歸調用。

---

我明白如何使用快速排序來排序數組，但是我不知道如何計算數據透視。

是對樞軸通過6 + 7 = 13然後13/2 = 6.5計算（向下舍入爲6），從而所述樞轉是2（即，第六元件）？

我知道左側顯示的元素少於樞軸，右側顯示大於樞軸的元素，分區將重複此步驟對子數組進行排序。

任何幫助將不勝感激。

Answer 1

對於快速排序，樞軸可以是任何你想要的元素。 結賬Wikipedia。

的問題很容易通過選擇任一一個隨機索引用於樞軸，選擇選擇位數的中間索引的分區的或（特別是對於較長的分區）解決了第一，中間和最後分區用於樞軸的元件從而

三種選擇：

• 網絡連接第一個元素
• 中間元素
• 第一個，中間和最後一個的中間值。

而且在使用第一和最後一個元素的意思是你的情況下值會給你：

6 + 7 = 13 
13/2 = 6.5 
6.5 rounded down = 6 

Answer 2

順便說一句，問題的措辭，樞軸應該只是6，不一定是數組中的第6項。

這是最明顯的例子，因爲如果在數組中只有3個項目，例如算術平均值大於3，那麼您將沒有選擇的主點，因爲沒有該項目指數。

注意：小心你索引數組中的元素的方式。你說第6個元素是'2'，如果你的編程語言開始索引爲0，那麼它可能是'5'。

Answer 3

你的支點是6.你的支點不是第6個元素 現在你可以應用下面的算法。

function quicksort(array) 
var list less, greater 
if length(array) ≤ 1 
    return array // an array of zero or one elements is already sorted 
select and remove a pivot value pivot from array 
for each x in array 
    if x ≤ pivot then append x to less 
    else append x to greater 
return concatenate(quicksort(less), pivot, quicksort(greater)) 

Answer 4

從計算樞軸的位置並不重要，快速排序排序基於元素無論它們是否多於或少於樞軸。然後將樞軸放置在兩組之間（或多或少）。