算法分析
快速排序的時間主要耗費在劃分操作上對長度為k的區間進行劃分共需k次關鍵字的比較
()最壞時間復雜度
最壞情況是每次劃分選取的基准都是當前無序區中關鍵字最小(或最大)的記錄劃分的結果是基准左邊的子區間為空(或右邊的子
區間為空)而劃分所得的另一個非空的子區間中記錄數目僅僅比劃分前的無序區中記錄個數減少一個
因此快速排序必須做n次劃分第i次劃分開始時區間長度為ni+所需的比較次數為ni(≤i≤n)故總的比較次數達
到最大值
C max = n(n)/=O(n )
如果按上面給出的劃分算法每次取當前無序區的第個記錄為基准那麼當文件的記錄已按遞增序(或遞減序)排列時每次劃分
所取的基准就是當前無序區中關鍵字最小(或最大)的記錄則快速排序所需的比較次數反而最多
() 最好時間復雜度
在最好情況下每次劃分所取的基准都是當前無序區的中值記錄劃分的結果是基准的左右兩個無序子區間的長度大致相等
總的關鍵字比較次數
(nlgn)
注意
用遞歸樹來分析最好情況下的比較次數更簡單因為每次劃分後左右子區間長度大致相等故遞歸樹的高度為O(lgn)而遞歸
樹每一層上各結點所對應的劃分過程中所需要的關鍵字比較次數總和不超過n故整個排序過程所需要的關鍵字比較總次數
C(n)=O(nlgn)
因為快速排序的記錄移動次數不大於比較的次數所以快速排序的最壞時間復雜度應為(n )最好時間復雜度為O(nlgn)
()基准關鍵字的選取
在當前無序區中選取劃分的基准關鍵字是決定算法性能的關鍵
①三者取中的規則
三者取中規則即在當前區間裡將該區間首尾和中間位置上的關鍵字比較取三者之中值所對應的記錄作為基准在劃分
開始前將該基准記錄和該區伺的第個記錄進行交換此後的劃分過程與上面所給的Partition算法完全相同
②取位於low和high之間的隨機數k(low≤k≤high)用R[k]作為基准
選取基准最好的方法是用一個隨機函數產生一個取位於low和high之間的隨機數k(low≤k≤high)用R[k]作為基准這相當於
強迫R[lowhigh]中的記錄是隨機分布的用此方法所得到的快速排序一般稱為隨機的快速排序具體算法【參見教材】
注意
隨機化的快速排序與一般的快速排序算法差別很小但隨機化後算法的性能大大地提高了尤其是對初始有序的文件一般不
可能導致最壞情況的發生算法的隨機化不僅僅適用於快速排序也適用於其它需要數據隨機分布的算法
()平均時間復雜度
盡管快速排序的最壞時間為O(n )但就平均性能而言它是基於關鍵字比較的內部排序算法中速度最快者快速排序亦因此
而得名它的平均時間復雜度為O(nlgn)
()空間復雜度
快速排序在系統內部需要一個棧來實現遞歸若每次劃分較為均勻則其遞歸樹的高度為O(lgn)故遞歸後需棧空間為O(lgn)
最壞情況下遞歸樹的高度為O(n)所需的棧空間為O(n)
()穩定性
快速排序是非穩定的例如[ ]
From:http://tw.wingwit.com/Article/program/sjjg/201311/23783.html
