本文為原創，歡迎轉載，轉載請注明出處BlogJava。
快速排序的算法思想：
快速排序采用了分治的策略，將原問題分解為若干個規模更小但結構與原問題相似的子問題。用遞歸方法解決子問題，然后將這些子問題的解組合為原問題的解。
快速排序的程序的一般過程可簡單描述為：
1.用統一的方法取得 pivot(軸)。
2.根據pivot 對已有數組進行排序
1) 將array[pivot]存儲在tmp變量中，作為比較基準。
以low、high分別從前向后、從后向前遍歷數組
2) 從后向前遍歷，找到第一個小于tmp的數，將其移動到low的位置。
3) 從前向后遍歷，找到第一個大于tmp的數，將其移動到high的位置。
4) 循環2、3步，直到兩指針重疊(即退出循環的條件是 low >= high)，將tmp移動到low(此時low與high重合)的位置，并將low返回成為新的pivot。
5) 根據4步返回的pivot，對已有數組進行劃分，0～pivot-1 和 pivot+1 ～ array.lenght，遞歸1～5步。直到調用退出。
相信對于以上理論大家一定是耳熟能詳了，但理解起來還是比較抽象，下面我就用Excel畫圖簡單的描述一下 快速排序 的過程。
假設我們要寫一個程序對已有數組進行排序，簡單起見，設定待排序數組為 int[] array = { 4, 2, 1, 7, 5, 3, 8, 6 }。對其用快速排序算法進行排序，過程描述如下：
1.根據已有待排序數組，取得pivot，我在這里取得pivot的策略就是 取 數組的第一個數，這里即為 4。
tmp = 4；
待排序數組：黃色底色表示pivot。
2.從后向前移動high，找到第一個小于tmp的數，則將該數移動到low的位置。
3.從前向后移動low，找到第一個大于tmp（4）的數，將其移動到high的位置。
4.然后再向前移動high，試圖找到第一個小于tmp(4)的數，但沒有找到，此時low與high重疊，將tmp的值放入low的位置，并將low作為pivot返回。
根據新的pivot進行遞歸調用，將原待排序數組 分解為兩塊，index區間分別為0～2，4～7，即以下兩個子數組
(并未新建數組，只是只關注這個區間的數據，對其進行排序，也就是將問題分解為兩個小的子問題，但問題很類似。)
這兩個數組的排序過程這里就不畫了，一樣的過程。
下面來看看實現的代碼，與剛剛的過程描述是符合的：
package com.bz.sort.algorithm;
public class QuickSort 
{
/** *//**
* 對外調用的方法入口。
* @param array 待排序數組
*/
public void sort(int[] array) {
if (array == null || array.length < 0) {
throw new RuntimeException("待排序數組中無數據。");
}
// 排序
sort(array, 0, array.length - 1);
}
/** *//**
* 快速排序。
* @param arr 待排序數組
* @param left 關注的區間
* @param right 關注的區間
*/
private void sort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
// 取得pivot位置，這里的策略是取得最小的index，即返回left
int pivot = findPivot(arr, left, right);
// 排序并重新計算出pivot
pivot = partion(arr, left, right, pivot);
// 以pivot為中心將原數組分解成兩塊，遞歸排序
sort(arr, left, pivot - 1);
sort(arr, pivot + 1, right);
}
/** *//**
* 排序并返回新的pivot
* @param arr 待排序數組
* @param left 區間
* @param right 區間
* @param pivot 軸
* @return
*/
private int partion(int[] arr, int left, int right, int pivot) {
int tmp = arr[pivot];
int low = left;
int high = right;
while (low < high) {
// 從后向前遍歷數組，找到第一個小于arr[pivot]的數
while (low < high && tmp < arr[high]) {
high--;
}
arr[low] = arr[high];
// 從前向后遍歷數組，找到第一個大于arr[pivot]的數
while (low < high && tmp >= arr[low]) {
low++;
}
arr[high] = arr[low];
}
// 此時low與high重合，將tmp的值移動到low的位置
arr[low] = tmp;
// 將low當作新的pivot返回
return low;
}
/** *//**
* 取得排序的軸
* @param array
* @return
*/
protected int findPivot(int[] array, int left, int right) {
if (array == null || array.length < 0) {
throw new RuntimeException("待排序數組中無數據。");
}
// 選擇第一個元素為軸
return left;
}
}
測試代碼如下：
package com.bz.sort.algorithm;
import org.junit.Test;
import junit.framework.Assert;
public class QuickSortTest {
@Test
public void testSort() {
int[] array = { 4, 2, 1, 7, 5, 3, 8, 6 };
QuickSort qs = new QuickSort();
qs.sort(array);
for (int i = 0; i < array.length - 1; i++) {
Assert.assertTrue(array[i] <= array[i + 1]);
}
}
}
注：此代碼只為 演示 排序過程。