快速排序屬性
上一篇文章介紹了 冒泡排序和它的優化 。這次介紹的快速排序是冒泡排序演變而來的算法，比冒泡排序要高效的很多。
快速排序之是以快，是因為它使用了分治法。它雖然也是通過不斷的比較和移動來實作排序的，隻不過它的實作，增大了比較的距離和移動的距離。而冒泡排序隻是相鄰的比較和交換。
快速排序的思想是，通過一趟排序将待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分别對這兩部分記錄繼續進行排序，以達到整個序列有序的目的。
從字面上感覺不到它的好處，我們通過一個示例來了解基本的快速排序算法，假設目前數組元素是：5, 1, 9, 3, 7, 4, 8, 6, 2。
基本的快速排序算法
初始狀态：5, 1, 9, 3, 7, 4, 8, 6, 2
選擇5作為一個基準元素，然後從右向左移動hight下标，進行基準元素和下标為hight的元素進行比較。
如果基準元素要大，則進行hight的左移一位；如果基準元素要小，則進行元素的交換。
在hight下标左移的過程中，我們目的是找出比基準元素小的，然後進行交換。
交換完之後，進行left的右移，找出比基準元素大的，找到則進行交換。
視訊動畫
Code
Result
優化樞軸的選取
舉一個恰當的例子，假設數組元素是9，8，7，6，5，4，3，2，1。
進行hight左移的時候第一個就發生了交換，1，8，7，6，5，4，3，2，9。嗯看似效率蠻快，但是進行low右移的時候一個個做了不必要的計算，沒有一個元素比樞軸值要大。和冒泡排序一樣，這一趟進行了8次比較，時間複雜度達到最壞程度O(n^2)。和快排的O(nlongn)相悖。
那拿什麼更好的方式選取樞軸值呢？
我看到網上都說是，随機選取一個數作為基準元素。嗯看似一個好的方法，但是和上面大機率出現的最壞情況還是有可能發生的。每次選取樞軸值都有可能是最大的或者最小的。如果是龐大的資料量第一個随機選到了最大的數，程式卡的半死不活的，隻有kill掉再重新運作嗎？
改進情況，取三數之中的中間數的一個數。什麼意思呢？
就是在一組數中取三個關鍵數字，将中間數作為樞軸，一般可以取左端，右端和中間三個數，也可以随機選取。那你可能說了，要是三個數都是最小的或者都是最大的那什麼辦呢？
沒錯，這樣選取還是會帶來時間上的開銷，并不證明選取到一個好的樞軸值。那要是取九數之中的中間數呢？
這當然不是采用随機取九個數然後再排序排一半取中間數那一個。
它是從數組中分三次取樣，每次取三個數，三個樣品中各取出中間數，然後在這三個中樞當中再取一個中間數作為樞軸。如果一次極端就算了，但是分三次取樣還會碰到三次極端那顯然是微乎其微的。這樣的方法增加選到好的樞軸的機率。
優化不必要的交換
回到基本的快速排序算法，回顧上面的視訊動畫。我們可以發現，這其中發生了不必要的移動方式。
我們最終要求一趟選的樞軸值，大的數在它的右邊，小的數在它左邊。但是這個樞軸值每次符合條件去了不該去的地方。我認為它前面的地方不要動，等一趟完了就去自己該去的地方，減少時間上的消耗。
優化遞歸操作
我們都知道，遞歸對性能是有一定影響的，quickSort函數尾部有兩次遞歸操作。如果待排序的序列極為極端不平衡，遞歸的深度幾乎接近于n的高度（沒有了二分法的優勢）。這樣的時間複雜度也是達到了最壞的程度O(n^2)，而不是平衡時的O(nlogn)。
時間慢也就算了，但是棧的大小也是有限的，每次遞歸操作都消耗一定的棧空間，函數的參數越多，每次遞歸調用參數耗費的空間也是越多。
如果能減少遞歸，性能也是以大大提高。
那拿什麼方式優化遞歸操作呢？
來看下面代碼。
執行結果之後和前面兩個結果無異。這是一個很好的方法。我們把if改成while，然後一次遞歸之後，low已經沒有用處了，是以把pivot+1指派給low作為下一個參數。結果你也看到了，結果都相同。
是以采用疊代而不是遞歸的方法可以縮減堆棧深度，進而提高了整體性能。
-----End-----
來源 | 算法無遺策
作者 | 我脫下短袖