說明：該系列博客整理自《算法導論(原書第二版)》，但更偏重于實用景殷，所以晦澀偏理論的內容未整理溅呢，請見諒。另外本人能力有限猿挚，如有問題咐旧，懇請指正！
1绩蜻、綜述
????快速排序是一種原地排序算法铣墨，對包含?n?個數(shù)的輸入數(shù)組進行排序，最壞情況運行時間為?Θ?(?n2?)办绝。雖然這個最壞情況運行時間比較差踏兜，但快速排序通常是用于排序的最佳的實用選擇专酗，這是因為其平均性能相當好：期望的運行時間為?Θ?(?n?lg?n?)胀葱，且?Θ?(?n?lg?n?)記號中隱含的常數(shù)因子很小迁霎。由于快速排序是一種原地排序，所以在虛存環(huán)境中也能很好的工作昔驱。
2、不隨機快速排序（平均情況下的時間復雜度相對較高）
????像合并排序一樣上忍，快速排序也是基于分治模式的骤肛。下面是對一個子數(shù)組?A?[?p?..?r?]快速排序的過程纳本，符合分治過程的三個步驟：
? ? ? ? 1）、分解：數(shù)組?A?[?p?..?r?]被劃分成兩個（可能為空）子數(shù)組?A?[?p?..?q?- 1 ]和?A?[?q?+ 1 ..?r?]腋颠，使得?A?[?p?..?q?- 1 ]中的每一個元素都小于等于?A?[?q?]繁成，而且，A?[?q?]小于等于?A?[?q?+ 1 ..?r?]中的元素淑玫。下標?q?也在這個劃分過程中計算得出巾腕。
? ? ? ? 2）、解決：通過遞歸調用絮蒿，對子數(shù)組?A?[?p?..?q?- 1 ]和?A?[?q?+ 1 ..?r?]進行快速排序尊搬。
? ? ? ? 3）、合并：因為兩個子數(shù)組是就地排序的土涝，將它們合并不需要操作佛寿，整個數(shù)組?A?[?p?..?r?]已排序。
????????下面的過程實現(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)
????????快速排序算法的關鍵是?PARTITION?過程但壮，它對子數(shù)組?A?[?p?..?r?]進行就地重排：
????????PARTITION(A, p, r)
?????????????x = A[r]
?????????????i = p - 1
?????????????for j = p to r - 1//首先遍歷出小于中值元素的值冀泻，放在i+1左側，
????????????? ? ?if A[j] <= x
????????????? ? ? ? ?i = i + 1
????????????? ? ? ? ?exchange A[i] with A[j]
?????????????exchange A[i + 1] with A[r]//遍歷結束后交換中值和i+1元素的值蜡饵，則i+1之后的元素都大于中值
?????????????return i + 1
????????PARTITION?總是選擇?x?=?A?[?r?]作為?主元?（pivot element）弹渔，并圍繞它來劃分子數(shù)組。在第3行到第6行中循環(huán)的每一輪迭代開始時验残，對于任何數(shù)組下標?k?捞附，有
????????????????如果?p?<=?k?<=?i?，則?A?[?k?] <=?x
????????????????如果?i?+ 1 <=?k?<=?j?- 1您没，則?A?[?k?] >?x
????????????????如果?k?=?r?鸟召，則?A?[?k?] =?x
????????下圖總結了這一結構。過程?PARTITION?作用于子數(shù)組?A?[?p?..?r?]中得到四個區(qū)域氨鹏。?A?[?p?..?i?]中的各個值都小于等于?x?欧募，?A?[?i?+ 1 ..?j?- 1 ]中的值都大于?x?，?A?[?r?] =?x?仆抵。?A?[?j?..?r?- 1 ]中的值可以是任何值跟继。
3、快速排序的性能
????快速排序的運行時間與劃分是否對稱有關镣丑，而“劃分是否對稱”又與選擇了哪一個元素來進行劃分有關舔糖。如果劃分是對稱的，那么本算法從漸近意義上來講莺匠，就和歸并排序算法一樣快金吗；如果劃分是不對稱的，那么本算法漸近上就和插入排序一樣慢。下面我們討論劃分為對稱和不對稱時快速排序的性能摇庙。
? ? 1）旱物、最壞情況劃分
????????快速排序的最壞情況劃分發(fā)生在劃分過程產生的兩個區(qū)域分別包含?n?- 1個元素和1個0元素的時候。假設算法的每一次遞歸調用都出現(xiàn)了這種不對稱劃分卫袒。劃分的時間代價為?Θ?(?n?)宵呛。對一個大小為0的數(shù)組進行遞歸調用后，返回?T?( 0 ) =?Θ?( 1 )夕凝，故算法的運行時間為?T?(?n?) =?T?(?n?- 1 ) +?Θ?(?n?)宝穗。
????????從直觀上看，如果將每一層遞歸的代價加起來迹冤，就可以得到一個算術級數(shù)讽营，其和值的量級為Θ?(?n2?)。利用代換法泡徙，可以比較直接的證明遞歸式T?(?n?) =?T?(?n?- 1 ) +?Θ?(?n?)的解為T?(?n?) =?Θ?(?n2?)橱鹏。
? ??????因此，如果在算法的每一層上遞歸上堪藐，劃分都是最大程度不對稱莉兰，那么算法的運行時間就是Θ?(?n2?)。即礁竞，快速排序算法的最壞情況運行時間并不比插入排序好糖荒。此外，當輸入數(shù)組已經(jīng)完全排好序時模捂，快速排序的運行時間為Θ?(?n2?)捶朵，而在同樣情況下，插入排序的運行時間為Θ?(n)狂男。
? ? 2）综看、最佳情況劃分
????????在?PARTITION?過程可能的最平衡劃分中，得到的兩個子問題的大小都不可能大于n/2岖食，因為其中一個子問題的大小為?FLOOR（n / 2）?红碑，另一個子問題的大小為?CEIL(n / 2)?- 1。這種情況下泡垃，其運行時間的遞歸式為?T?(?n?) <= 2?T?(?n?/ 2 ) +?Θ?(?n?)析珊。該遞歸式的解為?T?(?n?) =?O?(?n?lg?n?)。由于在每一層的遞歸上蔑穴，劃分的兩邊都是對稱的忠寻，因此，從漸近意義上來看存和，算法運行的就跟快了锡溯。
? ? 3）赶舆、平衡的劃分
? ? ? ? 快速排序的平均情況運行時間與其最佳情況運行時間很接近，而不是非常接近于其最壞情況運行時間祭饭。要理解這一點，就要理解劃分的平衡性是如何在刻畫運行時間的遞歸式中反映出來的叙量。
????????當好倡蝙、壞劃分交替分布在各層時，快速排序的運行時間和最佳情況劃分是一樣的绞佩，即O?(?n?lg?n?)寺鸥，只是O記號中隱含的常數(shù)因子要略大一些。如何好壞交替呢品山？需要隨機的選取選擇?x?作為?主元?（pivot element）胆建，而不是像不隨機快速排序那樣?x 一直等于 A?[?r?]。隨機快速排序在下面講解肘交。
4笆载、隨機快速排序
? ? 在探討快速排序的平均性態(tài)過程中，我們已經(jīng)假定輸入數(shù)據(jù)的所有排列都是等可能的涯呻，但在工程中凉驻，這個假設并不是總是成立的。所以复罐，我們需要向算法中加入隨機化的成分涝登，以便于對于所有輸入均能獲得很好的平局情況性能。
? ??隨機劃分使用?隨機取樣?（random sampling）的隨機化技術效诅，從子數(shù)組?A?[?p?..?r?]中隨機選擇一個元素并與?A?[?r?]互換胀滚，因為主元是隨機選擇的，我們期望在平均情況下乱投，對輸入數(shù)組的劃分能夠比較對稱咽笼。
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、參考
? ??算法導論讀書筆記（7）
? ??快速排序算法
