前言
本篇部落格是在伍迷兄的部落格基礎上進行的，其部落格位址。
希爾排序相當于直接插入排序的優化，它們同屬于插入排序類，堆排序相當于簡單選擇排序的優化，它們同屬于選擇排序類。而快速排序其實就是冒泡排序的更新，它們都屬于交換排序類。即它也是通過不斷的比較和移動交換來實作排序的，隻不過它的實作，增大了記錄的比較和移動的距離，将關鍵字較大的記錄從前面直接移動到後面，關鍵字較小的記錄從後面直接移動到前面，進而減少了總的比較次數和移動交換次數，而不是像冒泡排序那樣左右兩兩進行比較和交換。
說白了，其實就是在冒泡排序的基礎上加入了記憶的功能，類似堆排序于簡單選擇排序，冒泡排序兩兩左右比較之後是沒有記住兩者大小關系的，下輪比較的時候兩者比較還是如他們第一次比較一樣，彼此不認識；而快速排序，他選取了一個樞紐值，使得樞紐值左右兩邊的元素有個大小關系，那麼樞紐值左邊的就不需要與樞紐值右邊的進行比較了。
基本思想
通過一趟排序将待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分别對這兩部分記錄繼續進行排序，以達到整個序列有序的目的；就是選擇一個關鍵字，通過一趟排序（進行比較和移動）使得關鍵字的左邊都比他小（或者大）、右邊都比他大（或者小），然後對他的左邊元素和右邊元素分别進行排序，以此直至整個序列有序。
從字面可能不太好了解，那麼我們來看代碼，假設初始序列為{5,3,7,9,1,6,4,8,2}。
代碼實作
/**
* 快速排序
* @param arr
*/
private static void quickSort(int[] arr) {
qSort(arr,0,arr.length-1);
}
/**
* 對序列arr中的子序列arr[low..high]作快速排序
* @param arr
* @param low
* @param high
*/
private static void qSort(int[] arr, int low, int high) {
int pivotKey;
if(low < high){
// 找到樞紐值的位置，此時arr[low,pivotKey-1]都小于(大于)arr[pivotKey],arr[pivotKey+1...high]都大于(小于)arr[pivotKey]
pivotKey = partition(arr,low,high);
qSort(arr,low,pivotKey-1); // 對arr[low...pivotKey-1]進行快速排序
qSort(arr,pivotKey+1,high); // 對arr[pivotKey+1...high]進行快速排序
}
} partition(arr,low,high);”，在執行它之前，arr的數組值為{5,3,7,9,1,6,4,8,2}。partition函數要做的，就是先選取當中的一個關鍵字，比如選擇第一個關鍵字5，然後想盡辦法将它放到一個位置，使得它左邊的值都比它小，右邊的值比它大，我們将這樣的關鍵字稱為樞軸。
在經過partition(arr,0,9)的執行之後，數組變成{2,3,4,1,5,6,9,8,7}，并傳回值樞紐值的下标4給pivotKey，數字4表明元素5放置在數組下标為4的位置。此時，程式把原來的數組變成了兩個位于元素5左和右的小數組{2,3,4,1}和
{6,9,8,7}，然後分别對子序列進行快速排序。
到了這裡，應該說了解起來還不算困難。partition的作用相當于賦予了程式記憶功能，進而來提高速度。下面我們就來看看快速排序最關鍵的partition方法實作是怎麼樣的。
1 /**
2 * 尋找樞紐值的下标，并傳回
3 * 交換arr[low...high]中的元素，移動樞紐值到正确的位置
4 * @param arr
5 * @param low
6 * @param high
7 * @return
8 */
9 private static int partition(int[] arr, int low, int high) {
10 int pivotValue = arr[low]; // 選取arr[low]當作樞紐值
11 // 從兩端向中間掃描，使樞紐值移動到正确的位置
12 while(low < high){
13 while(low<high && arr[high]>=pivotValue){
14 high --;
15 }
16 swap(arr,low,high); // 将比樞紐值小的記錄交換到低端
17 while(low<high && arr[low]<=pivotValue){
18 low ++;
19 }
20 swap(arr,low,high); // 将比樞紐值大的記錄交換到高端
21 }
22 return low;
23 } 執行過程模拟
partition方法，那麼我們就來模拟一下這個方法的執行過程
1）初始時，low=0，high=8，pivotValue=arr[low]=5,如下圖
pivotValue不滿足，跳出循環，執行16行，交換5和2，此時，序列如下圖
執行17～19行，循環條件滿足，low++後，low=1，繼續執行循換，條件依然滿足，low++，low=2，繼續執行循環，此時循環條件不滿足，跳出循環，執行20行，交換arr[low=2]和arr[high=8]即7和5，過程如下圖
3）内部循環結束，繼續執行外部循環，回到12行，low<high，繼續執行内部循環，執行13～15行
條件滿足，執行循環體，high--，high=7，繼續執行循環，條件滿足，執行循環體，high--，那麼high=6，繼續執行循環，條件不滿足，交換arr[low=2]和arr[high=6]，即交換5和4，執行過程如下
接下來執行17～19行，循環條件滿足，low++，那麼low=3，繼續執行循環，條件不滿足，跳出循環，執行20行，交換arr[low=3]和arr[high=6],即交換9和5，執行過程如下
4）内部循環結束，繼續執行外部循環，條件滿足，繼續執行内部循環
執行13～15行，條件滿足，high--，那麼high=5，繼續執行循環，條件滿足，high--，此時high=4，條件不滿足，跳出循環，執行16行，交換arr[low=3]和arr[high=4],即交換5和1,執行過程如下如
接下來執行18～19行，條件滿足，low++，那麼low=4，繼續執行循環，條件不滿足，跳出循環，交換arr[low=4]和arr[high=4],即交換5和5，過程圖就不提供了，比較簡單容易了解
關鍵字5已經找到正确的位置即4，并将該位置的索引4傳回，序列為{2,3,4,1,5,6,9,8,7}