快速排序
首先選一個基準 pivot臼氨，然后過一遍數(shù)組掺喻，
- 把小于 pivot 的都挪到 pivot 的左邊芭届，
- 把大于 pivot 的都挪到 pivot 的右邊储矩。
這樣一來，這個 pivot 的位置就確定了褂乍，也就是排好了 1 個元素持隧。
然后對 pivot 左邊 ?? 的數(shù)排序，
對 pivot 右邊 ?? 的數(shù)排序逃片，
就完成了屡拨。
那怎么排左邊和右邊？
答：同樣的方法褥实。
所以快排也是用的分治法的思想呀狼。
「分」
選擇一個 pivot，就把問題分成了
- pivot 左邊
- pivot 右邊
這兩個問題损离。
「治」
就是最開始描述的方法哥艇，直到每個區(qū)間內沒有元素或者只剩一個元素就可以返回了。
「合」
放在一起自然就是僻澎。
但是如何選擇這個 pivot貌踏？
取中間的？
取第一個窟勃？
取最后一個祖乳？
舉個例子：{5, 2, 1, 0, 3}.
比如選最后一個，就是 3.
然后我們就需要把除了 3 之外的數(shù)分成「比 3 大」和「比 3 小」的兩部分秉氧，這個過程叫做 partition（劃分）眷昆。
這里我們仍然使用「擋板法」的思想，不用真的弄兩個數(shù)組來存這兩部分，而是用兩個擋板亚斋，把區(qū)間劃分好了垦藏。
我們用「兩個指針」（就是擋板）把數(shù)組分成「三個區(qū)間」，那么
- 左邊的區(qū)間用來放小于 pivot 的元素伞访；
- 右邊的區(qū)間用來放大于 pivot 的元素掂骏；
- 中間是未排序區(qū)間。
那么初始化時厚掷，我們要保證「未排序區(qū)間」能夠包含除了 3 之外的所有元素弟灼，所以
- 未排序區(qū)間 = [i, j]
這樣左邊和右邊的區(qū)間就成了：
- [0, i)：放比 3 小的數(shù)；
- (j, array.length -2]：放比 3 大的數(shù)
注意 ?? i, j 是不包含在左右區(qū)間里的呢冒黑。
那我們的目的是 check 未排序區(qū)間里的每一個數(shù)田绑，然后把它歸到正確的區(qū)間里，以此來縮小未排序區(qū)間抡爹，直到沒有未排序的元素掩驱。
從左到右來 check：
Step1.
5 > 3, 所以 5 要放在右區(qū)間里，所以 5 和 j 指向的 0 交換一下：
這樣 5 就排好了冬竟，指針 j --欧穴，這樣我們的未排序區(qū)間就少了一個數(shù)；
Step2.
0 < 3泵殴，所以就應該在左邊的區(qū)間涮帘，直接 i++；
Step3.
2 < 3笑诅，同理调缨，i++；
Step4.
1 < 3吆你，同理弦叶，i++；
所以當兩個指針錯位的時候妇多，我們結束循環(huán)伤哺。
但是還差了一步，3 并不在正確的位置上呀砌梆。所以還要把它插入到兩個區(qū)間中間默责，也就是和指針 i 交換一下。
齊姐聲明：這里并不鼓勵大家把 pivot 放最左邊咸包。
基本所有的書上都是放右邊桃序，既然放左右都是一樣的，我們就按照大家默認的烂瘫、達成共識的來媒熊，沒必要去“標新立異”奇适。
就比如圍棋的四個星位，但是講究棋道的就是先落自己這邊的星位芦鳍，而不是伸著胳膊去夠對手那邊的嚷往。
那當我們把 pivot 換回到正確的位置上來之后，整個 partition 就結束了柠衅。
之后就用遞歸的寫法皮仁，對左右兩邊排序就好了。
最后還有兩個問題想和大家討論一下：
- 回到我們最初選擇 pivot的問題菲宴，每次都取最后一個贷祈，這樣做好不好？
答：并不好喝峦。
因為我們是想把數(shù)組分割的更均勻势誊，均勻的時間復雜度更低；但是如果這是一個有序的數(shù)組谣蠢，那么總是取最后一個是最不均勻的取法粟耻。
所以應該隨機取 pivot，這樣就避免了因為數(shù)組本身的特點總是取到最值的情況眉踱。
- pivot 放在哪
隨機選取之后挤忙，我們還是要把這個 pivot 放到整個數(shù)組的最右邊，這樣我們的未排序區(qū)間才是連續(xù)的勋锤，否則每次走到 pivot 這里還要想著跳過它饭玲，心好累哦。
class Solution {
public void quickSort(int[] array) {
if (array == null || array.length <= 1) {
return;
}
quickSort(array, 0, array.length - 1);
}
private void quickSort(int[] array, int left, int right) {
// base case
if (left >= right) {
return;
}
// partition
Random random = new Random(); // java.util 中的隨機數(shù)生成器
int pivotIndex = left + random.nextInt(right - left + 1);
swap(array, pivotIndex, right);
int i = left;
int j = right-1;
while (i <= j) {
if (array[i] <= array[right]) {
i++;
} else {
swap(array, i, j);
j--;
}
}
swap(array, i, right);
//「分」
quickSort(array, left, i-1);
quickSort(array, i+1, right);
}
private void swap(int[] array, int x, int y) {
int tmp = array[x];
array[x] = array[y];
array[y] = tmp;
}
}
這里的時空復雜度和分的是否均勻有很大關系叁执，所以我們分情況來說：
1. 均分
時間復雜度
如果每次都能差不多均勻分，那么
- 每次循環(huán)的耗時主要就在這個 while 循環(huán)里矮冬，也就是 O(right - left)谈宛；
- 均分的話那就是 logn 層；
- 所以總的時間是 O(nlogn).
空間復雜度
- 遞歸樹的高度是 logn胎署，
- 每層的空間復雜度是 O(1)吆录，
- 所以總共的空間復雜度是 O(logn).
2. 最不均勻
如果每次都能取到最大/最小值，那么遞歸樹就變成了這個樣子：
時間復雜度
如上圖所示：O(n^2)
空間復雜度
這棵遞歸樹的高度就變成了 O(n).
3. 總結
實際呢琼牧，大多數(shù)情況都會接近于均勻的情況恢筝，所以均勻的情況是一個 average case.
為什么看起來最好的情況實際上是一個平均的情況呢？
因為即使如果沒有取到最中間的那個點巨坊，比如分成了 10% 和 90% 兩邊的數(shù)撬槽，那其實每層的時間還是 O(n)，只不過層數(shù)變成了以 9 為底的 log趾撵，那總的時間還是 O(nlogn).
所以快排的平均時間復雜度是 O(nlogn)侄柔。
穩(wěn)定性
那你應該能看出來了，在 swap 的時候，已經破壞了元素之間的相對順序暂题，所以快排并不具有穩(wěn)定性移剪。
這也回答了我們開頭提出的問題，就是
-
為什么對于 primitive type 使用快排薪者，
- 因為它速度最快纵苛；
-
為什么對于 object 使用歸并，
- 因為它具有穩(wěn)定性且快言津。
以上就是快排的所有內容了赶站，也是很常考的內容哦纺念！那下一篇文章我會講幾道從快排引申出來的題目贝椿，猜猜是什么？??
如果你喜歡這篇文章陷谱，記得給我點贊留言哦～你們的支持和認可烙博，就是我創(chuàng)作的最大動力，我們下篇文章見烟逊！
我是小齊渣窜，紐約程序媛，終生學習者宪躯，每天晚上 9 點乔宿，云自習室里不見不散！
更多干貨文章見我的 Github: https://github.com/xiaoqi6666/NYCSDE
