快速排序算法
思路：選擇基準(zhǔn)數(shù)，將所有小于基準(zhǔn)數(shù)的移動到基準(zhǔn)數(shù)的左邊，大于的移動到右邊，之后采用分治思想，遞歸調(diào)用。
步驟如下：
首先，需要一個待排序的數(shù)組。
將第一個數(shù)，也就是8作為基準(zhǔn)數(shù)，分別在數(shù)組頭和尾各設(shè)置一個哨兵A和B。
哨兵B負(fù)責(zé)向左移動，找到一個小于基準(zhǔn)數(shù)的值之后停下，將值B位置的值賦值給A所在位置，也就是將8改成7，將A的位置向后移動一位。（因?yàn)槟康氖菍⑿∮诨鶞?zhǔn)數(shù)的值放到基準(zhǔn)數(shù)左邊，7已經(jīng)小于8了，所以A = A + 1，將A指向20的位置）
之后A開始移動，發(fā)現(xiàn)本身位置20大于temp，那么不用繼續(xù)移動了，直接將20賦值給B所在位置，B向前移動一位。（同理）
第一次移動的一定是B哨兵而不是哨兵A，讀者可以先自己思考為什么這樣做，后面會給出答案。
移動到下圖的時候注意，此時應(yīng)該是B繼續(xù)向前搜索小于temp的值。
結(jié)果發(fā)現(xiàn)，當(dāng)B移動到A位置時，發(fā)現(xiàn)也沒有找到小于temp的數(shù)，這時就需要把temp這個基準(zhǔn)數(shù)插入到這個位置，結(jié)束一輪尋找。
至此我們發(fā)現(xiàn)，8左邊的數(shù)都小于8，右邊的數(shù)都大于8，這就完成了一次操作。
之后采用分治法，將8左邊的序列當(dāng)作一個數(shù)組，右邊的序列當(dāng)做一個數(shù)組，對兩個數(shù)組都進(jìn)行上面的操作（也就是重新傳入排序方法中，進(jìn)行遞歸調(diào)用）。
總結(jié)
- 主要的判斷條件是A是否小于B，如果小于B就結(jié)束尋找將基準(zhǔn)數(shù)插入。
- 為什么一定要從哨兵B先開始呢？其實(shí)自己實(shí)驗(yàn)一下就能知道為什么。
這里如果賦值了的話，那么15就變成20，15這個數(shù)就丟失了，你可能會想，我可以拿一個數(shù)先把15記錄下來呀，這樣做可以，我們假設(shè)用temp1記錄下15，之后繼續(xù)向下走，我們走到最后，如下圖。
將基準(zhǔn)數(shù)8加入到arr[3]這個位置。那么temp1該如何處理呢，賦值到arr[0]位置嗎，如果這樣做，那8的左邊就出現(xiàn)了一個大于8的數(shù)字，違反了快速排序的條件。
全部代碼如下
/**
* Created by ShouJingGuo on 2018/3/14.
* 快速排序
*/
public class QuickSort<T> {
private Comparator<T> comparator;
QuickSort(Comparator<T> comparator){
if(comparator == null){
throw new NullPointerException("比較器不能為null");
}
this.comparator = comparator;
}
public void quickSort(T[] arr){
int i = 0, j = arr.length - 1;
quickSort(arr, i, j);
}
private void quickSort(T[] arr, int left, int right){
if(left < right) {
int i = left, j = right;
T temp = arr[left];
while (i < j) {
while ((i < j) && (comparator.compare(temp, arr[j]) < 0)) {
j--;
}
if (i < j) {
arr[i++] = arr[j];
}
while ((i < j) && (comparator.compare(temp, arr[i]) > 0)) {
i++;
}
if (i < j) {
arr[j--] = arr[i];
}
}
arr[i] = temp;
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
}
public static void main(String[] args) {
Integer arr[] = {10,50,24,11,68,20,41,0,24,25,4,7,94,15,5,44,66};
QuickSort<Integer> quickSort = new QuickSort<>(new IntegerComparator());
quickSort.quickSort(arr);
System.out.println(Arrays.toString(arr));
}
}
