思路
像合并排序一樣，快速排序是基于分支模式的：
分解：數組A[n]被劃分兩個字數組A[0..q-1]和A[q+1..n],使得對于數組A[0..q-1]中的元素都小于A[q], A[q+1..n]中的元素都大于等于A[q]。此時A[q]就得排好序。
解決：通過遞歸調用快速排序，對字數組A[0..q-1]和A[q+1..n]進行排序
合并：因為兩個字數組已經是就地排好序的了，整個數組已經排好序了。
參考代碼
按照以上模式可以寫出程式：
<a></a>
關鍵是找出劃分元素的位置函數getPartition，程式如下：其中一次運作過程，如下：
圖示
最後，數組的最後一個元素找到了自己最終的位置上，把左右分成了兩個相對獨立的數組。
通過圖示可以看出規律：
測試
性能
時間複雜度：就平均性能而言，快速排序是目前被認為是最好的一種内部排序方法。通常認為快速排序在平均情況下的時間複雜度為O(nlogn)。若初始記錄序列按關鍵字有序或基本有序，快速排序将蛻化為冒泡排序，其時間複雜度為O(n2)。
空間複雜度：最壞情況下，若每趟排序之後，樞軸位置均偏向子序列的一端（有序），棧的最大深度為n。如果在一趟劃分之後比較分割所得兩部分的長度，且先對長度短的子序列中的記錄進行快速排序，則棧的最大深度可降為O(logn)。
性能改善：在區間選取随機數，把該數放在應在的位置，可以有效避免最壞情況。如下
穩定性
不穩定
本文轉自jihite部落格園部落格，原文連結：http://www.cnblogs.com/kaituorensheng/archive/2013/02/23/2923771.html，如需轉載請自行聯系原作者