快速排序
- 優(yōu)點:
- 原地排序（只需要很小的輔助棧）
- 時間復雜度:NLgN
- 缺點:
- 非常脆弱。有無數(shù)例子證明許多錯誤能致使它在實際運用中只有平方級別的性能
QuickSort是一種分治的算法数冬，將一個數(shù)組分為兩個小數(shù)組髓抑，將兩部分獨立排序。
與MergeSort比較
- MergeSort將數(shù)組分為兩個子數(shù)組分別排序，然后將排好序的子數(shù)組Merge
- 遞歸調用位于處理整個數(shù)組之前
- 將數(shù)組分為兩半
- QuickSort是當兩個子數(shù)組都有序的時候品山，父數(shù)組自然有序了
- 遞歸調用位于處理整個數(shù)組之后(即partition之后)
- partition位置取決于數(shù)組的內(nèi)容
關鍵在于partition
使得數(shù)組滿足3個條件:
- 對于某個j述雾，a[j]已經(jīng)排定
- a[lo]到a[j-1]中的所有元素都不大于a[j]
- a[j+1]到a[hi]中的所有元素都不小于a[j]
切分的實現(xiàn)
一般選擇a[lo]作為切分元素
我們先從數(shù)組左端開始掃描街州，找到第一個比切分元素大的元素，然后從數(shù)組右端開始找到第一個比切分元素小的元素玻孟。顯然這兩個元素是沒有排定的唆缴，因此我們交換它們的位置。如此繼續(xù)黍翎，我們可以保證左指針i左側的元素都不大于切分元素面徽，右指針j的右側元素都不小于切分元素。當兩個指針相遇的時候匣掸，將切分元素與左子數(shù)組最右側的元素交換位置即可趟紊。
算法正確性
由于切分過程總是能排定一個元素，由歸納法可知一定能正確遞歸將整個數(shù)組排序
性能特點
QuickSort的內(nèi)循環(huán)會用一個遞增的index將數(shù)組的元素和一個定值比較(切分元素),shell sort 和 merge sort慢的原因在于它們在內(nèi)層循環(huán)中移動元素
Quick sort另一速度優(yōu)勢在于比較次數(shù)少.
但是排序效率還是取決于切分數(shù)組的效果碰酝，切分實際上有可能發(fā)生于一個數(shù)組的任何位置霎匈。理想情況是將數(shù)組對半分。在這種情況下送爸，quick sort所需的比較次數(shù)滿足Cn = 2Cn/2 + N
.2Cn/2表示兩個子數(shù)組的比較成本铛嘱，N表示需要讓左右指針于數(shù)組中間處相遇的比較次數(shù).
如果第一次從最小的元素開始切分，第二次從第二小的元素切分袭厂，那么大數(shù)組每次都要被切分墨吓，效率極低，因此在排序之前將數(shù)組隨機排序的主要原因就是要避免這種情況纹磺。
相關數(shù)學命題
命題K(按照算法書上的順序)
將長度為N的無重復數(shù)組排序帖烘，快速排序平均需要~2NLnN次比較以及1/6NLnN的交換.具體證明見書
命題L
快速排序最多需要N^2/2次比較，但隨機打亂數(shù)組能夠預防這種情況爽航。即:
若每次排序后總有其中一個數(shù)組是空的蚓让，則比較次數(shù)是∑n = N(N+1)/2 ~ N^2/2.
提升性能的幾個方法
1.切換到插入排序
基于以下兩點:
- 對于小數(shù)組乾忱，快速排序比插入排序要慢
- 因為遞歸，快速排序的sort()在小數(shù)組中也會調用自己
方法: if (hi <= lo) return; => if (hi <= lo + 5) { Insertion.sort(a, lo, hi); return;}
2.三取樣切分
使用子數(shù)組的一小部分元素的中位數(shù)來切分數(shù)組,取樣大小為3并用大小劇中的元素切分效果最好.
3.熵最優(yōu)的排序
簡單的想法是將數(shù)組切分為三部分历极，分別對應于小于窄瘟，等于，大于切分元素的數(shù)組元素.
Dijkstra解法:
維護一個lt指針趟卸，使得a[lo..lt-1]中的元素都小于v,一個gt指針使得a[gt+1..hi]中的元素都大于v,一個指針i使得a[lt..i-1]中的元素都等于v,a[i..gt]中的元素待定.
- a[i]小于v,交換a[lt]和a[i], lt和i ++
- a[i]大于v,交換a[i]和a[gt], --gt
- a[i]等于v, ++i
對于只有若干不同主鍵的隨機數(shù)組蹄葱，MergeSort的時間復雜度是NLgN，而quick3way則是線性的锄列。3way的最壞情況正是所有主鍵不同图云，當存在重復主鍵時，性能會比merge sort好很多邻邮。三向切分是信息量最優(yōu)的(熵值最低)竣况，對于任意分布的輸入，最優(yōu)的基于比較的算法平均所需的比較次數(shù)和3way切分的quicksort平均所需比較次數(shù)處于常數(shù)因子范圍內(nèi)筒严。
3way運行時間與輸入的信息量的N倍成正比丹泉。實際運用中這個性質很重要，因為對于包含大量重復元素的數(shù)組鸭蛙，它將排序時間從線性對數(shù)降到了線性級別摹恨。這和元素的順序沒有關系，因為會事先打亂以避免前文所提到的最壞情況娶视。
有人提出了不基于比較的排序算法晒哄，但仍然是quicksort的表現(xiàn)最優(yōu)良見后文
