可能經常看面經的同學都知道，面試所遇到的排序演算法，快速排序占主要位置，熱度只增不減啊，其次就是歸并和堆排序，

其實以前寫過一篇排序的文章，寫的比較簡單，只是輕描淡寫，今天我再次重新拿起筆，將快速排序的幾大優化，再次一一講述一遍，各位同學，讀完這篇文章，如若對你能夠帶來一些感悟，記得給個大大的贊哦！！！

前言

快速排序是在冒泡排序的基礎之上，再次進行優化得來的，具體的步驟如下：

在待排序的序列中，選取一個數值，將大于它的數放到陣列的右邊，小于它的數放到陣列的左邊，等于它的數就放到陣列的中間，
此時，相對于上一步挑選出來的數值而言，此時陣列的左部分都小于它，右部分都大于它，達到“相對有序”，
然后，遞回左部分和右部分，重復以上操作即可，

流程知道后，問題就在于如何選取這個基準值？我們有以下幾種選取基準值和優化的方法：

挖坑法
隨機取值法
三數取中法
荷蘭國旗問題優化

以上四種，筆試最容易考到的代碼題就是挖坑法，可能最難理解的就是荷蘭國旗問題帶來的優化，要想拿到一個好的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)，

還有一個優化就是，當待排序陣列的資料個數到達一定的范圍時，可直接使用插入排序，會比快速排序快一點點的，

好啦，本期更新就到此結束啦，以上全部就是快速排序的代碼，大家需要多敲幾遍代碼，多過幾遍思路，這個排序演算法就算收入囊中啦！

我們下期再見吧！！！

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/337755.html

標籤：其他

上一篇：C語言基礎之分支陳述句