**1、算法思想：**
一趟快速排序的算法是：
1）、設置兩個變量I、J，排序開始的時候I：=1，J：=N；
2）以第一個數組元素作為關鍵數據，賦值給X，即X：=A[1]；
3）、從J開始向前搜索，即由后開始向前搜索（J：=J-1），找到第一個小于X的值，兩者交換；
4）、從I開始向后搜索，即由前開始向后搜索（I：=I+1），找到第一個大于X的值，兩者交換；
5）、重復第3、4步，直到I=J；
**2、代碼實現：**
注意：
~~~
if (a.length > 0) { // 查看數組是否為空
? ? ? ? ? ? quickSort(a, 0, a.length - 1);
? ? ? ? }
~~~
~~~
private static void quickSort(int[] list, int low, int high) {
if (low < high) {// 不是while，否則死循環
int middle = partition(list, low, high); // 將list數組進行一分為二
quickSort(list, low, middle - 1); // 對低字表進行遞歸排序
quickSort(list, middle + 1, high); // 對高字表進行遞歸排序
}
}
private static int partition(int[] arr, int low, int high) {
int tmp = arr[low]; // 數組的第一個元素作為基準,用temp臨時存儲
while (low < high) {// 從區間兩端交替向中間掃描，直至low=high為止
while (low < high && arr[high] >= tmp) {// high向前搜索,直到找到第一個比temp小的元素
high--;
}
arr[low] = arr[high]; // 比temp小的(high)移到低端
while (low < high && arr[low] <= tmp) {// low下標增至第一個比temp大的元素
low++;
}// while終止說明arr[low]>temp
arr[high] = arr[low]; // 比temp大的(low)移到高端
}
// 當low == high，完成一趟快速排序，此時low位相當于空，等待基準temp補上
arr[low] = tmp; // 基準記錄已被最后定位
return low; // 返回基準的位置【下標】<基準最終位置>
}
~~~
**3、算法分析**
快速排序的時間主要耗費在劃分操作上，對長度為k的區間進行劃分，共需k-1次關鍵字的比較。
**（1）最壞時間復雜度**
最壞情況是每次劃分選取的基準都是當前無序區中關鍵字最小(或最大)的記錄，劃分的結果是基準左邊的子區間為空(或右邊的子區間為空)，而劃分所得的另一個非空的子區間中記錄數目，僅僅比劃分前的無序區中記錄個數減少一個。
因此，快速排序必須做n-1次劃分，第i次劃分開始時區間長度為n-i+1，所需的比較次數為n-i(1≤i≤n-1)，故總的比較次數達到最大值：
Cmax = 1+2+3+……(n-1)=n(n-1)/2=O(n2)
如果按上面給出的劃分算法，每次取當前無序區的第1個記錄為基準，那么當文件的記錄已按遞增序(或遞減序)排列時，每次劃分所取的基準就是當前無序區中關鍵字最小(或最大)的記錄，則快速排序所需的比較次數反而最多。
**（2）最好時間復雜度**
在最好情況下，每次劃分所取的基準都是當前無序區的"中值"記錄，劃分的結果是基準的左、右兩個無序子區間的長度大致相等。總的關鍵字比較次數：
0(nlgn)
注意：
用遞歸樹來分析最好情況下的比較次數更簡單。因為每次劃分后左、右子區間長度大致相等，故遞歸樹的高度為O(lgn)，而遞歸樹每一層上各結點所對應的劃分過程中所需要的關鍵字比較次數總和不超過n，故整個排序過程所需要的關鍵字比較總次數C(n)=O(nlgn)。
因為快速排序的記錄移動次數不大于比較的次數，所以快速排序的最壞時間復雜度應為0(n2)，最好時間復雜度為O(nlgn)。
（3）基準關鍵字的選取
在當前無序區中選取劃分的基準關鍵字是決定算法性能的關鍵。
**①"三者取中"的規則**
"三者取中"規則，即在當前區間里，將該區間首、尾和中間位置上的關鍵字比較，取三者之中值所對應的記錄作為基準，在劃分開始前將該基準記錄和該區伺的第1個記錄進行交換，此后的劃分過程與上面所給的Partition算法完全相同。
**②取位于low和high之間的隨機數k(low≤k≤high)，用R[k]作為基準**
選取基準最好的方法是用一個隨機函數產生一個取位于low和high之間的隨機數k(low≤k≤high)，用R[k]作為基準，這相當于強迫R[low..high]中的記錄是隨機分布的。用此方法所得到的快速排序一般稱為隨機的快速排序。
注意：
隨機化的快速排序與一般的快速排序算法差別很小。但隨機化后，算法的性能大大地提高了，尤其是對初始有序的文件，一般不可能導致最壞情況的發生。算法的隨機化不僅僅適用于快速排序，也適用于其它需要數據隨機分布的算法。
（4）平均時間復雜度
盡管快速排序的最壞時間為O(n2)，但就平均性能而言，它是基于關鍵字比較的內部排序算法中速度最快者，快速排序亦因此而得名。它的平均時間復雜度為O(nlgn)。
（5）空間復雜度
快速排序在系統內部需要一個棧來實現遞歸。若每次劃分較為均勻，則其遞歸樹的高度為O(lgn)，故遞歸后需棧空間為O(lgn)。最壞情況下，遞歸樹的高度為O(n)，所需的棧空間為O(n)。
（6）穩定性
快速排序是非穩定的，例如[2，2，1]。
**4、算法改進**
在本改進算法中,只對長度大于k的子序列遞歸調用快速排序,讓原序列基本有序，然后再對整個基本有序序列用插入排序算法排序。實踐證明，改進后的算法時間復雜度有所降低，且當k取值為 8?左右時,改進算法的性能最佳。
源碼地址：[https://github.com/zxiaofan/Algorithm/blob/master/src/sort/QuickSort.java](https://github.com/zxiaofan/Algorithm/blob/master/src/sort/QuickSort.java)
