Quicksort遞歸深度O（n）的堆棧空間不會導致stackoverflow？

在最壞情況下快速排序深度要求堆棧空間爲O（n）。爲什麼它在最壞的情況下不會導致大集合的堆棧溢出？（反向序列）Quicksort遞歸深度O（n）的堆棧空間不會導致stackoverflow？

2012-10-19 Rahul Kumar Dubey

使用第一個元素作爲數據透視表的快速排序實現是一個糟糕的實現。請注意，更好的方法是隨機取一個元素或選擇中間元素作爲關鍵點。 – amit

@amit：以中間元素爲中心也是可怕的，它不那麼糟糕，因爲它更難構建殺手級輸入。 –

@SteveJessop：我不同意。請注意，隨機數組與任何選擇具有完全相同的「最壞情況」變化 - 作爲隨機選定的元素。選擇第一個元素的問題是 - 真實生活數組被排序（或幾乎排序）的概率不是「1/n！」（你看過多少次已經排序了已經排序的數組的代碼？很多...），而我懷疑選擇中間元素的最壞情況數組的概率會大得多，如果有的話。這就是說 - 如果你害怕*攻擊* - 那麼應該避免任意的選擇。 – amit

如果您在主軸的兩側進行遞歸，那麼在最壞的情況下它確實會導致足夠大的數據堆棧溢出。這就是爲什麼沒有人在生產代碼中使用天真的QuickSort。

您可以對算法進行簡單的更改，以防止最壞情況下的堆棧使用。在每個分區之後，遞歸地快速排列「小一半」，然後迭代地循環執行「大一半」。這需要O(log n)額外的堆棧空間。如果你願意，你可以通過再次修改它來使它的堆棧空間和O(log n)額外的非堆棧空間成爲O(1)。將「大一半」推到預先分配的數組（或者您選擇的其他後進先出的數據結構）的末尾，循環執行「小一半」，當你點擊底部時彈出最後一個元素關閉數據結構做下一步。

您可以進行進一步更改以避免Omega(n^2)最壞情況運行時間。但它不再是一個天真的QuickSort，它是一個QuickSort-with-median-of-medians-pivot-selection，或者一個Introsort，或者其他的東西。

來源

2012-10-19 09:12:43

QuickSort-with-median-of-medians-pivot-selection仍然是快速排序，對於某些輸入仍然表現出相同的最壞情況行爲。 –

@Konrad：沒有。中位數的中位數是一個真正的線性時間選擇算法，其樞軸選擇算法（這是你在快速排序中使用的算法）發現數據的第30和第70百分位數之間的關鍵點，這足以避免最壞的情況QuickSort和QuickSelect。你是否想過「3中位數」，雖然需要一些棘手的構造，但確實有殺手案例？ –

你當然是對的。我把它當作三位數中位數，這是一種不同的（恆定時間）方法。 –

如果序列顛倒（最差的情況），可能會導致堆棧溢出。因爲數組對於內部函數堆棧可能太大。（例如，99,000,000個元素）您可以用stack數據結構替換遞歸。您將循環while (stck.empty() == false)

function quicksort(arr[0,1,...n-1]) 
    stack.push(pair(0, n - 1)) 
    while stack not empty 
      interval = stack.pop() 
      ... 
      ... 
      stack.push(interval(0, pivot - 1)) 
      stack.push(interval(pivot + 1, n - 1))

來源

2012-10-19 08:57:25

這不是問題。儘管它會停止堆棧溢出，但它不會改善O（n）空間消耗，這是一個嚴重的問題。 – delnan

@delnan'O（n）'堆棧空間的問題高度依賴於排序情況。它在好的案例和更糟糕的casa之間有所不同 – 2012-10-19 09:03:19

@delnan：那完全是*問題，這完全是關於堆棧溢出的問題。也許提問者也應該關心非堆棧額外的空間要求，但實際上並沒有問及它。 –

那麼爲什麼它亙古不變導致堆棧爲大套的訂單數據溢出最壞的情況下

它。爲什麼你會認爲它不？（但請注意，快速排序的最壞情況輸入取決於您選擇的樞軸，它通常不是反向序列 - 事實上，對於主軸的簡單選擇，另一個最壞情況輸入是已排序的序列，它）

但是現在排序算法的庫實現實際上很少快速排序，正是因爲這個原因。例如，C++ std::sort改爲使用introsort，這是一個修改後的快速排序，只要它遞歸得太深，就會切換到不同的排序算法。

來源

2012-10-19 09:11:49

Quicksort遞歸深度O（n）的堆棧空間不會導致stackoverflow？

回答

相關問題