Java深入淺出理解快速排序以及優化方式
可能經常看面經的同學都知道，面試所遇到的排序算法，快速排序占主要位置，熱度隻增不減啊，其次就是歸並和堆排序。
其實以前寫過一篇排序的文章，寫的比較簡單，隻是輕描淡寫。今天我再次重新拿起筆，將快速排序的幾大優化，再次一一講述一遍。各位同學，讀完這篇文章，如若對你能夠帶來一些感悟，記得給個大大的贊哦！！！
前言
快速排序是在冒泡排序的基礎之上，再次進行優化得來的。具體的步驟如下：
- 在待排序的序列中，選取一個數值，將大於它的數放到數組的右邊，小於它的數放到數組的左邊，等於它的數就放到數組的中間。
- 此時，相對於上一步挑選出來的數值而言，此時數組的左部分都小於它，右部分都大於它。達到“相對有序”。
- 然後，遞歸左部分和右部分，重復以上操作即可。
流程知道後，問題就在於如何選取這個基準值？我們有以下幾種選取基準值和優化的方法：
- 挖坑法
- 隨機取值法
- 三數取中法
- 荷蘭國旗問題優化
以上四種，筆試最容易考到的代碼題就是挖坑法，可能最難理解的就是荷蘭國旗問題帶來的優化。要想拿到一個好的offer，以上必須全部掌握，並且還得學會寫非遞歸版本的代碼（非遞歸比較簡單）。
本期文章源碼：GitHub
以下所有講解，可能會頻繁用到如下交換數值的方法，這裡提前寫瞭：
public void swap(int[] array, int L, int R) {
int tmp = array[L];
array[L] = array[R];
array[R] = tmp;
}
一、挖坑法
挖坑法：默認將數組的第一個數值作為基準值。然後做以下步驟：
- 第一、從數組的最後開始遍歷（下標R），找到第一個小於基準值的數值。然後將小於的這個數值放入上次空出來的位置（第一次就是基準值的位置）
- 第二、上一步將小於的數值交換位置後，空出來的位置用於：在數組的前面找到第一個大於基準值的數值（下標L），放到這個空出來的位置。
- 循環以上兩個步驟，直到遍歷到L==R時，循環停止
看如下長圖：
挖坑法，就類似於，我先拿出基準值，此時基準值的位置就空出來瞭，需要從後面的數值拿一個數來補這個空位置；補完之後，後面的位置又空出來瞭，此時再從前面的數組找一個數去補後面的空位置，循環往復，知道L和R相遇。再把基準值放入此時的L位置即可。
此時，整個數組，就從基準值位置分為瞭兩部分，分別遞歸左部分和右部分即可。
//挖坑法-升序
public int partition(int[] array, int L, int R) {
int tmp = array[L]; //保存基準值
while (L < R) {
//先從右邊找一個數
while (L < R && array[R] >= tmp) {
R--; //找小於基準值的數
}
array[L] = array[R];
//再從左邊找一個數
while (L < R && array[L] <= tmp) {
L++; //找大於基準值的數
}
array[R] = array[L];
}
array[L] = tmp; //將基準值放入中間位置
return L; //返回此時基準值的下標，用於將數組分為兩部分
}
特別值得註意的是，在數組左右兩邊查找一個數的時候，while循環的判斷（L<R && array[R] <= tmp）; 此時的等於號，切記不能少瞭，因為當待排序數組中有相同的數據時，會導致死循環。
主方法調用如下：
public void quick(int[] array, int L, int R) {
if (L >= R) {
return;
}
int p = partition(array, L, R); //返回基準值的下標
quick(array, L, p - 1); //遞歸左半部分
quick(array, p + 1, R); //遞歸右半部分
}
二、隨機取值法
隨機取值法：就是在數組范圍內，隨機抽取一個數值，作為基準值，這裡與挖坑法不同的是：挖坑法每次固定以數組的第一個數為基準值，而隨機取值法，則是隨機的。此時這種優化搭配著挖坑法，有更快的效率。主方法代碼如下：
public void quick2(int[] array, int L, int R) {
if (L >= R) {
return;
}
int index = L + (int)((R - L) * Math.random()); //生成L~R之間的隨機值
//為瞭好理解，我將這個隨機值放到數組開頭。也可以不交換，隻需改partition即可
swap(array, L, index);
int p = partition(array, L, R); //調用挖坑法
quick2(array, L, p - 1); //遞歸左半部分
quick2(array, p + 1, R); //遞歸右半部分
}
三、三數取中法
三數取中法：原意是，隨機生成數組范圍內的三個數，然後取三者的中間值作為基準值。但是在後序變化中，就沒有隨機生成，而是直接以數組的第一個數、最後一個數和中間數，這三個位置的數，取中間值，作為基準值。也是搭配著挖坑法來使用的，與隨機取值法一樣，都是起到優化的作用。
public void quick3(int[] array, int L, int R) {
if (L >= R) {
return;
}
threeNumberMid(array, L, R); //三數取中，並將中間值，放到數組最前面
int p = partition(array, L, R);
quick3(array, L, p - 1);
quick3(array, p + 1, R);
}
private void threeNumberMid(int[] array, int L, int R) {
int mid = L + ((R - L) >> 1); //中間值
if (array[L] > array[R]) {
swap(array, L, R);
}
if (array[L] > array[mid]) {
swap(array, L, mid);
}
if (array[mid] > array[R]) {
swap(array, mid, R);
}
//以上三個if過後，這三個數就是一個升序
//然後將中間值，放到數組的最前面
swap(array, L, mid);
}
四、荷蘭國旗問題優化
荷蘭國旗問題所帶來的優化，有明顯是優於挖坑法的。在以後的使用中，可能這種優化可能會多一點。
至於為什麼叫荷蘭國旗問題所帶來的優化。大傢去百度查一下這關鍵字即可，我們這裡就不多說瞭。
原意是：給定一個數組，將這個數組，以某一個基準值，整體分為三個區域（大於區，小於區、等於區）。然後再去遞歸小於區和大於區的范圍。這就是荷蘭國旗問題所帶來的優化思想，不同於挖坑法的是，這種優化，會將所有等於基準值的數，都聚集在中間，這樣的話，分別去遞歸左右兩邊的子數組時，范圍上就有一定的縮小。
具體步驟：
- 有三個變量（less，more，index）。分別表示小於區的右邊界、大於區的左邊界，index則表示遍歷當前數組的下標值。less左邊都是小於基準值的，more右邊都是大於基準值的。如下圖：暫時先不看more范圍內的50，等會說明。
- index從左開始遍歷，每遍歷一個數，進行判斷，小於基準值，就劃分到
less區域；大於基準值就劃分到more區域；等於的話，不交換，index往後走就行。 - 循環上一走即可，直到index和more相遇就停止。
//偽代碼
public int[] partition(int[] array, int L, int R) {
int less = L - 1;
int more = R;
int index = L;
while (index < more) { //index和more相遇就停止
if (array[index] > 基準值) {
} else if (array[index] < 基準值) {
} else { //等於基準值時，index後移即可
index++;
}
}
//返回等於區的開始和結束下標即可。
}
以上就是荷蘭國旗問題的偽代碼，是不是感覺很簡單？？？返回的是一個數組，這個數組隻有兩個元素，第一個元素就是等於區的開始下標，第二個元素就是等於區的結束下標。
具體的思想我們講瞭，但是還是會遇到一個問題，那就是基準值的選擇。我們隻需套用前面講過的隨機取值法或者三數取中法即可。
我們前面將隨機取值法的時候，是將隨機抽取的基準值，放到數組的第一個元素的位置，然後再去調用partition方法，進行挖坑法的。這裡我們就換一下，將隨機抽取的基準值，放到數組的末尾。這也就是在上一張圖中，為什麼more范圍內的50是紅色的原因。因為它就是基準值，隻是暫時先放到瞭數組的最後而已。（當然，也可以像挖坑法一樣，放到數組的第一個元素位置，一樣的道理，隻是partition方法稍微修改一下初始值即可）。
既然我們將基準值放到瞭數組的末尾，那麼在while循環結束後，也就是index遍歷完之後，也需要將最後這個基準值放回到等於區的范圍。而此時數組狀態是這樣的：L……less是小於區，less+1 …… more – 1是等於區，more …… R是大於區。
我們將最後這個基準值放到等於區的末尾即可，也就是調用swap(array, more, R)。R是基準值的位置，more是大於區的開始位置。
所以完整的partition代碼如下：
//R位置就是基準值
public int[] partition(int[] array, int L, int R) {
if (L > R) {
return new int[] {-1, -1};
}
if (L == R) {
return new int[] {L, L};
}
int less = L - 1; //數組最前面開始為less
int more = R; //數組末尾，包括瞭最後的基準值
int index = L; //遍歷數組
while (index < more) {
if(array[index] > array[R]) { //大於區
swap(array, index, --more);
} else if (array[index] < array[R]) { //小於區
swap(array, index++, ++less);
} else { //等於區
index++;
}
}
swap(array, more, R); //將最後的基準值放回等於區
//此時的范圍：L …… less 是小於區。less+1 ……more 是等於區。more + 1 …… R是大於區
return new int[] {less+1, more};
}
特別值得註意的是，循環裡第一個if語句，大於基準值的時候，從與數組後面的元素交換。但是從數組後面交換過來的數據，並不知道大小情況，所以此時的index還不能移動，需再次判斷交換過來的數據才行。其他的註意地方就是less和more的變化，留意一下是前置++-- 。
主方法的調用：
public void quick(int[] array, int L, int R) {
if (L >= R) {
return;
}
int i = L + (int)((R - L) * Math.random()); //隨機值
swap(array, i, R); //放到數組的最後
int[] mid = partition(array, L, R); //返回的是等於區的范圍
quick(array, L, mid[0] - 1); //左半部分
quick(array, mid[0] + 1, R); //右半部分
}
五、非遞歸版本
講完瞭快速排序的挖坑法和荷蘭國旗問題的優化，剩下的就很簡單瞭。非遞歸的話，就是申請一個棧，棧裡壓入的是待排序數組的開始下標和結束下標。也就是說，這個入棧時，需要同時壓入兩個下標值的。彈出的時候，也是同時彈出兩個下標值的。
唯一的問題就在於，我該在什麼時候進行壓入？
- 當此時的右半部分隻有一個數據，或者沒有數據的時候，此時右半部分就不需要再入棧瞭。
- 同理，當此時左半部分隻有一個數據，或者沒有數據的時候，就不需要再入棧瞭。
以上兩點，推導出，當mid[1] + 1 >= R 時，不需要再壓入右半部分；當mid[0] - 1 <= L 時，就不需要再壓入左半部分。
則可反推：mid[1] + 1 < R時，就壓入；mid[0] – 1 > L 時，就壓入。則有如下代碼：
//非遞歸版本
public void quick(int[] array) {
Stack<Integer> stack = new Stack<>();
stack.push(0);
stack.push(array.length - 1);
while (!stack.isEmpty()) {
int R = stack.pop();
int L = stack.pop();
int[] mid = partition(array, L, R); //調用荷蘭國旗問題優化的代碼
if (mid[1] + 1 < R) {
stack.push(mid[1] + 1);
stack.push(R);
}
if (mid[0] - 1 > L) {
stack.push(L);
stack.push(mid[0] - 1);
}
}
}
非遞歸代碼，就是需要註意，先壓入數組的左邊界L，再壓入右邊界R，則彈出棧的時候，是先彈出R的值。這裡需要註意，不要反瞭。
快速排序的時間復雜度O(NlogN)，空間復雜度O(logN)，沒有穩定性。快速排序的時間復雜度，取決於基準值的選擇，基準值選在所有數據的中間，將左右部分的子數組平分，就是最優的，能達到O(NlogN)，如果選在所有數據的最小值或最大值，則時間復雜度就會退化為O(N^2)。
還有一個優化就是，當待排序數組的數據個數到達一定的范圍時，可直接使用插入排序，會比快速排序快一點點的。
好啦，本期更新就到此結束啦。以上全部就是快速排序的代碼，大傢需要多敲幾遍代碼，多過幾遍思路，這個排序算法就算收入囊中啦！
我們下期再見吧！！！
到此這篇關於Java深入淺出理解快速排序以及優化方式的文章就介紹到這瞭,更多相關Java 快速排序內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！