2.6.1　快速排序算法

快速排序是一種最壞情況為O(n^2)的排序算法，雖然這個最壞情況比較差，但快速排序通常是用于排序的最佳實用選擇，這是因為它的平均性能比較好，其排序期望運行時間為O(nlgn)，且O(nlgn)記號中隱含的常數因子很小。另外，它還不消耗額外的內存空間，在嵌入式環境中也能很好工作，因此廣受人們歡迎，是最常用、最好用的排序算法。

快速排序算法的排序步驟如下。

1）從序列中選一個元素作為基準元素。

2）把所有比基準元素小的元素移到基準元素的左邊，把比基準元素大的移到右邊。

3）對分開來的兩個（一大一?。﹨^塊依次進行遞歸、篩選后，再對這兩個區塊進行前兩個步驟的處理。

簡單來說，就是選取一個區域里的數字，把這個區域按這個數字分成兩半，一半小一半大，然后繼續對這兩部分執行同樣的操作，直到所有篩選都完成，就完成了排序。

該排序算法最差的情況是，每次都選到一個最小的或最大的數字，這樣每次篩選時都要充分移動，不過這種排列方式的相對概率低?？焖倥判蚴亲畛Ｓ玫呐判蚍椒ǎ晕覀円貎灮怂惴?。

下面就來看看如何優化快速排序算法。

1.隨機選擇中軸數

在快速排序時，選擇以哪個元素作為中軸數比較關鍵，因為這會影響算法的排序效率，如果選中的數字不是中間的數字，而是一個偏小或偏大的數字，那么排序的速度就會大大降低。如果選中的剛好是最大的或最小的數字，則更糟糕，左邊或右邊完全沒有數字可以排，相當于一次完整的遍歷只排序了一個元素。

因為我們查找區間那個準確的中軸數會花費很多精力，所以只能減小得到最壞情況的概率，隨機獲取列表中的元素作為基準元素。雖然隨機是為了減小選到最大值和最小值的概率，但隨機也會選到不好的基準元素，實際上，隨機數并沒有對排序提供多大的幫助。

2.三數取中

為了讓選擇的中軸數更接近中位數，可以將頭、中、尾3個數字先進行排序，最小的數字放在頭部，中間的數字放在中部，最大的數字放在尾部，然后用3個數字去提高有效接近中位數的中軸元素。

在每個區間的頭、中、尾排序前都先執行這個操作，也就是說，每次排序前，中軸數都不可能是最小的，起碼是區間里第二小的或者第二大的，這樣選出來的中軸數靠近中位數的概率就很大。

那么是否可以把3個數擴大到4個或M個數？其實過多數字的選擇就相當于多出了一個排序算法，降低了二分排序的效果，實際效果不如3個數字來得快。雖然可以用隨機選取3個數字的方式，但實際上這對中軸數的選擇并沒有什么幫助，況且偽隨機數的計算和沖突的解決也是需要消耗CPU空間的，因此三數取中是選擇接近中位數的元素比較有效的辦法。

3.小區間使用插入排序

排序算法有各自的使用量級，當量級不同時，排序效率可能不一樣。插入排序就依賴于序列的有序性和排序元素的數量，即排序的效率由排序列表的有序程度決定，也與排序的元素數量有關，如果序列的排序剛好是反序的，則排序效率最低，反之，如果是有序序列，則效率最高。

插入排序的特點是排序序列越長，效率越差。短序列的排序效果很好，高效排序序列長度為8左右。于是我們可以用這個特點來改善快速排序中的效率，即當切分的區塊小于或等于8個時，就采用插入排序來替代快速排序，因為8個以下的元素排序時，插入排序能達到更好的效率，因此我們可將它與快速排序混合使用，這樣的排序效率更高，其他時候仍然采用快速排序算法。

4.縮小分割范圍，與中軸數相同的合并在一起

除了選擇更加靠近中位數的數字作為中軸數，以及小范圍使用更快的排序方式外，我們還可以通過縮小排序范圍的方法來提高排序效率。

可以把與中軸數相同的數合并到中軸數左右的位置，這樣分割后兩邊的范圍就會縮小，范圍越小，排序的速度就越快，刨去了更多不需要排序的元素。具體操作步驟為，在每次的分割比較中，當元素與中軸數相等時，直接將其移動到中軸數身邊，移動完畢后劃分范圍從中軸數變為最邊上相同元素的位置，使用這種方式來縮小范圍，后續可減少排序元素。

快速排序是最常用也是使用范圍最廣的排序算法，銘記于心很有必要。