1司训、快排的核心思想：
1构捡、從無序的數(shù)組中找到一個樞軸元素M，將數(shù)組一分為二：如將數(shù)組的第一個元素設(shè)置為樞軸元素壳猜。
2勾徽、然后從數(shù)組的左右開始找元素：
滿足的規(guī)則是
a、從右側(cè)開始找比樞軸元素M小的元素统扳，如果找到將該元素X（right）跟樞軸元素M交換位置喘帚，即更小的數(shù)字換到了數(shù)組前面。
b咒钟、再從左側(cè)開始找比樞軸元素M大的元素吹由，如果找到將該元素Y（left）跟樞軸元素M交換位置，即更大的數(shù)字換到了數(shù)組后面朱嘴。
c倾鲫、對a,b步驟交替進行。
d萍嬉、最終的時候乌昔，right和left會重合 ，且該位置放置M元素壤追。`
3磕道、此時將數(shù)組，在M的前面都是比M小的元素行冰，在M的后面都是比M大的元素捅厂。
4、然后分別對M前面元素組成的數(shù)組资柔，M元素后的元素組成的數(shù)組遞歸調(diào)用2步驟封裝的方法即可
java版本代碼實現(xiàn)如下：
package com.example.demo.chapter06.controller;
import java.util.Arrays;
public class Solution {
public static void main(String[] args) {
quickSort(new int[] {39,28,55,87,66,3,17,40});
}
public static void quickSort(int[] arr) {
// 快排傳入的內(nèi)容： 數(shù)組焙贷，數(shù)組開始的位置，數(shù)組的末尾贿堰。
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
// arr 代表目標(biāo)數(shù)組
public static void quickSort(int[] arr, int left, int right) {
// 保存每次排序后辙芍，分界點的在數(shù)組中的位置
int middle;
if (left < right) {
// 返回每次排序后，分界點在數(shù)組中的位置羹与。比如返回的3故硅， 則是代表分界值在數(shù)組的第4個位置。
middle = partition(arr, left, right);
System.out.println(middle);
// 分別對于分界值兩側(cè)的數(shù)組纵搁，進行遞歸調(diào)用吃衅。
// 對于左側(cè)數(shù)組：left 第一次是傳入的初始位置， right則是分界值的位置-1腾誉。
// 對于右側(cè)數(shù)組徘层，left 是分界值的位置+1峻呕， right是最后的位置。
quickSort(arr, left, middle-1);
quickSort(arr, middle+1, right);
}
}
/**
*
* @param arr
* @param left
* @param right
* @return 最終分界值的索引位置趣效。
*/
public static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
while (left < right) {
// 當(dāng)右邊的元素如果比標(biāo)志位一直大的話瘦癌，就不斷執(zhí)行該循環(huán)。
// 當(dāng)從右側(cè)找到了比其小的元素跷敬，就將該元素與標(biāo)志位置交換位置讯私。
while (left < right && arr[right] >= pivot) {
right--;
}
// 將找到的數(shù)，放置到設(shè)置的目標(biāo)值上西傀。 此時arr[right]相當(dāng)于置為空了
arr[left] = arr[right];
// 左邊查找的方式. 當(dāng)遍歷元素小于標(biāo)識位的時候斤寇，進行移動。
while (left < right && arr[left] <= pivot) {
left++;
}
// 將找到的數(shù)拥褂，放置到設(shè)置的目標(biāo)值上抡驼。 此時arr[left]相當(dāng)于置為空了
arr[right] = arr[left];
}
// 將最終的目標(biāo)值（分界線值），放置到arr[left] 上
arr[left] = pivot;
return left;
}
}
測試結(jié)果：
2肿仑、時間復(fù)雜度分析：
時間復(fù)雜度分析：
①致盟、最好的情況，每次算的數(shù)據(jù)剛好將數(shù)組平均分成2個部分
說明：
根據(jù)代碼分析尤慰，每次的遞歸操作馏锡，該次遞歸傳入的元素個數(shù)，需要減去掉樞軸元素（1個元素并沒有傳遞給下一次遞歸）伟端，當(dāng)數(shù)據(jù)量足夠大的時候杯道，每次減去一個
元素對時間復(fù)雜度的影響不大，所以可暫時忽略责蝠。
第一輪操作党巾，頭尾指針加在一起會掃描整個數(shù)組. 共有n次操作 （忽略掉-1的軸樞元素）
第二輪操作，有2次遞歸操作霜医，每次有n/2次（忽略掉-1的軸樞元素）齿拂，共有n次操作。
第三輪操作肴敛，有4次遞歸操作署海，每次有n/4次， 共有n次操作医男。
第k輪操作砸狞， 有2k-1次遞歸草最，每次有n/(2k-1)次操作镀梭，共n次操作刀森。
遞歸結(jié)束的條件最后只有一個元素即 n/(2^l-1) = 1
解出 k= logn + 1, 及總共有k輪循環(huán)。
所以時間復(fù)雜度位 n * (logn + 1) 即為O（nlog2 n）
②报账、最壞時間復(fù)雜度
當(dāng)待排序的序列為正序或逆序排列時研底，且每次劃分只得到一個比上一次劃分少一個記錄的子序列埠偿，注意另一個為空。
如果遞歸樹畫出來飘哨，它就是一棵斜樹。此時需要執(zhí)行n‐1次遞歸調(diào)用琐凭，且第i次劃分需要經(jīng)過n‐i次關(guān)鍵字的比較才能找到第i個記錄芽隆，也就是樞軸的位置，因此比較次數(shù)為
最終其時間復(fù)雜度為O(n^2)统屈。
程序執(zhí)行結(jié)果：
初始數(shù)組為{9,8,7,6,5,4,3,2,1}
遞歸調(diào)用了n-1次
第1次劃分胚吁，需要8次排序才找到了軸樞元素9的位置：即將9月其他元素比較，得到9的位置愁憔，此時將數(shù)組分成{1, 8, 7, 6, 5, 4, 3, 2}和{}
第2次劃分腕扶，需要7次找到了軸樞元素1的位置： 即1與除掉9這個最大的其他元素作比較，得到1的位置吨掌。此時將數(shù)組分成{} 和 {8, 7, 6, 5, 4, 3, 2, 9}
第3次劃分半抱，需要6次找到了軸樞元素8的位置：及8與其他元素作比較，得到8位位置膜宋，此時將數(shù)組分為{1, 2, 7, 6, 5, 4, 3} 和 {}
第i次劃分窿侈，需要n-i次知道軸樞元素i的位置。
所以總的查找次數(shù)為： n-1 + n-2 + .... + 1 = n(n-1)/2
即時間復(fù)雜度為O(n^2)
