說(shuō)明：該系列博客整理自《算法導(dǎo)論(原書第二版)》，但更偏重于實(shí)用，所以晦澀偏理論的內(nèi)容未整理，請(qǐng)見(jiàn)諒。另外本人能力有限，如有問(wèn)題，懇請(qǐng)指正！
1、綜述
????快速排序是一種原地排序算法，對(duì)包含?n?個(gè)數(shù)的輸入數(shù)組進(jìn)行排序，最壞情況運(yùn)行時(shí)間為?Θ?(?n2?)。雖然這個(gè)最壞情況運(yùn)行時(shí)間比較差，但快速排序通常是用于排序的最佳的實(shí)用選擇，這是因?yàn)槠淦骄阅芟喈?dāng)好：期望的運(yùn)行時(shí)間為?Θ?(?n?lg?n?)，且?Θ?(?n?lg?n?)記號(hào)中隱含的常數(shù)因子很小。由于快速排序是一種原地排序，所以在虛存環(huán)境中也能很好的工作。
2、不隨機(jī)快速排序（平均情況下的時(shí)間復(fù)雜度相對(duì)較高）
????像合并排序一樣，快速排序也是基于分治模式的。下面是對(duì)一個(gè)子數(shù)組?A?[?p?..?r?]快速排序的過(guò)程，符合分治過(guò)程的三個(gè)步驟：
? ? ? ? 1）、分解：數(shù)組?A?[?p?..?r?]被劃分成兩個(gè)（可能為空）子數(shù)組?A?[?p?..?q?- 1 ]和?A?[?q?+ 1 ..?r?]，使得?A?[?p?..?q?- 1 ]中的每一個(gè)元素都小于等于?A?[?q?]，而且，A?[?q?]小于等于?A?[?q?+ 1 ..?r?]中的元素。下標(biāo)?q?也在這個(gè)劃分過(guò)程中計(jì)算得出。
? ? ? ? 2）、解決：通過(guò)遞歸調(diào)用，對(duì)子數(shù)組?A?[?p?..?q?- 1 ]和?A?[?q?+ 1 ..?r?]進(jìn)行快速排序。
? ? ? ? 3）、合并：因?yàn)閮蓚€(gè)子數(shù)組是就地排序的，將它們合并不需要操作，整個(gè)數(shù)組?A?[?p?..?r?]已排序。
????????下面的過(guò)程實(shí)現(xiàn)了快速排序：
????????QUICK-SORT(A, p, r)
????????????if p < r
????????????????q = PARTITION(A, p, r)
????????????????QUICK-SORT(A, p, q - 1)
????????????????QUICK-SORT(A, q + 1, r)
????????快速排序算法的關(guān)鍵是?PARTITION?過(guò)程，它對(duì)子數(shù)組?A?[?p?..?r?]進(jìn)行就地重排：
????????PARTITION(A, p, r)
?????????????x = A[r]
?????????????i = p - 1
?????????????for j = p to r - 1//首先遍歷出小于中值元素的值，放在i+1左側(cè)，
????????????? ? ?if A[j] <= x
????????????? ? ? ? ?i = i + 1
????????????? ? ? ? ?exchange A[i] with A[j]
?????????????exchange A[i + 1] with A[r]//遍歷結(jié)束后交換中值和i+1元素的值，則i+1之后的元素都大于中值
?????????????return i + 1
????????PARTITION?總是選擇?x?=?A?[?r?]作為?主元?（pivot element），并圍繞它來(lái)劃分子數(shù)組。在第3行到第6行中循環(huán)的每一輪迭代開始時(shí)，對(duì)于任何數(shù)組下標(biāo)?k?，有
????????????????如果?p?<=?k?<=?i?，則?A?[?k?] <=?x
????????????????如果?i?+ 1 <=?k?<=?j?- 1，則?A?[?k?] >?x
????????????????如果?k?=?r?，則?A?[?k?] =?x
????????下圖總結(jié)了這一結(jié)構(gòu)。過(guò)程?PARTITION?作用于子數(shù)組?A?[?p?..?r?]中得到四個(gè)區(qū)域。?A?[?p?..?i?]中的各個(gè)值都小于等于?x?，?A?[?i?+ 1 ..?j?- 1 ]中的值都大于?x?，?A?[?r?] =?x?。?A?[?j?..?r?- 1 ]中的值可以是任何值。
3、快速排序的性能
????快速排序的運(yùn)行時(shí)間與劃分是否對(duì)稱有關(guān)，而“劃分是否對(duì)稱”又與選擇了哪一個(gè)元素來(lái)進(jìn)行劃分有關(guān)。如果劃分是對(duì)稱的，那么本算法從漸近意義上來(lái)講，就和歸并排序算法一樣快；如果劃分是不對(duì)稱的，那么本算法漸近上就和插入排序一樣慢。下面我們討論劃分為對(duì)稱和不對(duì)稱時(shí)快速排序的性能。
? ? 1）、最壞情況劃分
????????快速排序的最壞情況劃分發(fā)生在劃分過(guò)程產(chǎn)生的兩個(gè)區(qū)域分別包含?n?- 1個(gè)元素和1個(gè)0元素的時(shí)候。假設(shè)算法的每一次遞歸調(diào)用都出現(xiàn)了這種不對(duì)稱劃分。劃分的時(shí)間代價(jià)為?Θ?(?n?)。對(duì)一個(gè)大小為0的數(shù)組進(jìn)行遞歸調(diào)用后，返回?T?( 0 ) =?Θ?( 1 )，故算法的運(yùn)行時(shí)間為?T?(?n?) =?T?(?n?- 1 ) +?Θ?(?n?)。
????????從直觀上看，如果將每一層遞歸的代價(jià)加起來(lái)，就可以得到一個(gè)算術(shù)級(jí)數(shù)，其和值的量級(jí)為Θ?(?n2?)。利用代換法，可以比較直接的證明遞歸式T?(?n?) =?T?(?n?- 1 ) +?Θ?(?n?)的解為T?(?n?) =?Θ?(?n2?)。
? ??????因此，如果在算法的每一層上遞歸上，劃分都是最大程度不對(duì)稱，那么算法的運(yùn)行時(shí)間就是Θ?(?n2?)。即，快速排序算法的最壞情況運(yùn)行時(shí)間并不比插入排序好。此外，當(dāng)輸入數(shù)組已經(jīng)完全排好序時(shí)，快速排序的運(yùn)行時(shí)間為Θ?(?n2?)，而在同樣情況下，插入排序的運(yùn)行時(shí)間為Θ?(n)。
? ? 2）、最佳情況劃分
????????在?PARTITION?過(guò)程可能的最平衡劃分中，得到的兩個(gè)子問(wèn)題的大小都不可能大于n/2，因?yàn)槠渲幸粋€(gè)子問(wèn)題的大小為?FLOOR（n / 2）?，另一個(gè)子問(wèn)題的大小為?CEIL(n / 2)?- 1。這種情況下，其運(yùn)行時(shí)間的遞歸式為?T?(?n?) <= 2?T?(?n?/ 2 ) +?Θ?(?n?)。該遞歸式的解為?T?(?n?) =?O?(?n?lg?n?)。由于在每一層的遞歸上，劃分的兩邊都是對(duì)稱的，因此，從漸近意義上來(lái)看，算法運(yùn)行的就跟快了。
? ? 3）、平衡的劃分
? ? ? ? 快速排序的平均情況運(yùn)行時(shí)間與其最佳情況運(yùn)行時(shí)間很接近，而不是非常接近于其最壞情況運(yùn)行時(shí)間。要理解這一點(diǎn)，就要理解劃分的平衡性是如何在刻畫運(yùn)行時(shí)間的遞歸式中反映出來(lái)的。
????????當(dāng)好、壞劃分交替分布在各層時(shí)，快速排序的運(yùn)行時(shí)間和最佳情況劃分是一樣的，即O?(?n?lg?n?)，只是O記號(hào)中隱含的常數(shù)因子要略大一些。如何好壞交替呢？需要隨機(jī)的選取選擇?x?作為?主元?（pivot element），而不是像不隨機(jī)快速排序那樣?x 一直等于 A?[?r?]。隨機(jī)快速排序在下面講解。
4、隨機(jī)快速排序
? ? 在探討快速排序的平均性態(tài)過(guò)程中，我們已經(jīng)假定輸入數(shù)據(jù)的所有排列都是等可能的，但在工程中，這個(gè)假設(shè)并不是總是成立的。所以，我們需要向算法中加入隨機(jī)化的成分，以便于對(duì)于所有輸入均能獲得很好的平局情況性能。
? ??隨機(jī)劃分使用?隨機(jī)取樣?（random sampling）的隨機(jī)化技術(shù)，從子數(shù)組?A?[?p?..?r?]中隨機(jī)選擇一個(gè)元素并與?A?[?r?]互換，因?yàn)橹髟请S機(jī)選擇的，我們期望在平均情況下，對(duì)輸入數(shù)組的劃分能夠比較對(duì)稱。
RANDOMIZED-PARTITION(A, p, r)
?????i = RANDOM(p, r)
?????exchange A[r] with A[i]
?????return PARTITION(A, p, r)
????RANDOMIZED-QUICK-SORT(A, p, r)
????????????if p < r
????????????????q = RANDOMIZED-PARTITION(A, p, r)
????????????????RANDOMIZED-QUICK-SORT(A, p, q - 1)
????????????????RANDOMIZED-QUICK-SORT(A, q + 1, r)
5、參考
? ??算法導(dǎo)論讀書筆記（7）
? ??快速排序算法
