快速排序
是對冒泡排序的一種改進，由 C.A.R.Hoare（Charles Antony Richard Hoare，東尼·霍爾）在 1962 年提出。
快速排序的
基本思想
是：通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料比另一部分的所有資料要小，再按這種方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行，使整個資料變成有序序列。
快速排序的原理
排序算法的思想非常簡單，在待排序的數列中，我們首先要找一個數字作為基準數（這隻是個專用名詞）。為了友善，我們一般選擇第 1 個數字作為基準數（其實選擇第幾個并沒有關系）。接下來我們需要把這個待排序的數列中小于基準數的元素移動到待排序的數列的左邊，把大于基準數的元素移動到待排序的數列的右邊。這時，左右兩個分區的元素就相對有序了；接着把兩個分區的元素分别按照上面兩種方法繼續對每個分區找出基準數，然後移動，直到各個分區隻有一個數時為止。
這是典型的分治思想，即分治法。下面我們對一個實際例子進行算法描述，講解快速排序的排序步驟。
以 47、29、71、99、78、19、24、47 的待排序的數列為例進行排序，為了友善區分兩個 47，我們對後面的 47 增加一個下畫線，即待排序的數列為 47、29、71、99、78、19、24、47。
首先我們需要在數列中選擇一個基準數，我們一般會選擇中間的一個數或者頭尾的數，這裡直接選擇第 1 個數 47 作為基準數，接着把比 47 小的數字移動到左邊，把比 47 大的數字移動到右邊，對于相等的數字不做移動。是以實際上我們需要找到中間的某個位置 k，這樣 k 左邊的值全部比 k 上的值小，k 右邊的值全部比 k 上的值大。
接下來開始移動元素。怎麼移動呢？其實冒泡排序也涉及對元素的移動，但是那樣移動起來很累，比如把最後一個元素移動到第 1 個，就需要比較 n-1 次，同時交換 n-1 次，效率很低。其實，隻需把第 1 個元素和最後一個元素交換就好了，這種思想是不是在排序時可以借鑒呢？之前說快速排序就是對冒泡排序的一個改進，就是這個原因。
快速排序的操作
是這樣的：首先從數列的右邊開始往左邊找，我們設這個下标為 i，也就是進行減減操作（i–），找到第 1 個比基準數小的值，讓它與基準值交換；接着從左邊開始往右邊找，設這個下标為 j，然後執行加加操作（j++），找到第 1 個比基準數大的值，讓它與基準值交換；然後繼續尋找，直到 i 與 j 相遇時結束，最後基準值所在的位置即 k 的位置，也就是說 k 左邊的值均比 k 上的值小，而 k 右邊的值都比 k 上的值大。
是以對于上面的數列 47、29、71、99、78、19、24、47，進行第 1 趟第 1 個交換的排序情況如下，第 1 次的操作情況如圖 1 所示。
圖 1 第 1 次發現可以交換的數
交換之後，i 移動到了下标為 6 的位置，對 j 繼續掃描，如圖 2 所示。
圖 2 第 2 次發現可交換的值
此時交換後的數列變為 24、29、47、99、78、19、71、47。接下來我們繼續對 i、j 進行操作，如圖 3 所示，繼續進行 i-- 及 j++ 的比較操作。
圖 3 繼續進行 i 與 j 的移動
進行了這兩次 i、j 的移動、比較、交換之後，我們最終得到的數列是 24、29、19、47、78、99、71、47。接下來我們繼續進行 i-- 的操作，發現在 i 為 4 時比 47 大不用交換，在 i 為 3 時與 j 相遇，這時就不需要繼續移動、比較了，已經找到 k 了，并且 k 的值為 3。我們可以确認一下目前的數列是不是 k 左邊的值都比 47 小，而 k 右邊的值都比 47 大（由于要保持相對位置不變，是以 47 同樣在基準值 47 的右邊）。
47 這個值已經落到了它該在的位置，第 1 趟排序完成了。接下來就是以 k 為基準，分為兩部分，然後在左右兩部分分别執行上述排序操作，最後資料會分為 4 部分；接着對每部分進行操作，直到每部分都隻有一個值為止。
接下來進行第 2 趟排序，現在左邊部分為 24、29、19，我們選擇第 1 個數 24 作為基準數，接着進行 i–、j++ 的操作，我們發現 i 最初的值為 19，比 24 這個基準值小，是以與基準值進行交換，得到的數列為 19、29、24；當 j 為 1 時，我們發現 29 比 24 大，是以與基準值進行交換，得到的數列 19、24、29，此時 i 為 2，j 為 1；繼續 i-- 時發現 i 為 1，與 j 相遇，左邊部分的數列的 k 為 1，并且左右兩部分分别隻有一個元素，此時第 2 輪排序的左邊部分的排序結束，同時左邊部分的所有資料都排序完成。
我們接着看右邊部分的排序，待排序的數列為 78、99、71、47，我們同樣選擇第 1 個值 78 為基準值，接下來進行 i 與 j 的移動與比較，發現 47 比 78 小，進行交換，得到的數列 47、99、71、78；從左往右發現 99 比基準值 78 大，進行交換，得到的數列為 47、78、71、99；繼續從右向左看，發現 71 比基準值 78 小，進行交換，得到的數列為 47、71、78、99。此時 i 在整體數組中的下标為 6，j 為 5，若繼續 j++ 則與 i 相遇，是以完成此輪排序。
此時右邊數列的 k 為 6，一般會是相遇的位置，也就是基準值所在的位置，這時數列又被分為兩部分，左邊是 47、71，右邊是 99，需要繼續對左邊部分的資料進行排序，雖然隻有兩個資料，但我們還是繼續按照快速排序的思想操作一下，選擇 47 作為基準數，将i進行從右向左的移動、比較，發現 i 與 j 相等時沒有産生移動，完成第 2 輪排序。
至此，所有排序都已經完成，最終數列的結果是 19、24、29、47、47、71、78、99，怎麼樣，快速排序是不是非常簡單地完成了所有的排序呢？雖然本次快速排序沒有改變相同值的元素的順序，但是由于快速排序需要對數列中的元素來回移動，有時還是會改變相對順序的，是以快速排序并不是一個穩定的算法。
快速排序的實作
通過以上的學習，你是否可以自己寫出快速排序的實作代碼呢？在接着學習之前，最好自己能對代碼的實作進行一些思考，然後和下面的内容進行比對，看看自己有哪些疏忽之處。
其實快速排序有一個比較簡單的思想，就是遞歸。對于每一趟排序都是一樣的思想，隻不過需要進行排序的數組的範圍越來越小了，使用遞歸實作這種排序最适合不過了。
public class QuickSort {
public static void main(String[] args) {
int[] array = {5, 9, 1, 9, 5, 3, 7, 6, 1}; // 待排序數組
sort(array, 0, array.length - 1);
print(array);
}
/**
* 快速排序
*
* @param array 待排序的數組
* @param low 數組的起始位址
* @param high 數組的結束位址
*/
public static void sort(int array[], int low, int high) {
// 直到兩個下标相遇，程式結束
if (low < high) {
// 查找 k 的位置
int k = partition(array, low, high);
// 對 k 左側的子表進行排序
sort(array, low, k - 1);
// 對 k 右側的子表進行排序
sort(array, k + 1, high);
}
}
/**
* 快速排序，分割的過程
*
* @param array 待排序的數組
* @param low 數組的起始位址
* @param high 數組的結束位址
* @return k 值
*/
public static int partition(int array[], int low, int high) {
// 基準點
int point = array[low];
// 直到兩個下标相遇，程式結束
while (low < high) {
// high 向左移動，直至遇到比point值小的記錄，停止移動
while (low < high && array[high] >= point) {
high--;
}
// 交換兩個元素的位置
swap(array, low, high);
//low 向右移動，直至遇到比point值大的記錄，停止移動
while (low < high && array[low] <= point) {
low++;
}
// 交換兩個元素的位置
swap(array, low, high);
}
return low;
}
/**
* 交換數組中兩個元素的位置
*/
public static void swap(int array[], int low, int high) {
int temp = array[low];
array[low] = array[high];
array[high] = temp;
}
/**
* 列印數組
*/
public static void print(int array[]) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}
快速排序的特點及性能
快速排序是在冒泡排序的基礎上改進而來的，冒泡排序每次隻能交換相鄰的兩個元素，而快速排序是跳躍式的交換，交換的距離很大，是以總的比較和交換次數少了很多，速度也快了不少。
但是快速排序在最壞情況下的時間複雜度和冒泡排序一樣，是 O(n2)，實際上每次比較都需要交換，但是這種情況并不常見。我們可以思考一下如果每次比較都需要交換，那麼數列的平均時間複雜度是 O(nlogn)，事實上在大多數時候，排序的速度要快于這個平均時間複雜度。這種算法實際上是一種分治法思想，也就是分而治之，把問題分為一個個的小部分來分别解決，再把結果組合起來。
快速排序隻是使用數組原本的空間進行排序，是以所占用的空間應該是常量級的，但是由于每次劃分之後是遞歸調用，是以遞歸調用在運作的過程中會消耗一定的空間，在一般情況下的空間複雜度為 O(logn)，在最差的情況下，若每次隻完成了一個元素，那麼空間複雜度為 O(n)。是以我們一般認為快速排序的空間複雜度為 O(logn)。
快速排序是一個不穩定的算法
，在經過排序之後，可能會對相同值的元素的相對位置造成改變。
快速排序基本上被認為是相同數量級的所有排序算法中，平均性能最好的
。