快速排序算法的分析與研究

摘 要： 快速排序是排序算法中性能較好的一種，但存在對數據基本有序的情形下的性能瓶頸問題。為了保證快速排序在任何情況下的高效性，在對快速排序算法的時間效率進行充分的分析的基礎上，指出支點元素的選取是影響快速排序算法效率的主要因素。提出了一種隨機選擇支點元素的快速快排方法，很好地避免了最壞情況的發生。通過實驗驗證了改進算法的正確性和高效性。

關鍵詞： 快速排序算法； 支點元素； 時間效率； 隨機化快速排序

中圖分類號： TN911?34； TP301.6 文獻標識碼： A 文章編號： 1004?373X（2013）20?0054?03

快速排序（Quicksort）是一種基于比較、劃分的排序方法。它基本思想是：在待排元素集S中選擇一個元素x作為支點（Pivot），通過一趟排序將要排序的數據分割成獨立的兩個子序列SL和SR，其中左部分SL的所有元素都小于或等于支點元素，而右部分SR的所有元素都大于或等于支點元素（升序排序） ，其狀態如圖1所示。然后按此方法對這兩部分數據分別再進行快速排序，以此達到整個待排元素有序，整個排序過程可以遞歸進行，其遞歸的深度可用二叉樹表示，如圖2所示。從算法的思想可以得出，快速排序算法是利用分治技術的典型例子。通常，大家公認快速排序是基于比較的排序方法中平均比較次數最少、速度最快的排序算法，平均時間復雜度為O（nlbn）。但是，若支點元素選擇不當，在劃分的兩個子序列元素個數極度不平衡時，快速排序有效率會急劇下降，最壞情況下快速排序將蛻變為冒泡排序，其時間復雜度為O（n2），算法的遞歸深度就變成一棵深度為n的單支二叉樹?！?br>