Can you summarize the following document?
        
  快速排序使用分治法(Divide and conquer)策略來把一個序列(list)分為較小和較大的2個子序列,然後遞迴地排序兩個子序列。  步驟為:  遞迴到最底部的判斷條件是數列的大小是零或一,此時該數列顯然已經有序。  選取基準值有數種具體方法,此選取方法對排序的時間效能有決定性影響。  在簡單的虛擬碼中,此演算法可以被表示為:

  上面簡單版本的缺點是,它需要formula_5的額外儲存空間,也就跟歸併排序一樣不好。額外需要的記憶體空間配置,在實際上的實作,也會極度影響速度和快取的效能。有一個比較複雜使用原地(in-place)分割演算法的版本,且在好的基準選擇上,平均可以達到formula_6空間的使用複雜度。  這是原地分割演算法,它分割了標示為"左邊(left)"和"右邊(right)"的序列部分,藉由移動小於codice_1的所有元素到子序列的開頭,留下所有大於或等於的元素接在他們後面。在這個過程它也為基準元素找尋最後擺放的位置,也就是它回傳的值。它暫時地把基準元素移到子序列的結尾,而不會被前述方式影響到。由於演算法只使用交換,因此最後的數列與原先的數列擁有一樣的元素。要注意的是,一個元素在到達它的最後位置前,可能會被交換很多次。  一旦我們有了這個分割演算法,要寫快速排列本身就很容易:  這個版本經常會被使用在命令式語言中,像是C語言。

  快速排序是二叉查詢樹(二元搜尋樹)的一個空間最佳化版本。不是循序地把資料項插入到一個明確的樹中,而是由快速排序組織這些資料項到一個由遞迴呼叫所隱含的樹中。這兩個演算法完全地產生相同的比較次數,但是順序不同。對於排序演算法的穩定性指標,原地分割版本的快速排序演算法是不穩定的。其他變種是可以通過犧牲效能和空間來維護穩定性的。  快速排序的最直接競爭者是堆排序(Heapsort)。堆排序通常比快速排序稍微慢,但是最壞情況的執行時間總是formula_7。快速排序是經常比較快,除了introsort變化版本外,仍然有最壞情況效能的機會。如果事先知道堆排序將會是需要使用的,那麼直接地使用堆排序比等待introsort再切換到它還要快。堆排序也擁有重要的特點,僅使用固定額外的空間(堆排序是原地排序),而即使是最佳的快速排序變化版本也需要formula_8的空間。然而,堆排序需要有效率的隨機存取才能變成可行。  快速排序也與歸併排序(Mergesort)競爭,這是另外一種遞迴排序演算法,但有壞情況formula_7執行時間的優勢。不像快速排序或堆排序,歸併排序是一個穩定排序,且可以輕易地被採用在連結串列(linked list)和儲存在慢速存取媒體上像是磁碟儲存或網路連線儲存的非常巨大數列。儘管快速排序可以被重新改寫使用在鏈序列上,但是它通常會因為無法隨機存取而導致差的基準選擇。歸併排序的主要缺點,是在最佳情況下需要formula_5額外的空間。

  從一開始快速排序平均需要花費formula_7時間的描述並不明顯。但是不難觀察到的是分割運算,陣列的元素都會在每次迴圈中走訪過一次,使用formula_12的時間。在使用結合(concatenation)的版本中,這項運算也是formula_12。  在最好的情況,每次我們執行一次分割,我們會把一個數列分為兩個幾近相等的片段。這個意思就是每次遞迴呼叫處理一半大小的數列。因此,在到達大小為一的數列前,我們只要作formula_14次巢狀的呼叫。這個意思就是呼叫樹的深度是formula_6。但是在同一階層的兩個程式呼叫中,不會處理到原來數列的相同部分;因此,程式呼叫的每一階層總共全部僅需要formula_12的時間(每個呼叫有某些共同的額外耗費,但是因為在每一階層僅僅只有formula_12個呼叫,這些被歸納在formula_12係數中)。結果是這個演算法僅需使用formula_7時間。  另外一個方法是為formula_20設立一個遞迴關係式,也就是需要排序大小為formula_1的數列所需要的時間。在最好的情況下,因為一個單獨的快速排序呼叫牽涉了formula_12的工作,加上對formula_23大小之數列的兩個遞迴呼叫,這個關係式可以是:  formula_24  解決這種關係式型態的標準數學歸納法技巧告訴我們formula_25。  事實上,並不需要把數列如此精確地分割;即使如果每個基準值將元素分開為99%在一邊和1%在另一邊,呼叫的深度仍然限制在formula_26,所以全部執行時間依然是formula_7。  然而,在最壞的情況是,兩子數列擁有大各為formula_28 和formula_29,且呼叫樹(call tree)變成為一個formula_1個巢狀(nested)呼叫的線性連串(chain)。第formula_31 次呼叫作了formula_32的工作量,且formula_33遞迴關係式為:  formula_34  這與插入排序和選擇排序有相同的關係式,以及它被解為formula_35。

  亂數快速排序有一個值得注意的特性,在任意輸入資料的狀況下,它只需要formula_7的期望時間。是什麼讓隨機的基準變成一個好的選擇?  假設我們排序一個數列,然後把它分為四個部分。在中央的兩個部分將會包含最好的基準值;他們的每一個至少都會比25%的元素大,且至少比25%的元素小。如果我們可以一致地從這兩個中央的部分選出一個元素,在到達大小為1的數列前,我們可能最多僅需要把數列分割formula_37次,產生一個formula_7演算法。  不幸地,亂數選擇只有一半的時間會從中間的部分選擇。出人意外的事實是這樣就已經足夠好了。想像你正在翻轉一枚硬幣,一直翻轉一直到有formula_39次人頭那面出現。儘管這需要很長的時間,平均來說只需要formula_40次翻動。且在formula_39次翻動中得不到formula_39次人頭那面的機會,是像天文數字一樣的非常小。藉由同樣的論證,快速排序的遞迴平均只要formula_43的呼叫深度就會終止。但是如果它的平均呼叫深度是formula_6且每一階的呼叫樹狀過程最多有formula_1個元素,則全部完成的工作量平均上是乘積,也就是formula_7。

  即使如果我們無法隨機地選擇基準數值,對於它的輸入之所有可能排列,快速排序仍然只需要formula_7時間。因為這個平均是簡單地將輸入之所有可能排列的時間加總起來,除以formula_1這個因子,相當於從輸入之中選擇一個隨機的排列。當我們這樣作,基準值本質上就是隨機的,導致這個演算法與亂數快速排序有一樣的執行時間。  更精確地說,對於輸入順序之所有排列情形的平均比較次數,可以藉由解出這個遞迴關係式可以精確地算出來。  formula_49。  在這裡,formula_29是分割所使用的比較次數。因為基準值是相當均勻地落在排列好的數列次序之任何地方,總和就是所有可能分割的平均。  這個意思是,平均上快速排序比理想的比較次數,也就是最好情況下,只大約比較糟39%。這意味著,它比最壞情況較接近最好情況。這個快速的平均執行時間,是快速排序比其他排序演算法有實際的優勢之另一個原因。

  被快速排序所使用的空間,依照使用的版本而定。使用原地(in-place)分割的快速排序版本,在任何遞迴呼叫前,僅會使用固定的額外空間。然而,如果需要產生formula_6巢狀遞迴呼叫,它需要在他們每一個儲存一個固定數量的資訊。因為最好的情況最多需要formula_6次的巢狀遞迴呼叫,所以它需要formula_6的空間。最壞情況下需要formula_12次巢狀遞迴呼叫,因此需要formula_12的空間。  然而我們在這裡省略一些小的細節。如果我們考慮排序任意很長的數列,我們必須要記住我們的變數像是"left"和"right",不再被認為是佔據固定的空間;也需要formula_6對原來一個formula_1項的數列作索引。因為我們在每一個堆疊框架中都有像這些的變數,實際上快速排序在最好跟平均的情況下,需要formula_58空間的位元數,以及最壞情況下formula_7的空間。然而,這並不會太可怕,因為如果一個數列大部分都是不同的元素,那麼數列本身也會佔據formula_7的空間位元組。  非原地版本的快速排序,在它的任何遞迴呼叫前需要使用formula_12空間。在最好的情況下,它的空間仍然限制在formula_12,因為遞迴的每一階中,使用與上一次所使用最多空間的一半,且  它的最壞情況是很恐怖的,需要  空間,遠比數列本身還多。如果這些數列元素本身自己不是固定的大小,這個問題會變得更大;舉例來說,如果數列元素的大部分都是不同的,每一個將會需要大約formula_6為原來儲存,導致最好情況是formula_7和最壞情況是formula_67的空間需求。

  選擇演算法(selection algorithm)可以選取一個數列的第formula_39個最小值;一般而言這是比排序還簡單的問題。一個簡單但是有效率的選擇演算法與快速排序的作法相當類似,除了對兩個子數列都作遞迴呼叫外,它僅僅針對包含想要的元素之子數列作單一的結尾遞迴(tail recursive)呼叫。這個小改變降低了平均複雜度到線性或是formula_69時間,且讓它成為一個原地演算法。這個演算法的一種變化版本,可以讓最壞情況下降為formula_12(參考選擇演算法來得到更多資訊)。  相反地,一旦我們知道一個最壞情況的formula_12選擇演算法是可以利用的,我們在快速排序的每一步可以用它來找到理想的基準(中位數),得到一種最壞情況下formula_7執行時間的變化版本。然而在實際的實作中,這種版本一般而言相當慢。

  1. David M. W. Powers. Parallelized Quicksort with Optimal Speedup. "Proceedings of International Conference on Parallel Computing Technologies". Novosibirsk. 1991.
快速排序(英語:Quicksort),又稱分割槽交換排序(英語:partition-exchange sort),簡稱快排,一種排序演算法,最早由東尼·霍爾提出。在平均狀況下,排序formula_1個專案要formula_2(大O符號)次比較。在最壞狀況下則需要formula_3次比較,但這種狀況並不常見。事實上,快速排序formula_4通常明顯比其他演算法更快,因為它的內部迴圈(inner loop)可以在大部分的架構上很有效率地達成。