9.9.4?快速排序優(yōu)化

??????? 剛才講的快速排序還是有不少可以改進的地方，我們來看一些優(yōu)化的方案。

1.優(yōu)化選取樞軸
??????? 如果我們選取的pivotkey是處于整個序列的中間位置，那么我們可以將整個序列分成小數(shù)集合和大數(shù)集合了。但注意，我剛才說的是“如果……是中間”，那么假如我們選取的pivotkey不是中間數(shù)如何呢？比如我們前面講冒泡和簡單選擇排序一直用到的數(shù)組{9,1,5,8,3,7,4,6,2}，由代碼第4行“pivotkey=L->r[low];”知道，我們應(yīng)該選取9作為第一個樞軸pivotkey。此時，經(jīng)過一輪“pivot=Partition(L,1,9);”轉(zhuǎn)換后，它只是更換了9與2的位置，并且返回9給pivot，整個系列并沒有實質(zhì)性的變化。如圖9-9-8。
?

??????? 就是說，代碼第4行“pivotkey=L->r[low];”變成了一個潛在的性能瓶頸。排序速度的快慢取決于L.r[1]的關(guān)鍵字處在整個序列的位置，L.r[1]太小或者太大，都會影響性能(比如第一例子中的50就是一個中間數(shù)，而第二例子的9就是一個相對整個序列過大的數(shù))。因為在現(xiàn)實中，待排序的系列極有可能是基本有序的，此時，總是固定選取第一個關(guān)鍵字（其實無論是固定選取哪一個位置的關(guān)鍵字）作為首個樞軸就變成了極為不合理的作法。
??????? 改進辦法，有人提出，應(yīng)該隨機獲得一個low與high之間的數(shù)rnd，讓它的關(guān)鍵字L.r[rnd]與L.r[low]交換，此時就不容易出現(xiàn)這樣的情況。這被稱為隨機選取樞軸法。應(yīng)該說，這在某種程度上，解決了對于基本有序的序列快速排序時的性能瓶頸。不過，隨機就有些撞大運的感覺，萬一沒撞成功，隨機到了依然是很小或很大的關(guān)鍵字怎么辦呢？
??????? 再改進，于是就有了三數(shù)取中（median-of-three）法。即取三個關(guān)鍵字先進行排序，將中間數(shù)作為樞軸，一般是取左端、右端和中間三個數(shù)，也可以隨機選取。這樣至少這個中間數(shù)一定不會是最小或者最大的數(shù)，從概率來說，取三個數(shù)均為最小或最大數(shù)的可能性是微乎其微的，因此中間數(shù)位于較為中間的值的可能性就大大提高了。由于整個序列是無序狀態(tài)，隨機選取三個數(shù)和從左中右端取三個數(shù)其實是一回事，而且隨機數(shù)生成器本身還會帶來時間上的開銷，因此隨機生成不予考慮。
??????? 我們來看看取左端、右端和中間三個數(shù)的實現(xiàn)代碼，在Partition函數(shù)代碼的第3行與第4行之間增加這樣一段代碼。

?

int pivotkey;int m = low + (high - low) / 2; /* 計算數(shù)組中間的元素的下標 */ if (L->r[low]>L->r[high]) swap(L,low,high); /* 交換左端與右端數(shù)據(jù)，保證左端較小 */if (L->r[m]>L->r[high])swap(L,high,m); /* 交換中間與右端數(shù)據(jù)，保證中間較小 */if (L->r[m]>L->r[low])swap(L,m,low); /* 交換中間與左端數(shù)據(jù)，保證左端較小 *//* 此時L.r[low]已經(jīng)為整個序列左中右三個關(guān)鍵字的中間值。*/ pivotkey=L->r[low]; /* 用子表的第一個記錄作樞軸記錄 */

??????? 試想一下，我們對數(shù)組{9,1,5,8,3,7,4,6,2}，取左9，中3，右2來比較，使得L.r[low]=3，一定要比9和2要來得更為合理。
????????三數(shù)取中對小數(shù)組來說有很大的概率選擇到一個比較好的pivotkey，但是對于非常大的待排序的序列來說還是不足以保證能夠選擇出一個好的pivotkey，因此還有個辦法是所謂九數(shù)取中（median-of-nine），它是先從數(shù)組中分三次取樣，每次取三個數(shù)，三個樣品各取出中數(shù)，然后從這三個中數(shù)當中再取出一個中數(shù)作為樞軸。顯然這就更加保證了取到的pivotkey是比較接近中間值的關(guān)鍵字。有興趣的同學可以自己去實現(xiàn)一下代碼，這里不再詳述了。

2.?優(yōu)化不必要的交換
??????? 觀察圖9-9-1～圖9-9-6，我們發(fā)現(xiàn)，50這個關(guān)鍵字，其位置變化是1→9→3→6→5，可其實，它的最終目標就是5，當中的交換其實是不需要的。因此我們對Partition函數(shù)的代碼再進行優(yōu)化。

/* 快速排序優(yōu)化算法 */int Partition1(SqList *L,int low,int high){ int pivotkey;//這里省略三數(shù)取中代碼pivotkey=L->r[low]; /* 用子表的第一個記錄作樞軸記錄 */L->r[0]=pivotkey; /* 將樞軸關(guān)鍵字備份到L->r[0] */while(low<high) /* 從表的兩端交替地向中間掃描 */{ while(low<high&&L->r[high]>=pivotkey)high--;L->r[low]=L->r[high]; /* 采用替換而不是交換的方式進行操作 */while(low<high&&L->r[low]<=pivotkey)low++;L->r[high]=L->r[low]; /* 采用替換而不是交換的方式進行操作 */}L->r[low]=L->r[0]; /* 將樞軸數(shù)值替換回L.r[low] */return low; /* 返回樞軸所在位置 */}

??????? 注意代碼中高亮部分的改變。我們事實將pivotkey備份到L.r[0]中，然后在之前是swap時，只作替換的工作，最終當low與high會合，即找到了樞軸的位置時，再將L.r[0]的數(shù)值賦值回L.r[low]。因為這當中少了多次交換數(shù)據(jù)的操作，在性能上又得到了部分的提高。如圖9-9-9所示。
?

?

3.?優(yōu)化小數(shù)組時排序方案
??????? 對于一個數(shù)學科學家，博士生導(dǎo)師，他可以攻克世界性的難題，可以培養(yǎng)最優(yōu)秀的數(shù)學博士，但讓他去教小學生“1+1=2”的算術(shù)課程，那還真未必會比常年在小學學校里耕耘的數(shù)學老師教得好。換句話說，大材小用有時會變得反而不好用。剛才我談到了對于非常大的數(shù)組的解決辦法。那么相反的情況，如果數(shù)組非常小，其實快速排序反而不如直接插入排序來得更好（直接插入是簡單排序中性能最好）。其原因在于快速排序用到了遞歸操作，在大量數(shù)據(jù)排序時，這點性能影響相對于它的整體算法優(yōu)勢而言是可以忽略的，但如果數(shù)組只有幾個記錄需要排序時，這就成了一個大炮打蚊子的大問題。因此我們需要改進一下QSort函數(shù)。

#define MAX_LENGTH_INSERT_SORT 7 /* 數(shù)組長度閥值 *//* 對順序表L中的子序列L.r[low..high]作快速排序 */void QSort(SqList &L,int low,int high){ int pivot;if((high-low)>MAX_LENGTH_INSERT_SORT) /*當high-low大于常數(shù)時快速排序*/{pivot=Partition(L,low,high); /* 將L.r[low..high]一分為二，算出樞軸值pivot */QSort(L,low,pivot-1); /* 對低子表遞歸排序 */QSort(L,pivot+1,high); /* 對高子表遞歸排序 */}else /* 當high-low小于等于常數(shù)時用直接插入排序 */InsertSort(L); }

??????? 我們增加了一個判斷，當high-low不大于某個常數(shù)時（有資料認為7比較合適，也有認為50更合理，實際應(yīng)用可適當調(diào)整），就用直接插入排序，這樣就能保證最大化的利用兩種排序的優(yōu)勢來完成排序工作。

4.?優(yōu)化遞歸操作
??????? 大家知道，遞歸對性能是有一定影響的，QSort函數(shù)在其尾部有兩次遞歸操作。如果待排序的序列劃分極端不平衡，遞歸的深度將趨近于n，而不是平衡時的log₂n，這就不僅僅是速度快慢的問題了。棧的大小是很有限的，每次遞歸調(diào)用都會耗費一定的棧空間，函數(shù)的參數(shù)越多，每次遞歸耗費的空間也越多。因此如果能減少遞歸，將會大大提高性能。
??????? 于是我們對QSort實施尾遞歸優(yōu)化。來看代碼。

/* 對順序表L中的子序列L.r[low..high]作快速排序 */void QSort1(SqList *L,int low,int high){ int pivot;if((high-low)>MAX_LENGTH_INSERT_SORT){while(low<high){pivot=Partition1(L,low,high); /* L.r[low..high]一分為二,算出樞軸值pivot */QSort1(L,low,pivot-1); /* 對低子表遞歸排序 */low=pivot+1; /* 尾遞歸 */}}elseInsertSort(L);}

??????? 當我們將if改成while后（見高亮代碼部分），因為第一次遞歸以后，變量low就沒有用處了，所以可以將pivot+1賦值給low，再循環(huán)后，來一次Partition(L,low,high)，其效果等同于“QSort(L,pivot+1,high);”。結(jié)果相同，但因采用迭代而不是遞歸的方法可以縮減堆棧深度，從而提高了整體性能。
在現(xiàn)實的應(yīng)用中，比如C++、java、PHP、C#、VB、Javascript等等都有對快速排序算法的實現(xiàn) ，實現(xiàn)方式上略有不同，但基本上都是在我們講解的快速排序法基礎(chǔ)上的精神體現(xiàn)。

??????? 我們現(xiàn)在學過的排序算法，有按照實現(xiàn)方法分類命名的，如簡單選擇排序、直接插入排序、歸并排序，有按照其排序的方式類比現(xiàn)實世界命名的，比如冒泡排序、堆排序，還有用人名命名的，比如希爾排序。但是剛才我們講的排序，卻用“快速”來命名，這也就意味著只要再有人找到更好的排序法，此“快速”就會名不符實，不過，至少今天，TonyHoare發(fā)明的快速排序法經(jīng)過多次的優(yōu)化后，在整體性能上，依然是排序算法王者。我們應(yīng)該要好好研究并掌握它。?

出處：http://www.cnblogs.com/cj723/archive/2011/04/28/2031345.html

總結(jié)

以上是生活随笔為你收集整理的《大话数据结构》第9章 排序 9.9 快速排序（下）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。