概念

??????快速排序的基本思想是分治法，選取一個(gè)“基準(zhǔn)數(shù)”作為比較參照，經(jīng)過(guò)排序運(yùn)算傍药，將數(shù)據(jù)分為兩個(gè)規(guī)模更小的數(shù)據(jù)源，其中一個(gè)所有的數(shù)據(jù)都比另一部分的小默穴，然后遞歸進(jìn)行操作從而使數(shù)據(jù)達(dá)到有序的狀態(tài)怔檩。

分治法的基本思想是：將原問(wèn)題分解為若干個(gè)規(guī)模更小但結(jié)構(gòu)與原問(wèn)題相似的子問(wèn)題。遞歸地解這些子問(wèn)題蓄诽，然后將這些子問(wèn)題的解組合為原問(wèn)題的解薛训。

快速排序的時(shí)間復(fù)雜度在最壞情況下是O(N²)，平均的時(shí)間復(fù)雜度是O(N*log^N)仑氛∫野＃快速排序是不穩(wěn)定的算法。

算法穩(wěn)定性：假設(shè)在數(shù)列中存在 a[i] = a[j]锯岖，若在排序之前介袜，a[i] 在a[j] 前面；并且排序之后出吹，a[i] 仍然在a[j] 前面遇伞。則這個(gè)排序算法是穩(wěn)定的！

實(shí)現(xiàn)方式

??????記錄一下三種簡(jiǎn)單的實(shí)現(xiàn)方式捶牢，總結(jié)以代碼+日志的方式展示鸠珠，通過(guò)日志可以清晰的展示出每輪每次的數(shù)據(jù)操作巍耗。前提假設(shè)最終的目標(biāo)排序方式都是升序，可以為了清晰展示出每次具體操作了哪些數(shù)據(jù)渐排，日志[]中括號(hào)內(nèi)展示的為數(shù)組下標(biāo)炬太，()小括號(hào)內(nèi)展示的為本輪的數(shù)據(jù)源，""雙引號(hào)內(nèi)展示的為本次需要交換的兩個(gè)值驯耻，''單引號(hào)內(nèi)展示的為pre(前后指針)的值亲族。

左右指針?lè)?/h3>

• 選取基準(zhǔn)值，開(kāi)始本輪循環(huán)可缚；
• 從數(shù)組右側(cè)開(kāi)始遞減比較霎迫，發(fā)現(xiàn)有值小于基準(zhǔn)值，停下記錄該下標(biāo)城看；
• 從數(shù)組左側(cè)開(kāi)始遞增比較女气，發(fā)現(xiàn)有值大于基準(zhǔn)值，停下記錄該下標(biāo)测柠；
• 將兩個(gè)下標(biāo)的值進(jìn)行交換炼鞠；
• 接著循環(huán)重復(fù)第2~4步，直到左右兩指針相遇轰胁，表示這一輪的內(nèi)循環(huán)比較結(jié)束谒主；
• 此時(shí)左、右指針指向相同的值赃阀，將左霎肯、右指針指向的值與基準(zhǔn)值交換（基準(zhǔn)值歸位），就完成了本輪的排序榛斯；
• 每輪排序完成后观游，基準(zhǔn)值左邊的都是小于它的，而右邊都是大于等于它的驮俗，接著以基準(zhǔn)值為分割點(diǎn)懂缕，將兩個(gè)子集數(shù)據(jù)源從第1步進(jìn)行遞歸操作；

??????通俗點(diǎn)說(shuō)王凑，就是一個(gè)指針從右側(cè)依次遞減搪柑，一個(gè)指針從左側(cè)依次遞增，當(dāng)發(fā)現(xiàn)符合條件的情況時(shí)索烹，交換兩個(gè)指針指向的值工碾，然后以基準(zhǔn)值為分割點(diǎn)，將本次數(shù)據(jù)源分為兩個(gè)小的數(shù)組百姓，依次遞歸循環(huán)該操作渊额。

??????這里需要注意的就是內(nèi)部循環(huán)初始先從右側(cè)開(kāi)始還是左側(cè)開(kāi)始，這里先分析下本例當(dāng)中，要求升序排列端圈，從左側(cè)（最終肯定是小于基準(zhǔn)值的值）取默認(rèn)基準(zhǔn)值焦读，當(dāng)內(nèi)部循環(huán)優(yōu)先從右側(cè)開(kāi)始時(shí)，每次循環(huán)完舱权，右側(cè)指針指向的永遠(yuǎn)是小于基準(zhǔn)值的值（排除已經(jīng)是升序的情況），這時(shí)假如本次沒(méi)有交換仑嗅，在循環(huán)外右側(cè)指針（等于左側(cè)指針）就可以與基準(zhǔn)值的進(jìn)行交換宴倍，最終基準(zhǔn)值歸位，小于基準(zhǔn)值的數(shù)都在一側(cè)仓技。
??????相應(yīng)的鸵贬，我們也可以在內(nèi)循環(huán)時(shí)優(yōu)先從左側(cè)判斷，這時(shí)在選基準(zhǔn)值時(shí)就選擇右側(cè)的脖捻；或者嘗試下降序時(shí)的初始方式阔逼，這里就不贅述了……

public static void quickSort(int left, int right) {
    if (left >= right) {
        return;
    }
        
    int l = left;
    int r = right;
    int target = arrs[l];
        
    while (l < r) {
        while (arrs[r] >= target && l < r) {
            r--;
        }
        while (arrs[l] <= target && l < r) {
            l++;
        }
            
        if (l < r) {
            swap(arrs[l], arrs[r]);
        }
    }
        
    if (l != left) {
        swap(arrs[l], arrs[left]):
    }
        
    quickSort(left, l - 1);
    quickSort(l + 1, right);
}

隨機(jī)初始數(shù)組： [29, 13, 86, 2, 55, 7, 22, 33, ] 
################

第1輪，基準(zhǔn)值是29：
交換[2]和[6]位置的值
交換前的數(shù)據(jù)： [(29, 13, "86", 2, 55, 7, "22", 33), ] 
交換后的數(shù)據(jù)： [(29, 13, "22", 2, 55, 7, "86", 33), ] 
交換[4]和[5]位置的值
交換前的數(shù)據(jù)： [(29, 13, 22, 2, "55", "7", 86, 33), ] 
交換后的數(shù)據(jù)： [(29, 13, 22, 2, "7", "55", 86, 33), ] 
內(nèi)循環(huán)結(jié)束地沮，當(dāng)前l(fā)=r=[4]嗜浮，與基準(zhǔn)值(下標(biāo)[0])值交換
交換前的數(shù)據(jù)： [("29", 13, 22, 2, "7", 55, 86, 33), ] 
交換后的數(shù)據(jù)： [("7", 13, 22, 2, "29", 55, 86, 33), ] 
第1輪結(jié)束

第2輪，基準(zhǔn)值是7：
交換[1]和[3]位置的值
交換前的數(shù)據(jù)： [(7, "13", 22, "2"), 29, 55, 86, 33, ] 
交換后的數(shù)據(jù)： [(7, "2", 22, "13"), 29, 55, 86, 33, ] 
內(nèi)循環(huán)結(jié)束摩疑，當(dāng)前l(fā)=r=[1]危融，與基準(zhǔn)值(下標(biāo)[0])值交換
交換前的數(shù)據(jù)： [("7", "2", 22, 13), 29, 55, 86, 33, ] 
交換后的數(shù)據(jù)： [("2", "7", 22, 13), 29, 55, 86, 33, ] 
第2輪結(jié)束

第3輪，基準(zhǔn)值是22：
循環(huán)結(jié)束雷袋，當(dāng)前l(fā)=r=[3]吉殃，與基準(zhǔn)值(下標(biāo)[2])值交換
交換前的數(shù)據(jù)： [2, 7, ("22", "13"), 29, 55, 86, 33, ] 
交換后的數(shù)據(jù)： [2, 7, ("13", "22"), 29, 55, 86, 33, ] 
第3輪結(jié)束

第4輪，基準(zhǔn)值是55：
交換[6]和[7]位置的值
交換前的數(shù)據(jù)： [2, 7, 13, 22, 29, (55, "86", "33"), ] 
交換后的數(shù)據(jù)： [2, 7, 13, 22, 29, (55, "33", "86"), ] 
內(nèi)循環(huán)結(jié)束楷怒，當(dāng)前l(fā)=r=[6]蛋勺，與基準(zhǔn)值(下標(biāo)[5])值交換
交換前的數(shù)據(jù)： [2, 7, 13, 22, 29, ("55", "33", 86), ] 
交換后的數(shù)據(jù)： [2, 7, 13, 22, 29, ("33", "55", 86), ] 
第4輪結(jié)束

################
排序最終數(shù)組： [2, 7, 13, 22, 29, 33, 55, 86, ] 

填坑法

• 選取基準(zhǔn)值，該下標(biāo)即為第一個(gè)坑位A鸠删，開(kāi)始本輪循環(huán)抱完；
• 從數(shù)組右側(cè)開(kāi)始遞減比較，當(dāng)發(fā)現(xiàn)有值小于基準(zhǔn)值時(shí)冶共，將當(dāng)前值填到坑位A中乾蛤，同時(shí)當(dāng)前下標(biāo)替換為坑位B（注意：初始基準(zhǔn)值被覆蓋掉了，本輪操作最后捅僵，需要將該值填到坑位中）家卖；
• 從數(shù)組左側(cè)開(kāi)始遞增比較，當(dāng)發(fā)現(xiàn)有值大于基準(zhǔn)值庙楚，將值填到坑位B中上荡，同時(shí)當(dāng)前下標(biāo)替換為坑位A；
• 不停的重復(fù)第2~3步的操作，直到左右兩指針相遇酪捡，表示這一輪的內(nèi)循環(huán)比較結(jié)束叁征；
• 將基準(zhǔn)值填到左右指針指向的坑位中，就完成了本輪的排序逛薇；
• 以基準(zhǔn)值為分割點(diǎn)捺疼，將本次數(shù)據(jù)源分為兩個(gè)小的數(shù)組，依次從第1步遞歸循環(huán)操作永罚；

public static void quickSort(int left, int right) {
    if (left >= right) {
        return;
    }
        
    int l = left;
    int r = right;
    int target = arrs[l];
        
    while (l < r) {
        while (arrs[r] >= target && l < r) {
            r--;
        }
        if (l < r) {
            arrs[l] = arrs[r];
        }
            
        while (arrs[l] <= target && l < r) {
            l++;
        }
        if (l < r) {        
            arrs[r] = arrs[l];
        }
    }
    arrs[l] = target;
    
    quickSort(left, l - 1);
    quickSort(l + 1, right);
}

隨機(jī)初始數(shù)組： [14, 18, 1, 28, 30, 11, 78, 55, ] 
################

第1輪啤呼，基準(zhǔn)值是14，當(dāng)前坑位[0]：
交換前的數(shù)據(jù)： [("14", 18, 1, 28, 30, "11", 78, 55), ] 
交換后的數(shù)據(jù)： [("11", 18, 1, 28, 30, "11", 78, 55), ] 當(dāng)前坑位[5]呢袱，值是11
交換前的數(shù)據(jù)： [(11, "18", 1, 28, 30, "11", 78, 55), ] 
交換后的數(shù)據(jù)： [(11, "18", 1, 28, 30, "18", 78, 55), ] 當(dāng)前坑位[1]官扣，值是18
交換前的數(shù)據(jù)： [(11, "18", "1", 28, 30, 18, 78, 55), ] 
交換后的數(shù)據(jù)： [(11, "1", "1", 28, 30, 18, 78, 55), ] 當(dāng)前坑位[2]，值是1
內(nèi)循環(huán)結(jié)束羞福，準(zhǔn)備將基準(zhǔn)值補(bǔ)上最后一個(gè)坑位 [(11, 1, "1", 28, 30, 18, 78, 55), ] 
交換后的數(shù)據(jù)： [(11, 1, "14", 28, 30, 18, 78, 55), ] 
第1輪結(jié)束

第2輪惕蹄，基準(zhǔn)值是11，當(dāng)前坑位[0]：
交換前的數(shù)據(jù)： [("11", "1"), 14, 28, 30, 18, 78, 55, ] 
交換后的數(shù)據(jù)： [("1", "1"), 14, 28, 30, 18, 78, 55, ] 當(dāng)前坑位[1]治专，值是1
內(nèi)循環(huán)結(jié)束卖陵，準(zhǔn)備將基準(zhǔn)值補(bǔ)上最后一個(gè)坑位 [(1, "1"), 14, 28, 30, 18, 78, 55, ] 
交換后的數(shù)據(jù)： [(1, "11"), 14, 28, 30, 18, 78, 55, ] 
第2輪結(jié)束

第3輪，基準(zhǔn)值是28看靠，當(dāng)前坑位[3]：
交換前的數(shù)據(jù)： [1, 11, 14, ("28", 30, "18", 78, 55), ] 
交換后的數(shù)據(jù)： [1, 11, 14, ("18", 30, "18", 78, 55), ] 當(dāng)前坑位[5]赶促，值是18
交換前的數(shù)據(jù)： [1, 11, 14, (18, "30", "18", 78, 55), ] 
交換后的數(shù)據(jù)： [1, 11, 14, (18, "30", "30", 78, 55), ] 當(dāng)前坑位[4]，值是30
內(nèi)循環(huán)結(jié)束挟炬，準(zhǔn)備將基準(zhǔn)值補(bǔ)上最后一個(gè)坑位 [1, 11, 14, (18, "30", 30, 78, 55), ] 
交換后的數(shù)據(jù)： [1, 11, 14, (18, "28", 30, 78, 55), ] 
第3輪結(jié)束

第4輪鸥滨，基準(zhǔn)值是30，當(dāng)前坑位[5]：
內(nèi)循環(huán)結(jié)束谤祖，準(zhǔn)備將基準(zhǔn)值補(bǔ)上最后一個(gè)坑位 [1, 11, 14, 18, 28, ("30", 78, 55), ] 
交換后的數(shù)據(jù)： [1, 11, 14, 18, 28, ("30", 78, 55), ] 
第4輪結(jié)束

第5輪婿滓，基準(zhǔn)值是78，當(dāng)前坑位[6]：
交換前的數(shù)據(jù)： [1, 11, 14, 18, 28, 30, ("78", "55"), ] 
交換后的數(shù)據(jù)： [1, 11, 14, 18, 28, 30, ("55", "55"), ] 當(dāng)前坑位[7]粥喜，值是55
內(nèi)循環(huán)結(jié)束凸主，準(zhǔn)備將基準(zhǔn)值補(bǔ)上最后一個(gè)坑位 [1, 11, 14, 18, 28, 30, (55, "55"), ] 
交換后的數(shù)據(jù)： [1, 11, 14, 18, 28, 30, (55, "78"), ] 
第5輪結(jié)束
################
排序最終數(shù)組： [1, 11, 14, 18, 28, 30, 55, 78, ] 

前后指針?lè)?/h3>

• 選取基準(zhǔn)值，定義兩個(gè)指針额湘，cur 表示當(dāng)前指針指向卿吐，pre 默認(rèn)表示cur 指針的前一位；
• cur 和 pre 指針依次++ 進(jìn)行遞增比較锋华，當(dāng)cur 發(fā)現(xiàn)大于基準(zhǔn)值時(shí)嗡官，pre 暫停遞增（即[pre+1] 指向了一個(gè)大于基準(zhǔn)值的值）；
• cur 接著++ 進(jìn)行遞增比較毯焕，當(dāng)發(fā)現(xiàn)比基準(zhǔn)值小時(shí)衍腥，對(duì)數(shù)組[pre+1] 和 數(shù)組[cur] 的值進(jìn)行交換；
• 不停的重復(fù)第2~3步操作，直到一輪循環(huán)結(jié)束（即cur 從當(dāng)前數(shù)據(jù)源從左移到了右）婆咸；
• 內(nèi)循環(huán)結(jié)束后竹捉，將數(shù)組[pre+1] 的值與基準(zhǔn)值進(jìn)行交換；
• 以基準(zhǔn)值為分割點(diǎn)尚骄，將本次數(shù)據(jù)源分為兩個(gè)小的數(shù)組块差，依次從第1步遞歸循環(huán)操作；

public static void quickSort(int left, int right) {
    if (left >= right) {
        return;
    }
        
    int cur = left;
    int pre = cur - 1;
    int target = arrs[right];
        
    while (cur < right) {
        while (arrs[cur] < target && ++pre != cur) {
            swap(arrs[cur], arrs[pre];
        }
        cur++;
    }
        
    swap(arrs[++pre], arrs[right]);
        
    quickSort(left, pre -1);
    quickSort(pre + 1, right);
}

隨機(jī)初始數(shù)組： [86, 59, 63, 53, 68, 99, 58, 1, ] 
################

第1輪乖仇，基準(zhǔn)值是1憾儒，'pre'：[-1]，"cur"：[0]：
"cur"指針++了： [(86, "59", 63, 53, 68, 99, 58, 1), ] 乃沙，'pre'：[-1], "cur"：[1]
"cur"指針++了： [(86, 59, "63", 53, 68, 99, 58, 1), ] ，'pre'：[-1], "cur"：[2]
"cur"指針++了： [(86, 59, 63, "53", 68, 99, 58, 1), ] 诗舰，'pre'：[-1], "cur"：[3]
"cur"指針++了： [(86, 59, 63, 53, "68", 99, 58, 1), ] 警儒，'pre'：[-1], "cur"：[4]
"cur"指針++了： [(86, 59, 63, 53, 68, "99", 58, 1), ] ，'pre'：[-1], "cur"：[5]
"cur"指針++了： [(86, 59, 63, 53, 68, 99, "58", 1), ] 眶根，'pre'：[-1], "cur"：[6]
"cur"指針++了： [(86, 59, 63, 53, 68, 99, 58, "1"), ] 蜀铲，'pre'：[-1], "cur"：[7]
內(nèi)循環(huán)結(jié)束，準(zhǔn)備將'++pre'(大于基準(zhǔn)值的值)與基準(zhǔn)值交換： [("86", 59, 63, 53, 68, 99, 58, "1"), ] 
交換后的數(shù)據(jù)： [("1", 59, 63, 53, 68, 99, 58, "86"), ] 
第1輪結(jié)束

第2輪属百，基準(zhǔn)值是86记劝，'pre'：[0]，"cur"：[1]：
"cur"指針++了： [1, ('59', "63", 53, 68, 99, 58, 86), ] 族扰，'pre'：[1], "cur"：[2]
"cur"指針++了： [1, (59, '63', "53", 68, 99, 58, 86), ] 厌丑，'pre'：[2], "cur"：[3]
"cur"指針++了： [1, (59, 63, '53', "68", 99, 58, 86), ] ，'pre'：[3], "cur"：[4]
"cur"指針++了： [1, (59, 63, 53, '68', "99", 58, 86), ] 渔呵，'pre'：[4], "cur"：[5]
"cur"指針++了： [1, (59, 63, 53, '68', 99, "58", 86), ] 怒竿，'pre'：[4], "cur"：[6]
交換前的數(shù)據(jù)： [1, (59, 63, 53, 68, "99", "58", 86), ] 
交換后的數(shù)據(jù)： [1, (59, 63, 53, 68, "58", "99", 86), ] 
"cur"指針++了： [1, (59, 63, 53, 68, '58', 99, "86"), ] ，'pre'：[5], "cur"：[7]
內(nèi)循環(huán)結(jié)束扩氢，準(zhǔn)備將'++pre'(大于基準(zhǔn)值的值)與基準(zhǔn)值交換： [1, (59, 63, 53, 68, 58, "99", "86"), ] 
交換后的數(shù)據(jù)： [1, (59, 63, 53, 68, 58, "86", "99"), ] 
第2輪結(jié)束

第3輪耕驰，基準(zhǔn)值是58，'pre'：[0]录豺，"cur"：[1]：
"cur"指針++了： ['1', (59, "63", 53, 68, 58), 86, 99, ] 朦肘，'pre'：[0], "cur"：[2]
"cur"指針++了： ['1', (59, 63, "53", 68, 58), 86, 99, ] ，'pre'：[0], "cur"：[3]
交換前的數(shù)據(jù)： [1, ("59", 63, "53", 68, 58), 86, 99, ] 
交換后的數(shù)據(jù)： [1, ("53", 63, "59", 68, 58), 86, 99, ] 
"cur"指針++了： [1, ('53', 63, 59, "68", 58), 86, 99, ] 双饥，'pre'：[1], "cur"：[4]
"cur"指針++了： [1, ('53', 63, 59, 68, "58"), 86, 99, ] 媒抠，'pre'：[1], "cur"：[5]
內(nèi)循環(huán)結(jié)束，準(zhǔn)備將'++pre'(大于基準(zhǔn)值的值)與基準(zhǔn)值交換： [1, (53, "63", 59, 68, "58"), 86, 99, ] 
交換后的數(shù)據(jù)： [1, (53, "58", 59, 68, "63"), 86, 99, ] 
第3輪結(jié)束

第4輪兢哭，基準(zhǔn)值是63领舰，'pre'：[2]，"cur"：[3]：
"cur"指針++了： [1, 53, 58, ('59', "68", 63), 86, 99, ] ，'pre'：[3], "cur"：[4]
"cur"指針++了： [1, 53, 58, ('59', 68, "63"), 86, 99, ] 冲秽，'pre'：[3], "cur"：[5]
內(nèi)循環(huán)結(jié)束舍咖，準(zhǔn)備將'++pre'(大于基準(zhǔn)值的值)與基準(zhǔn)值交換： [1, 53, 58, (59, "68", "63"), 86, 99, ] 
交換后的數(shù)據(jù)： [1, 53, 58, (59, "63", "68"), 86, 99, ] 
第4輪結(jié)束
################
排序最終數(shù)組： [1, 53, 58, 59, 63, 68, 86, 99, ]