快速排序分析和行爲

我閱讀有關本名爲算法第四版羅伯特·塞奇威克快速排序algoritm。快速排序分析和行爲

快速排序是受歡迎，因爲它不是難以實施，工作以及用於各種不同類型的輸入數據中的，並且是實質上大於在典型的應用中任何其他排序方法更快。快速排序算法的所希望的特徵是，它是就地（僅使用一個小的輔助棧），而且它要求上的平均時間正比於N日誌N到排序的算法長度 N.無的陣列，我們迄今已考慮結合這兩個屬性。

此外，快速排序比其他大多數其他排序算法具有更短的內循環，這意味着它在理論上快速實踐以及。它的主要缺點是，它是在一定的照顧參與實施，一定要避免糟糕表現感脆弱。

我上面的文字問題是

什麼是筆者的「只使用一個小的輔助棧」是什麼意思？
什麼是筆者的「快速排序比其他大多數排序算法更短的內環」是什麼意思？

要求用簡單的例子來解釋。

感謝

來源

2016-06-10 venkysmarty

1什麼是筆者的「只使用一個小的輔助棧」是什麼意思？

作者意味着除了要排序的數據外，還需要很少的額外內存。所以在排序過程中生成的數據結構沒有大的開銷。

什麼作者通過「快速排序具有比大多數其他排序算法更短的內環」呢？

筆者指在最內層循環相當視圖中執行指令的數目，這是例如一個好處cpu緩存。

在內部循環僅索引遞增下面的代碼/遞減。並且檢查循環條件。

作爲一個例子我參加wikipedia

algorithm quicksort(A, lo, hi) is 
    if lo < hi then 
     p := partition(A, lo, hi) 
     quicksort(A, lo, p – 1) 
     quicksort(A, p + 1, hi) 

algorithm partition(A, lo, hi) is 
pivot := A[lo] 
i := lo – 1 
j := hi + 1 
loop forever 
    do 
     i := i + 1 
    while A[i] < pivot 
    do 
     j := j – 1 
    while A[j] > pivot 
    if i >= j then 
     return j 
    swap A[i] with A[j]

來源

2016-06-10 11:08:50 MrSmith42

通過快速排序的實現，最壞的情況是幾乎n次遞歸調用，佔用比陣列更多的空間。避免使用大型堆棧空間的常見工作是僅在較小的分區上使用遞歸，然後環回並拆分較大的分區，這是遞歸和迭代的混合。最壞情況下的時間複雜度仍然是O（n^2）。 – rcgldr

@rcgldr：這個問題和我的答案都不是關於實現的優化。這就是爲什麼我發佈了維基百科的示例實現，它更喜歡易於理解的方法，而不是最優化的方法。 – MrSmith42

function QuickSort(Array, Left, Right) 
var 
    L2, R2, PivotValue 
begin 
Stack.Push(Left, Right);  // pushes Left, and then Right, on to a stack 
while not Stack.Empty do 
begin 
    Stack.Pop(Left, Right); // pops 2 values, storing them in Right and then Left 
    repeat 
     PivotValue := Array[(Left + Right) div 2]; 
     L2 := Left; 
     R2 := Right; 
     repeat 
      while Array[L2] < PivotValue do // scan left partition 
       L2 := L2 + 1; 
      while Array[R2] > PivotValue do // scan right partition 
       R2 := R2 - 1; 
      if L2 <= R2 then 
      begin 
       if L2 != R2 then 
        Swap(Array[L2], Array[R2]); // swaps the data at L2 and R2 
       L2 := L2 + 1; 
       R2 := R2 - 1; 
      end; 
     until L2 >= R2; 
     if R2 - Left > Right - L2 then // is left side piece larger? 
     begin 
      if Left < R2 then 
       Stack.Push(Left, R2); 
      Left := L2; 
     end; 
     else 
     begin 
      if L2 < Right then // if left side isn't, right side is larger 
       Stack.Push(L2, Right); 
      Right := R2; 
     end; 
    until Left >= Right; 
end; 
end;

提到的實施是什麼筆者通過「只使用一個小的輔助棧」是什麼意思？

，你不需要第二個數組存儲（如歸併）是相同的內存

什麼是筆者的「快速排序比大多數更短的內環平均計算在內其他排序算法「？

快速排序的非常快的部分是內環（//向左掃描分區和//掃描的右分區），因爲它只是增加和檢查......不多。

來源

2016-06-10 11:10:23 Thomas

作者所說的「只使用一個小的輔助堆棧」是什麼意思？

您還需要考慮quick-sort是in-place排序算法。

in-place指：

此in-place特徵大大降低了存儲需求。
它使用恆定數量的存儲（讀取：固定數量的額外變量）以便於排序過程。

因此，由於存儲量小而固定，所以quick-sort「只使用一個小的輔助堆棧」。

作者認爲「quicksort比其他大多數排序算法有更短的內部循環」是什麼意思？

由此可能意味着內部循環內部的邏輯很簡單，因此需要的代碼較少。這個「較短的內部循環」不應與循環迭代的次數相混淆。因爲在任何級別的遞歸樹上，迭代的總數只會是「n」。

來源

2016-06-10 11:25:58 sameerkn

1作者是什麼意思的「只使用一個小的輔助堆棧」？

在理想的情況下，快速排序在堆棧上使用O（log2（n））空間，最壞的情況是它在堆棧上使用O（n）空間，佔用比排序數組更多的空間。

作者認爲「quicksort比其他大多數排序算法有更短的內部循環」是什麼意思？

這可能沒有多大意義的現代系統上，因爲任何合理大小的內循環，適合大多數處理器的代碼緩存中。取決於分支預測，條件分支將影響管線性能。

快速排序...比典型應用中的任何其他排序方法快得多。

這是不正確的，在最好的情況下，快速排序只比合併排序更快（少於10％），而在最差情況下，O（n^2）與O （n log（n））。合併排序的主要問題是它需要一個大小相同的臨時數組或原始數組大小的1/2。

來源

2016-06-13 09:25:07 rcgldr

快速排序分析和行爲

回答

相關問題