Quicksort - 故障確定樞軸

我想了解快速排序，我得到的一般想法，但我遇到了以下問題的麻煩。是否有一種簡單的方法可以在每次迭代後根據數組來確定使用哪個數據透視表？Quicksort - 故障確定樞軸

Consider the following array and its state after iterations of QuickSort on the array: 

Initial Array: 32, 12, 17, 73, 40, 88, 16, 75 
After Iter 1: 32, 12, 17, 40, 16, 73, 88, 75 
After Iter 2: 12, 16, 17, 40, 32, 73, 88, 75 
After Iter 3: 12, 16, 17, 40, 32, 73, 88, 75 
After Iter 4: 12, 16, 17, 32, 40, 73, 88, 75 
After Iter 5: 12, 16, 17, 32, 40, 73, 75, 88

命名此QuickSort執行中使用的數據透視選擇策略。

提示：檢查在每個階段選擇哪個值作爲關鍵點。記住 QuickSort首先在之前對左子陣列及其左子陣列進行遞歸排序，然後對右子陣列進行排序。

來源

2012-10-31 Dawson

它正在使用選擇中間值的最具成本效益的解決方案。這很容易選擇，並且在數據已經排序（或大部分排序）時效率很高。 – paddy

選擇任何元素作爲主點，然後在第一次迭代中，所有小於主點的元素都放置在主點的左側，並且如果它們已經不在主點的右側，則向右更大。這意味着如果需要，也可以在數組中向前交換樞軸。瞭解這一點並觀察迭代應該有助於確定關鍵點。

例如，在你上面的例子中，我相信中間元素被選爲pivot，即73.在第一次迭代之後，所有比它小的元素被移動到左邊，並且大於它被移動到正確的位置。

來源

2012-10-31 07:09:39 fayyazkl

謝謝，這就是我一直在尋找的。 – Dawson

歡迎您。請記住，這只是選擇樞軸的方式之一。一般意圖是理想的是總是將數組分成兩半。如果它主要是這樣，那麼我們實現（nlogn）平均案例時間。如果不是，我們可能會遇到最壞的情況。 – fayyazkl

Quicksort - 故障確定樞軸

回答

相關問題