【基本思想】
Divide and Conquer分治思想
將原問(wèn)題分成若干規(guī)模更小，但結(jié)構(gòu)相似的小問(wèn)題媳拴。遞歸解決子問(wèn)題巩那，再把子問(wèn)題的解組合為原問(wèn)題的解捻艳。
【步驟】
- 基準(zhǔn)。選取一個(gè)元素作為基準(zhǔn)
- 分區(qū)。將小于/大于基準(zhǔn)的點(diǎn)分別放置在兩邊黎做，分區(qū)結(jié)束后蝙砌，基準(zhǔn)所在的位置即為它的最終位置
- 對(duì)基準(zhǔn)左右兩邊的數(shù)據(jù)集重復(fù)步驟1&2阳堕，知道所有子數(shù)據(jù)集只剩一個(gè)元素為止
【實(shí)例分析】
現(xiàn)有數(shù)組 Arr = [6 1 2 7 9 3 4 5 10 8]
- 選擇基準(zhǔn)，方便起見(jiàn)择克，選擇第一個(gè)6
-
交換基準(zhǔn)外的元素
兩個(gè)變量 i 和 j恬总，分別指向序列最左邊和最右邊i=0, j=9;
（先移動(dòng)j，知道i j相遇）
j 一步一步地向左挪動(dòng)（即 j--）肚邢，直到找到一個(gè)小于 6 的數(shù)停下來(lái);
i 再一步一步向右挪動(dòng)（即 i++）壹堰，直到找到一個(gè)數(shù)大于 6 的數(shù)停下來(lái);
--第一次交換--
image
image
[6 1 2 5 9 3 4 7 10 8]
--“探測(cè)”繼續(xù)--
i，j繼續(xù)移動(dòng)骡湖，j到了4位置贱纠，i到了9位置，交換
6 1 2 5 4 3 9 7 10 8
--“探測(cè)”繼續(xù)--
j 繼續(xù)向左挪動(dòng)谆焊，他發(fā)現(xiàn)了 3浦夷；i 繼續(xù)向右移動(dòng)，此時(shí)哨兵 i 和哨兵 j 相遇了罐孝。探索結(jié)束肥缔。 -
交換基準(zhǔn)
將基準(zhǔn)數(shù) 6 和 3 進(jìn)行交換。
3 1 2 5 4 6 9 7 10 8 -
拆分序列，繼續(xù)探索
以 6 為分界點(diǎn)拆分成了兩個(gè)序列姑宽，左邊的序列是“3 1 2 5 4”，右邊的序列是“ 9 7 10 8 ”舵变。接下來(lái)還需要分別處理這兩個(gè)序列。
3 1 2 5 4 ==> 2 1 3 5 4
2 1 ==> 1 2 5 4 ==> 4 5
【偽代碼】
【JAVA代碼實(shí)現(xiàn)】
public static void main(String[] args)
{
// TODO Auto-generated method stub
int[] arr = {6,1,2,7,9,3,4,5,10,8};
quick_sort(arr, 0, arr.length-1);
for(int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void quick_sort(int[] arr, int l, int r) {
if(l < r) {
int i = l+1, j = r;
int p = arr[l];
while(i <= j) {
while(i <= j && arr[i] <= p) {
i = i+1;
}
while(i <= j && arr[j] > p) {
j = j-1;
}
if(i < j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
if(l < j) {
int tmp = arr[l];
arr[l] = arr[j];
arr[j] = tmp;
quick_sort(arr, l, j-1);
}
if(j < r) {
quick_sort(arr, j+1, r);
}
}
}
==>1 2 3 4 5 6 7 8 9 10
【性能分析】
快速排序的時(shí)間性能取決于快速排序遞歸的深度赊豌，可以用遞歸樹(shù)來(lái)描述遞歸算法的執(zhí)行情況绵咱。
1. 最優(yōu)
時(shí)間復(fù)雜度為O(nlogn)
最優(yōu)的情況，每次Partition都劃分得很均勻艾恼。遞歸樹(shù)的深度就為.logn.+1(.x.表示不大于x的最大整數(shù))麸锉，需要遞歸logn次，時(shí)間為T(mén)(n)
T（n）≤2T（n/2） +n花沉，T（1）=0
T（n）≤2（2T（n/4）+n/2） +n=4T（n/4）+2n
T（n）≤4（2T（n/8）+n/4） +2n=8T（n/8）+3n
……
T（n）≤nT（1）+（log2n）×n= O(nlogn)
2. 最壞
時(shí)間復(fù)雜度為O(n^2)
待排序的序列為正序或者逆序，每次劃分只得到一個(gè)比上一次劃分少一個(gè)記錄的子序列磷脯，注意另一個(gè)為空娩脾。如果遞歸樹(shù)畫(huà)出來(lái)，它就是一棵斜樹(shù)晦雨。
需要執(zhí)行n‐1次遞歸調(diào)用隘冲，且第i次劃分需要經(jīng)過(guò)n‐i次關(guān)鍵字的比較才能找到第i個(gè)記錄，也就是樞軸的位置
因此比較次數(shù)為
3. 平均
O(nlogn)
設(shè)樞軸的關(guān)鍵字應(yīng)該在第k的位置（1≤k≤n）
4. 空間復(fù)雜度
遞歸造成的棸掠剩空間
最好情況罗珍，遞歸樹(shù)的深度為log2n，其空間復(fù)雜度也就為O(logn)
最壞情況蘸朋，需要進(jìn)行n‐1遞歸調(diào)用扣唱，其空間復(fù)雜度為O(n)
平均情況团南，空間復(fù)雜度也為O(logn)
5. 穩(wěn)定性
由于關(guān)鍵字的比較和交換是跳躍進(jìn)行的炼彪，所以為不穩(wěn)定算法
【應(yīng)用：常見(jiàn)面試題目】
- 找出數(shù)組中最小/大的k個(gè)數(shù)
- 數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的數(shù)字
- 找出數(shù)組中第k個(gè)最小的數(shù)
- 荷蘭旗問(wèn)題
參考：
http://wiki.jikexueyuan.com/project/easy-learn-algorithm/fast-sort.html
https://blog.csdn.net/weshjiness/article/details/8660583
