9.9.2 快速排序復(fù)雜度分析
我們來(lái)分析一下快速排序法的性能,?？焖倥判虻臅r(shí)間性能取決于快速排序遞歸的深度，可以用遞歸樹(shù)來(lái)描述遞歸算法的執(zhí)行情況,。如圖9‐9‐7所示,，它是{50,10,90,30, 70,40,80,60,20}在快速排序過(guò)程中的遞歸過(guò)程。由于我們的第一個(gè)關(guān)鍵字是50,，正好是待排序的序列的中間值,，因此遞歸樹(shù)是平衡的，此時(shí)性能也比較好,。
 |
| 圖9-9-7 |
在最優(yōu)情況下,，Partition每次都劃分得很均勻,，如果排序n個(gè)關(guān)鍵字，其遞歸樹(shù)的深度就為.log2n.+1（.x.表示不大于x的最大整數(shù)）,，即僅需遞歸log2n次,，需要時(shí)間為T(mén)（n）的話(huà)，第一次Partiation應(yīng)該是需要對(duì)整個(gè)數(shù)組掃描一遍,，做n次比較,。然后，獲得的樞軸將數(shù)組一分為二,，那么各自還需要T（n/2）的時(shí)間（注意是最好情況,，所以平分兩半）。于是不斷地劃分下去,，我們就有了下面的不等式推斷,。
- T（n）≤2T（n/2） +n，T（1）=0
- T（n）≤2（2T（n/4）+n/2） +n=4T（n/4）+2n
- T（n）≤4（2T（n/8）+n/4） +2n=8T（n/8）+3n
- ……
- T（n）≤nT（1）+（log2n）×n= O(nlogn)
也就是說(shuō),，在最優(yōu)的情況下,，快速排序算法的時(shí)間復(fù)雜度為O(nlogn)。
在最壞的情況下,，待排序的序列為正序或者逆序,，每次劃分只得到一個(gè)比上一次劃分少一個(gè)記錄的子序列，注意另一個(gè)為空,。如果遞歸樹(shù)畫(huà)出來(lái)，它就是一棵斜樹(shù),。此時(shí)需要執(zhí)行n‐1次遞歸調(diào)用,，且第i次劃分需要經(jīng)過(guò)n‐i次關(guān)鍵字的比較才能找到第i個(gè)記錄，也就是樞軸的位置,，因此比較次數(shù)為
,，最終其時(shí)間復(fù)雜度為O(n2)。
平均的情況,，設(shè)樞軸的關(guān)鍵字應(yīng)該在第k的位置（1≤k≤n）,，那么：
由數(shù)學(xué)歸納法可證明，其數(shù)量級(jí)為O(nlogn),。
就空間復(fù)雜度來(lái)說(shuō),，主要是遞歸造成的棧空間的使用,，最好情況,，遞歸樹(shù)的深度為log2n，其空間復(fù)雜度也就為O(logn),，最壞情況,，需要進(jìn)行n‐1遞歸調(diào)用，其空間復(fù)雜度為O(n)，平均情況,，空間復(fù)雜度也為O(logn),。
可惜的是，由于關(guān)鍵字的比較和交換是跳躍進(jìn)行的,，因此,，快速排序是一種不穩(wěn)定的排序方法。
