快速排序是對冒泡排序的一種改進，是所有內部排序算法中平均性能最優的排序算法。其基本思想是基于分治法的：在待排序數組L[1...n]中任取一個元素pivot作為基準，從數組的兩端開始掃描。設兩個指示標志（low指向起始位置，high指向末尾)，先從后向前掃描（high遞減），如果high位置的元素小于pivot，就交換low和high位置的元素，然后從前向后掃描（low遞增），如果low位置的元素大于pivot，就交換low和high位置的元素。重復上述過程，直到low>=high，然后把基準放到low位置上，一趟排序就完成了，將一個元素（基準）放到了最終位置上，不產生有序子序列。將待排序數組劃分為兩部分即L[1...k-1]和L[k+1...n]，使得前半部分L[1...k-1]所有元素小于pivot，后半部分L[k+1...n]所有元素大于或等于pivot。接著采用遞歸的方式分別對前半部分和后半部分排序，直到每部分只有一個元素或空為止，即所有元素放在了最終位置上。
之所以快速排序比較快，是因為相比于冒泡排序，每次交換是跳躍式的。每次排序時選取一個基準，將小于基準的數全部放到基準點的左邊，將大于或等于基準的數全部放到基準的右邊，在每次交換時不會像冒泡排序一樣只能在相鄰的數之間進行交換，增大了交換距離，減少了總的比較和交換次數，加快了速度。在最壞情況下，仍可能交換相鄰的兩個數。
假設對“6 1 2 7 9 3 4 5 10 8”這10個數進行排序：
從后向前掃描
交換7和5
交換之后：6 1 2 5 9 3 4 7 10 8
交換9和4
交換之后：6 1 2 5 4 3 9 7 10 8
i>=j，交換6和3
交換之后：3 1 2 5 4 6 9 7 10 8
一趟排序結束。
1 public class QuickSort {
2
3 public static void quickSort(int[] arr, int low, int high) {
4 // 至少有兩個元素需要排序
5 if (low < high) {
6 int curLow = low;
7 int curHigh = high;
8 int temp = arr[low];
9
10 while(curLow < curHigh) {
11 // 從右向左掃描，尋找第一個比基準小的數
12 while(curLow < curHigh && arr[curHigh] >= temp) {
13 curHigh--;
14 }
15 arr[curLow] = arr[curHigh];
16
17 // 從左向右掃描，尋找第一個比基準大的數
18 while(curLow < curHigh && arr[curLow] <= temp) {
19 curLow++;
20 }
21 arr[curHigh] = arr[curLow];
22 }
23
24 // 基準歸位
25 arr[curLow] = temp;
26
27 // 基準位置左邊子序列遞歸排序
28 quickSort(arr, low, curLow - 1);
29 // 基準位置左邊子序列遞歸排序
30 quickSort(arr, curLow + 1, high);
31 }
32 }
33
34 public static void main(String[] args) {
35 int[] arr = {15, 1, 17, 3, 6, 8};
36 QuickSort.quickSort(arr, 0, arr.length - 1);
37
38 for (int i = 0, length = arr.length; i < length; i++) {
39 System.out.printf(" %d", arr[i]);
40 }
41 }
42
43 } 結果如下：
1 3 6 8 15 17 上述代碼每次以當前數組中第一個元素作為基準對數組進行劃分。
快速排序性能分析：
空間復雜度：因為快速排序是遞歸的，所以需要借助一個遞歸工作棧來保存每一層遞歸調用的必要信息，容量應與遞歸調用的最大深度一致。最壞情況下n-1次遞歸調用，棧的深度為O(n)；最好和平均情況下棧的深度為O(log2n)。所以，空間復雜度在最壞情況下為O(n)，平均情況下為O(log2n)。
時間復雜度：快速排序的性能主要取決于劃分操作的好壞。最壞情況下待排序數組基本有序或基本逆序時，每一次遞歸劃分的兩個區域分別包含n-1個元素和0個元素，快速排序退化成冒泡排序，時間復雜度為O(n2)。最好情況下最平衡劃分，兩個子數組長度不超過n/2，時間復雜度為O(nlog2n)。而快速排序平均情況下運行時間接近于最好情況下的運行時間，即時間復雜度在最壞情況下為O(n2)，平均情況下為O(nlog2n)。
穩定性：如果右端區間有兩個相同的關鍵字，且均小于基準，那么交換到左端區間后，它們的相對次序會變化，即快速排序不穩定。例如，表L={3， 2， 2}，經過一趟排序后L={2， 2， 3}，最終結果是L={2，?2， 3}，2與2的相對次序發生了變化。
改進方案
1 使用直接插入排序
當遞歸過程中劃分得到的子數組長度較小時，可以使用直接插入排序完成排序工作。
1 public static void quick(int []array ,int lo,int hi){
2 if(hi-lo+1<10){
3 insertSort(array);
4 }else{
5 quickSort(array,lo,hi);
6 }
7 } 2 選取好的基準
盡量選取可以把元素平衡劃分的基準，有三種方法：固定切分，隨機切分和三取樣切分。固定切分的效率低。隨機切分是常用的一種切分，效率高，最壞情況下時間復雜度有可能為O(n2)。三取樣切分最理想，具體操作：選取數組的頭尾和中間這3個元素，取這3個元素的中間值作為基準。
1 public static int partition(int []array,int lo,int hi){
2 //三數取中
3 int mid=lo+(hi-lo)/2;
4 if(array[mid]>array[hi]){
5 swap(array[mid],array[hi]);
6 }
7 if(array[lo]>array[hi]){
8 swap(array[lo],array[hi]);
9 }
10 if(array[mid]>array[lo]){
11 swap(array[mid],array[lo]);
12 }
13 int key=array[lo];
14
15 while(lo<hi){
16 while(array[hi]>=key&&hi>lo){
17 hi--;
18 }
19 array[lo]=array[hi];
20 while(array[lo]<=key&&hi>lo){
21 lo++;
22 }
23 array[hi]=array[lo];
24 }
25 array[hi]=key;
26 return hi;
27 }
28
29 public static void swap(int a,int b){
30 int temp=a;
31 a=b;
32 b=temp;
33 }
34 public static void sort(int[] array,int lo ,int hi){
35 if(lo>=hi){
36 return ;
37 }
38 int index=partition(array,lo,hi);
39 sort(array,lo,index-1);
40 sort(array,index+1,hi);
41 }
參考資料
《2017年數據結構聯考復習指導》 P287-288
快速排序（java實現）
坐在馬桶上看算法：快速排序
