可能經(jīng)?？疵娼?jīng)的同學(xué)都知道，面試所遇到的排序算法，快速排序占主要位置，熱度只增不減啊，其次就是歸并和堆排序。

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

前言

快速排序是在冒泡排序的基礎(chǔ)之上，再次進(jìn)行優(yōu)化得來的。具體的步驟如下：

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

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

• 挖坑法
• 隨機(jī)取值法
• 三數(shù)取中法
• 荷蘭國旗問題優(yōu)化

以上四種，筆試最容易考到的代碼題就是挖坑法，可能最難理解的就是荷蘭國旗問題帶來的優(yōu)化。要想拿到一個好的offer，以上必須全部掌握，并且還得學(xué)會寫非遞歸版本的代碼（非遞歸比較簡單）。

本期文章源碼：GitHub

以下所有講解，可能會頻繁用到如下交換數(shù)值的方法，這里提前寫了：

public void swap(int[] array, int L, int R) {
    int tmp = array[L];
    array[L] = array[R];
    array[R] = tmp;
}

一、挖坑法

挖坑法：默認(rèn)將數(shù)組的第一個數(shù)值作為基準(zhǔn)值。然后做以下步驟：

• 第一、從數(shù)組的最后開始遍歷（下標(biāo)R），找到第一個小于基準(zhǔn)值的數(shù)值。然后將小于的這個數(shù)值放入上次空出來的位置（第一次就是基準(zhǔn)值的位置）
• 第二、上一步將小于的數(shù)值交換位置后，空出來的位置用于：在數(shù)組的前面找到第一個大于基準(zhǔn)值的數(shù)值（下標(biāo)L），放到這個空出來的位置。
• 循環(huán)以上兩個步驟，直到遍歷到L==R時，循環(huán)停止

看如下長圖：

挖坑法，就類似于，我先拿出基準(zhǔn)值，此時基準(zhǔn)值的位置就空出來了，需要從后面的數(shù)值拿一個數(shù)來補(bǔ)這個空位置；補(bǔ)完之后，后面的位置又空出來了，此時再從前面的數(shù)組找一個數(shù)去補(bǔ)后面的空位置，循環(huán)往復(fù)，知道L和R相遇。再把基準(zhǔn)值放入此時的L位置即可。

此時，整個數(shù)組，就從基準(zhǔn)值位置分為了兩部分，分別遞歸左部分和右部分即可。

//挖坑法-升序
public int partition(int[] array, int L, int R) {
    int tmp = array[L]; //保存基準(zhǔn)值
    while (L < R) {
        //先從右邊找一個數(shù)
        while (L < R && array[R] >= tmp) {
            R--; //找小于基準(zhǔn)值的數(shù)
        }
        array[L] = array[R];
        
        //再從左邊找一個數(shù)
        while (L < R && array[L] <= tmp) {
            L++; //找大于基準(zhǔn)值的數(shù)
        }
        array[R] = array[L];
    }
    array[L] = tmp; //將基準(zhǔn)值放入中間位置
    return L; //返回此時基準(zhǔn)值的下標(biāo)，用于將數(shù)組分為兩部分
}

特別值得注意的是，在數(shù)組左右兩邊查找一個數(shù)的時候，while循環(huán)的判斷（L<R && array[R] <= tmp）; 此時的等于號，切記不能少了，因為當(dāng)待排序數(shù)組中有相同的數(shù)據(jù)時，會導(dǎo)致死循環(huán)。

主方法調(diào)用如下：

public void quick(int[] array, int L, int R) {
    if (L >= R) {
        return;
    }
    int p = partition(array, L, R); //返回基準(zhǔn)值的下標(biāo)
    quick(array, L, p - 1); //遞歸左半部分
    quick(array, p + 1, R); //遞歸右半部分
}

二、隨機(jī)取值法

隨機(jī)取值法：就是在數(shù)組范圍內(nèi)，隨機(jī)抽取一個數(shù)值，作為基準(zhǔn)值，這里與挖坑法不同的是：挖坑法每次固定以數(shù)組的第一個數(shù)為基準(zhǔn)值，而隨機(jī)取值法，則是隨機(jī)的。此時這種優(yōu)化搭配著挖坑法，有更快的效率。主方法代碼如下：

public void quick2(int[] array, int L, int R) {
    if (L >= R) {
        return;
    }
    int index = L + (int)((R - L) * Math.random()); //生成L~R之間的隨機(jī)值
     //為了好理解，我將這個隨機(jī)值放到數(shù)組開頭。也可以不交換，只需改partition即可
    swap(array, L, index);
    
    int p = partition(array, L, R); //調(diào)用挖坑法
    quick2(array, L, p - 1); //遞歸左半部分
    quick2(array, p + 1, R); //遞歸右半部分
}

三、三數(shù)取中法

三數(shù)取中法：原意是，隨機(jī)生成數(shù)組范圍內(nèi)的三個數(shù)，然后取三者的中間值作為基準(zhǔn)值。但是在后序變化中，就沒有隨機(jī)生成，而是直接以數(shù)組的第一個數(shù)、最后一個數(shù)和中間數(shù)，這三個位置的數(shù)，取中間值，作為基準(zhǔn)值。也是搭配著挖坑法來使用的，與隨機(jī)取值法一樣，都是起到優(yōu)化的作用。

public void quick3(int[] array, int L, int R) {
    if (L >= R) {
        return;
    }
    threeNumberMid(array, L, R); //三數(shù)取中，并將中間值，放到數(shù)組最前面
    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過后，這三個數(shù)就是一個升序
    //然后將中間值，放到數(shù)組的最前面
    swap(array, L, mid);
}

四、荷蘭國旗問題優(yōu)化

荷蘭國旗問題所帶來的優(yōu)化，有明顯是優(yōu)于挖坑法的。在以后的使用中，可能這種優(yōu)化可能會多一點(diǎn)。

至于為什么叫荷蘭國旗問題所帶來的優(yōu)化。大家去百度查一下這關(guān)鍵字即可，我們這里就不多說了。

原意是：給定一個數(shù)組，將這個數(shù)組，以某一個基準(zhǔn)值，整體分為三個區(qū)域（大于區(qū)，小于區(qū)、等于區(qū)）。然后再去遞歸小于區(qū)和大于區(qū)的范圍。這就是荷蘭國旗問題所帶來的優(yōu)化思想，不同于挖坑法的是，這種優(yōu)化，會將所有等于基準(zhǔn)值的數(shù)，都聚集在中間，這樣的話，分別去遞歸左右兩邊的子數(shù)組時，范圍上就有一定的縮小。

具體步驟：

• 有三個變量（less，more，index）。分別表示小于區(qū)的右邊界、大于區(qū)的左邊界，index則表示遍歷當(dāng)前數(shù)組的下標(biāo)值。less左邊都是小于基準(zhǔn)值的，more右邊都是大于基準(zhǔn)值的。如下圖：暫時先不看more范圍內(nèi)的50，等會說明。

• index從左開始遍歷，每遍歷一個數(shù)，進(jìn)行判斷，小于基準(zhǔn)值，就劃分到less區(qū)域；大于基準(zhǔn)值就劃分到more區(qū)域；等于的話，不交換，index往后走就行。
• 循環(huán)上一走即可，直到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] > 基準(zhǔn)值) {
            
        } else if (array[index] < 基準(zhǔn)值) {
            
        } else { //等于基準(zhǔn)值時，index后移即可
            index++;
        }
    }
    
    //返回等于區(qū)的開始和結(jié)束下標(biāo)即可。
}

以上就是荷蘭國旗問題的偽代碼，是不是感覺很簡單？？？返回的是一個數(shù)組，這個數(shù)組只有兩個元素，第一個元素就是等于區(qū)的開始下標(biāo)，第二個元素就是等于區(qū)的結(jié)束下標(biāo)。

具體的思想我們講了，但是還是會遇到一個問題，那就是基準(zhǔn)值的選擇。我們只需套用前面講過的隨機(jī)取值法或者三數(shù)取中法即可。

我們前面將隨機(jī)取值法的時候，是將隨機(jī)抽取的基準(zhǔn)值，放到數(shù)組的第一個元素的位置，然后再去調(diào)用partition方法，進(jìn)行挖坑法的。這里我們就換一下，將隨機(jī)抽取的基準(zhǔn)值，放到數(shù)組的末尾。這也就是在上一張圖中，為什么more范圍內(nèi)的50是紅色的原因。因為它就是基準(zhǔn)值，只是暫時先放到了數(shù)組的最后而已。（當(dāng)然，也可以像挖坑法一樣，放到數(shù)組的第一個元素位置，一樣的道理，只是partition方法稍微修改一下初始值即可）。

既然我們將基準(zhǔn)值放到了數(shù)組的末尾，那么在while循環(huán)結(jié)束后，也就是index遍歷完之后，也需要將最后這個基準(zhǔn)值放回到等于區(qū)的范圍。而此時數(shù)組狀態(tài)是這樣的：L……less是小于區(qū)，less+1 …… more - 1是等于區(qū)，more …… R是大于區(qū)。

我們將最后這個基準(zhǔn)值放到等于區(qū)的末尾即可，也就是調(diào)用swap(array, more, R)。R是基準(zhǔn)值的位置，more是大于區(qū)的開始位置。

所以完整的partition代碼如下：

//R位置就是基準(zhǔn)值
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; //數(shù)組最前面開始為less
    int more = R; //數(shù)組末尾，包括了最后的基準(zhǔn)值
    int index = L; //遍歷數(shù)組
    while (index < more) {
        if(array[index] > array[R]) { //大于區(qū)
            swap(array, index, --more);
        } else if (array[index] < array[R]) { //小于區(qū)
            swap(array, index++, ++less);
        } else { //等于區(qū)
            index++;
        }
    }
    swap(array, more, R); //將最后的基準(zhǔn)值放回等于區(qū)
    //此時的范圍：L …… less 是小于區(qū)。less+1 ……more 是等于區(qū)。more + 1 …… R是大于區(qū)
    return new int[] {less+1, more};
}

特別值得注意的是，循環(huán)里第一個if語句，大于基準(zhǔn)值的時候，從與數(shù)組后面的元素交換。但是從數(shù)組后面交換過來的數(shù)據(jù)，并不知道大小情況，所以此時的index還不能移動，需再次判斷交換過來的數(shù)據(jù)才行。其他的注意地方就是less和more的變化，留意一下是前置++-- 。

主方法的調(diào)用：

public void quick(int[] array, int L, int R) {
    if (L >= R) {
        return;
    }
    int i = L + (int)((R - L) * Math.random()); //隨機(jī)值
    swap(array, i, R); //放到數(shù)組的最后
    int[] mid = partition(array, L, R); //返回的是等于區(qū)的范圍
    quick(array, L, mid[0] - 1); //左半部分
    quick(array, mid[0] + 1, R); //右半部分
}

五、非遞歸版本

講完了快速排序的挖坑法和荷蘭國旗問題的優(yōu)化，剩下的就很簡單了。非遞歸的話，就是申請一個棧，棧里壓入的是待排序數(shù)組的開始下標(biāo)和結(jié)束下標(biāo)。也就是說，這個入棧時，需要同時壓入兩個下標(biāo)值的。彈出的時候，也是同時彈出兩個下標(biāo)值的。

唯一的問題就在于，我該在什么時候進(jìn)行壓入？

• 當(dāng)此時的右半部分只有一個數(shù)據(jù)，或者沒有數(shù)據(jù)的時候，此時右半部分就不需要再入棧了。

• 同理，當(dāng)此時左半部分只有一個數(shù)據(jù)，或者沒有數(shù)據(jù)的時候，就不需要再入棧了。

以上兩點(diǎn)，推導(dǎo)出，當(dāng)mid[1] + 1 >= R 時，不需要再壓入右半部分；當(dāng)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); //調(diào)用荷蘭國旗問題優(yōu)化的代碼
        
        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);
        }
    }
}

非遞歸代碼，就是需要注意，先壓入數(shù)組的左邊界L，再壓入右邊界R，則彈出棧的時候，是先彈出R的值。這里需要注意，不要反了。

快速排序的時間復(fù)雜度O(NlogN)，空間復(fù)雜度O(logN)，沒有穩(wěn)定性。快速排序的時間復(fù)雜度，取決于基準(zhǔn)值的選擇，基準(zhǔn)值選在所有數(shù)據(jù)的中間，將左右部分的子數(shù)組平分，就是最優(yōu)的，能達(dá)到O(NlogN)，如果選在所有數(shù)據(jù)的最小值或最大值，則時間復(fù)雜度就會退化為O(N^2)。

還有一個優(yōu)化就是，當(dāng)待排序數(shù)組的數(shù)據(jù)個數(shù)到達(dá)一定的范圍時，可直接使用插入排序，會比快速排序快一點(diǎn)點(diǎn)的。

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

我們下期再見吧?。?！

到此這篇關(guān)于Java深入淺出理解快速排序以及優(yōu)化方式的文章就介紹到這了,更多相關(guān)Java 快速排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論