典排序?qū)崿F(xiàn)與工程選型)
排序算法是數(shù)據(jù)結(jié)構(gòu)課里那塊最“硬”的骨頭也是各大廠(chǎng)筆試面試中出場(chǎng)率極高的?？?。這次梳理的是Java視角下的七大排序算法也就是直接插入排序、希爾排序、冒泡排序、快速排序、簡(jiǎn)單選擇排序、堆排序和歸并排序。無(wú)論你是正在準(zhǔn)備校招的應(yīng)屆生還是在公司里做業(yè)務(wù)開(kāi)發(fā)時(shí)偶爾需要手寫(xiě)一段排序邏輯或者純粹想把這些經(jīng)典算法吃透這篇內(nèi)容都能給你一個(gè)完整、可直接參考的脈絡(luò)。我會(huì)把每種算法的核心思想、Java實(shí)現(xiàn)、復(fù)雜度推導(dǎo)以及只有在真正寫(xiě)代碼時(shí)才會(huì)遇到的那些坑全都攤開(kāi)來(lái)講。這篇內(nèi)容不是單純的代碼堆砌我會(huì)按照“家族”把它們分組插入排序家族、交換排序家族、選擇排序家族再加上歸并排序這個(gè)“分治王者”這樣分類(lèi)的好處是你能從設(shè)計(jì)思路上去理解而不是死記硬背代碼。每一類(lèi)我都會(huì)給出完整的Java代碼并且標(biāo)注清楚哪些地方容易寫(xiě)錯(cuò)哪些細(xì)節(jié)是面試官特別喜歡追問(wèn)的。我還會(huì)分享一些在實(shí)際工程項(xiàng)目里篩選排序方案的經(jīng)驗(yàn)比如面對(duì)幾萬(wàn)條數(shù)據(jù)時(shí)該無(wú)腦選哪種、什么時(shí)候別手寫(xiě)排序而應(yīng)該直接調(diào)JDK自帶的方法。1. 七大排序全景透視復(fù)雜度與場(chǎng)景選型先把七種算法放到一張表里看全貌。這張表是你復(fù)習(xí)和面試前必須刻在腦子里的東西它決定了你在不同場(chǎng)景下第一時(shí)間該掏出哪種排序。排序算法平均時(shí)間復(fù)雜度最壞時(shí)間復(fù)雜度最好時(shí)間復(fù)雜度空間復(fù)雜度穩(wěn)定性直接插入排序O(n2)O(n2)O(n)O(1)穩(wěn)定希爾排序O(n^1.3~1.5)O(n2)O(n)O(1)不穩(wěn)定冒泡排序O(n2)O(n2)O(n)O(1)穩(wěn)定快速排序O(nlogn)O(n2)O(nlogn)O(logn)~O(n)不穩(wěn)定簡(jiǎn)單選擇排序O(n2)O(n2)O(n2)O(1)不穩(wěn)定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不穩(wěn)定歸并排序O(nlogn)O(nlogn)O(nlogn)O(n)穩(wěn)定讀這張表有個(gè)規(guī)律希望你能記下來(lái)大多數(shù)“不穩(wěn)定”的排序算法問(wèn)題都出在“跳躍式交換元素”這個(gè)動(dòng)作上。比如希爾排序是跳著組內(nèi)比較交換快速排序是基準(zhǔn)值左右跳躍式交換簡(jiǎn)單選擇排序是每輪把最小的元素直接甩到前面堆排序更是隔著整個(gè)堆在交換。反而是那些只在相鄰元素之間“小步挪動(dòng)”的算法——插入排序、冒泡排序、歸并排序——天然就能保證穩(wěn)定性。穩(wěn)定性這個(gè)詞很多初學(xué)者覺(jué)得無(wú)所謂但我舉個(gè)例子你就明白了。假設(shè)你要給一個(gè)班級(jí)的學(xué)生表排序先按年齡排好序再按姓名排序如果排序算法不穩(wěn)定第二次按姓名排序時(shí)年齡相同的學(xué)生順序可能就亂了你前面按年齡排的順序等于白做了。實(shí)際系統(tǒng)里這種情況太常見(jiàn)了先按主鍵排序再按副鍵排序穩(wěn)定的排序算法能保證兩次排序結(jié)果可疊加。選型的邏輯我一般看三個(gè)指標(biāo)數(shù)據(jù)量大小、數(shù)據(jù)初始有序程度、是否要求穩(wěn)定。數(shù)據(jù)量很小比如50個(gè)以?xún)?nèi)直接插入排序幾乎無(wú)敵因?yàn)槌?shù)極小沒(méi)有額外空間消耗。數(shù)據(jù)量中等幾千到幾萬(wàn)快速排序是最優(yōu)選平均性能最強(qiáng)但要注意最壞退化問(wèn)題。數(shù)據(jù)量超大百萬(wàn)級(jí)以上且要求最壞時(shí)間復(fù)雜度可控歸并排序或堆排序更穩(wěn)。要求穩(wěn)定且數(shù)據(jù)量不小歸并排序是你的唯一選擇Java的Collections.sort底層也是這個(gè)思路。幾乎有序的數(shù)據(jù)插入排序的最好情況O(n)優(yōu)勢(shì)就體現(xiàn)出來(lái)了很多商用的混合排序會(huì)用它來(lái)收尾。2. 插入排序家族直接插入與希爾2.1 直接插入排序像整理手牌一樣簡(jiǎn)單如果你打撲克牌時(shí)習(xí)慣把摸到的新牌插入到手里已經(jīng)排好序的牌堆中那你已經(jīng)懂了直接插入排序的核心思想。把數(shù)組看成兩部分左邊是已排序區(qū)右邊是待排序區(qū)每次從待排序區(qū)拿出第一個(gè)數(shù)把它往左插到合適位置。Java實(shí)現(xiàn)如下public static void insertSort(int[] arr) { if (arr null || arr.length 2) return; // 默認(rèn)arr[0]是已排序區(qū)從arr[1]開(kāi)始依次處理 for (int i 1; i arr.length; i) { int current arr[i]; // 待插入的數(shù) int j i - 1; // 從右往左找合適位置同時(shí)把元素向右挪動(dòng)給current騰位置 while (j 0 arr[j] current) { arr[j 1] arr[j]; j--; } arr[j 1] current; } }這段代碼里最容易出錯(cuò)的地方是最后那句arr[j 1] current;。很多初學(xué)者搞不清為什么是j1而不是j因?yàn)閣hile循環(huán)退出時(shí)有兩種情況要么j已經(jīng)小于0了說(shuō)明current應(yīng)該放在數(shù)組最前面要么arr[j]已經(jīng)不大于current了說(shuō)明current應(yīng)該插在arr[j]的后面。不管是哪種正確的位置都是索引j1。復(fù)雜度這塊最壞和平均都是O(n2)——你每次插入都要把前面一大片元素往后挪。但最好情況很討喜如果數(shù)據(jù)本來(lái)就是有序的while循環(huán)一次都不進(jìn)外層循環(huán)掃一遍就結(jié)束時(shí)間復(fù)雜度直接降到O(n)。所以它特別適合那種“基本有序”的數(shù)據(jù)。2.2 希爾排序給插入排序裝上“渦輪增壓”希爾排序是直接插入排序的改進(jìn)版思路非常聰明先讓數(shù)據(jù)整體變得“基本有序”再去做最后一次直接插入排序。怎么讓數(shù)據(jù)基本有序答案是對(duì)數(shù)組進(jìn)行分組組內(nèi)排序。關(guān)鍵點(diǎn)是分組的方式不是簡(jiǎn)單的連續(xù)分塊而是“按間隔取元素”分組。假設(shè)數(shù)組長(zhǎng)度是8間隔gap先取4那么下標(biāo)0、4一組1、5一組2、6一組3、7一組分別做插入排序。然后gap縮小為2再按新的間隔分組排序。最后gap變成1就是標(biāo)準(zhǔn)的直接插入排序了。public static void shellSort(int[] arr) { if (arr null || arr.length 2) return; int n arr.length; // 初始間隔取數(shù)組長(zhǎng)度的一半以后每輪砍半 for (int gap n / 2; gap 0; gap / 2) { // 從gap開(kāi)始逐個(gè)對(duì)“邏輯分組”做插入排序 for (int i gap; i n; i) { int current arr[i]; int j i; // 組內(nèi)做插入排序比較時(shí)跨越gap距離 while (j - gap 0 arr[j - gap] current) { arr[j] arr[j - gap]; j - gap; } arr[j] current; } } }注意這里的雙層循環(huán)變成了三層嵌套初看容易暈但你可以這樣理解i從gap掃到n-1每次處理時(shí)它都是在處理某個(gè)分組里的“下一個(gè)元素”內(nèi)層while負(fù)責(zé)在當(dāng)前分組里往前插入。這個(gè)寫(xiě)法比起先按組循環(huán)再組內(nèi)排序代碼更簡(jiǎn)潔但理解難度稍高。關(guān)于間隔序列經(jīng)典的“每次除以2”不是最優(yōu)的目前比較常用的是Sedgewick序列比如1、5、19、41、109……這種序列能達(dá)到O(n^1.3)級(jí)別的時(shí)間復(fù)雜度。我在實(shí)際項(xiàng)目里除非數(shù)據(jù)特征特別明確一般不會(huì)手寫(xiě)希爾排序但在算法題里偶爾有奇效尤其是某些對(duì)空間要求苛刻的場(chǎng)景。2.3 為什么希爾排序不穩(wěn)定希爾排序的不穩(wěn)定性是個(gè)經(jīng)典面試點(diǎn)。原因是分組排序時(shí)兩個(gè)數(shù)值相等的元素可能因?yàn)榉纸M的不同而被拆散后面某個(gè)組內(nèi)交換時(shí)讓原本靠前的那個(gè)元素跑到后面去了。舉個(gè)具體例子數(shù)組[2, 1, 2]gap1時(shí)直接插入排序沒(méi)問(wèn)題但如果gap2分組下標(biāo)0和下標(biāo)2這兩個(gè)“2”被分到同一組組內(nèi)排序時(shí)如果發(fā)生交換兩個(gè)2的相對(duì)位置就可能顛倒。這種跨越間隔的移動(dòng)是破壞穩(wěn)定性的元兇。3. 交換排序家族冒泡與快速3.1 冒泡排序教學(xué)常客工程棄兒冒泡排序的思路就是“大的往下沉小的往上浮”。每輪從頭開(kāi)始兩兩比較相鄰元素如果順序反了就交換一輪下來(lái)最大的數(shù)被“冒泡”到了最后。重復(fù)n輪就全部有序。public static void bubbleSort(int[] arr) { if (arr null || arr.length 2) return; int n arr.length; for (int i 0; i n - 1; i) { boolean swapped false; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; swapped true; } } // 如果某一輪沒(méi)有任何交換說(shuō)明已經(jīng)有序直接結(jié)束 if (!swapped) break; } }我加了一個(gè)swapped標(biāo)志位這是冒泡排序最重要的優(yōu)化——數(shù)據(jù)本來(lái)就有序時(shí)第一輪結(jié)束就能提前退出時(shí)間復(fù)雜度降到O(n)。還有一個(gè)優(yōu)化思路是記錄最后一次發(fā)生交換的位置這個(gè)位置之后的數(shù)據(jù)已經(jīng)排好了下一輪就不需要再遍歷到末尾。但說(shuō)句大實(shí)話(huà)冒泡排序在實(shí)際工程里幾乎不會(huì)被用到哪怕是幾百條數(shù)據(jù)處理直接插入排序都比它快得多因?yàn)樗龅慕粨Q次數(shù)太多了。它存在的最大意義就是當(dāng)作教學(xué)案例讓你理解最樸素的交換排序思想。3.2 快速排序最常用的“分治王者”快排的核心思想是分治隨便挑一個(gè)數(shù)當(dāng)基準(zhǔn)值pivot通過(guò)一次遍歷把數(shù)組分成兩撥比pivot小的放左邊、大的放右邊然后對(duì)左右兩撥分別遞歸做同樣的事最終整個(gè)數(shù)組有序?？焖倥判虻膶?shí)現(xiàn)版本很多寫(xiě)法差異很大我分享一個(gè)我用了很多年的經(jīng)典寫(xiě)法它叫“挖坑法”比較容易理解也不會(huì)寫(xiě)錯(cuò)public static void quickSort(int[] arr, int left, int right) { if (left right) return; // 三數(shù)取中優(yōu)化下面單獨(dú)講 int midIndex left (right - left) / 2; if (arr[left] arr[midIndex]) swap(arr, left, midIndex); if (arr[left] arr[right]) swap(arr, left, right); if (arr[midIndex] arr[right]) swap(arr, midIndex, right); swap(arr, left, midIndex); // 把基準(zhǔn)值放到最左邊 int pivot arr[left]; int i left, j right; while (i j) { // 必須先從右往左找比pivot小的 while (i j arr[j] pivot) j--; if (i j) { arr[i] arr[j]; i; } // 再?gòu)淖笸艺冶萷ivot大的 while (i j arr[i] pivot) i; if (i j) { arr[j] arr[i]; j--; } } arr[i] pivot; // i和j相遇的位置就是基準(zhǔn)值的最終位置 quickSort(arr, left, i - 1); quickSort(arr, i 1, right); } private static void swap(int[] arr, int a, int b) { int tmp arr[a]; arr[a] arr[b]; arr[b] tmp; }這個(gè)寫(xiě)法里有兩個(gè)隱藏很深的坑。第一個(gè)坑是為什么內(nèi)層循環(huán)必須先從右往左走因?yàn)槟惆鸦鶞?zhǔn)值放在了最左邊相當(dāng)于左邊“挖了個(gè)坑”你需要先從右邊找一個(gè)比基準(zhǔn)值小的數(shù)來(lái)填左邊的坑。如果先從左往右找左邊第一個(gè)元素可能就直接把坑越過(guò)了邏輯會(huì)亂。第二個(gè)坑是內(nèi)層while里的條件必須是和不能寫(xiě)成和。如果用嚴(yán)格大于或小于遇到和基準(zhǔn)值相等的元素時(shí)i和j都可能卡住不動(dòng)導(dǎo)致死循環(huán)或者無(wú)限遞歸。關(guān)于三數(shù)取中的優(yōu)化我簡(jiǎn)單解釋一下為什么需要它。快排最怕的是每次選基準(zhǔn)值都選到最大值或最小值那樣分區(qū)極不平衡遞歸深度達(dá)到n層時(shí)間復(fù)雜度退化成O(n2)。取數(shù)組左端、中間、右端三個(gè)數(shù)的中間值作為基準(zhǔn)值可以在很大程度上避免這個(gè)問(wèn)題尤其是對(duì)“已經(jīng)有序”的數(shù)組效果立竿見(jiàn)影。還有一個(gè)工程上的優(yōu)化細(xì)節(jié)當(dāng)子數(shù)組長(zhǎng)度比較小比如小于10時(shí)遞歸調(diào)用的開(kāi)銷(xiāo)占比很大很多版本的快排會(huì)切換到直接插入排序來(lái)收尾。JDK內(nèi)部實(shí)現(xiàn)的排序就是這么干的大區(qū)間用快排思路小區(qū)間用插入排序整體性能能提升不少。3.3 快排的空間復(fù)雜度與穩(wěn)定性快排的空間復(fù)雜度是O(logn)這里的空間不是指額外的數(shù)組而是遞歸調(diào)用棧的深度。理想情況下每次分區(qū)都均衡遞歸層數(shù)是logn最壞情況下每次都只拆出一個(gè)元素遞歸層數(shù)是n棧溢出風(fēng)險(xiǎn)很高。這也就是為什么面試官會(huì)追問(wèn)“快排空間復(fù)雜度是多少”很多人會(huì)答O(1)這就錯(cuò)了——遞歸本身在消耗調(diào)用?？臻g。快速排序不穩(wěn)定原因在于它的交換是“跳躍式”的——基準(zhǔn)值可能被直接換到很遠(yuǎn)的位置兩個(gè)數(shù)值相同的元素的相對(duì)順序在這個(gè)過(guò)程中可能被改變。所以如果業(yè)務(wù)上有穩(wěn)定排序要求快排不能直接上。4. 選擇排序家族簡(jiǎn)單選擇與堆排序4.1 簡(jiǎn)單選擇排序最直觀但毫無(wú)“亮點(diǎn)”簡(jiǎn)單選擇排序的思路比冒泡還直觀第一輪從0到n-1里找到最小的數(shù)放到下標(biāo)0的位置第二輪從1到n-1里找到最小的放到下標(biāo)1的位置以此類(lèi)推。public static void selectSort(int[] arr) { if (arr null || arr.length 2) return; for (int i 0; i arr.length - 1; i) { int minIndex i; for (int j i 1; j arr.length; j) { if (arr[j] arr[minIndex]) { minIndex j; } } if (minIndex ! i) { int tmp arr[i]; arr[i] arr[minIndex]; arr[minIndex] tmp; } } }這個(gè)算法的時(shí)間復(fù)雜度不管是最好、最壞還是平均都是O(n2)因?yàn)樗恳惠喍家暾麙呙枰槐槭Ｓ鄶?shù)組來(lái)找最小元素不能利用數(shù)據(jù)原本的有序性。它的交換次數(shù)很少每輪最多一次理論上比冒泡的交換成本低但比較次數(shù)一樣多實(shí)際性能并不占優(yōu)。簡(jiǎn)單選擇排序的不穩(wěn)定性值得拿出來(lái)專(zhuān)門(mén)講。考慮數(shù)組 [5, 5, 1]第一輪找到最小元素1然后把它和下標(biāo)0的5交換結(jié)果是 [1, 5, 5]。你會(huì)看到原來(lái)在前面的那個(gè)“5”被第一次交換到了數(shù)組末尾兩個(gè)5的相對(duì)順序顛倒了。這給我們的啟示是凡是“把最值直接換到目標(biāo)區(qū)”的排序都得小心穩(wěn)定性問(wèn)題。4.2 堆排序建堆、調(diào)整與樸素“堆”的誤區(qū)堆排序的核心是“完全二叉樹(shù)”和“大頂堆”。升序排序用大頂堆堆頂元素永遠(yuǎn)是整個(gè)堆的最大值每次把堆頂和當(dāng)前未排序區(qū)域的最后一個(gè)元素交換堆頂?shù)淖畲笾稻汀皾L”到數(shù)組末尾去了然后重新調(diào)整堆結(jié)構(gòu)讓新的堆頂繼續(xù)成為剩余元素里的最大值。堆排序的兩個(gè)關(guān)鍵步驟簡(jiǎn)稱(chēng)為“建堆”和“調(diào)整”。建堆的意思是從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始從下往上做堆化heapify調(diào)整的意思是把堆頂和末尾交換后從堆頂開(kāi)始向下調(diào)整恢復(fù)大頂堆的性質(zhì)。public static void heapSort(int[] arr) { if (arr null || arr.length 2) return; int n arr.length; // 建堆從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始向上調(diào)整 for (int i n / 2 - 1; i 0; i--) { heapify(arr, n, i); } // 逐個(gè)把堆頂最大元素放到末尾 for (int i n - 1; i 0; i--) { swap(arr, 0, i); heapify(arr, i, 0); } } private static void heapify(int[] arr, int size, int root) { int largest root; int left 2 * root 1; int right 2 * root 2; if (left size arr[left] arr[largest]) largest left; if (right size arr[right] arr[largest]) largest right; if (largest ! root) { swap(arr, largest, root); heapify(arr, size, largest); // 遞歸調(diào)整被換下去的子樹(shù) } }很多初學(xué)者會(huì)問(wèn)為什么建堆的循環(huán)是從n/2 - 1開(kāi)始而不是從n-1開(kāi)始因?yàn)橥耆鏄?shù)里下標(biāo)n/2到n-1全部是葉子節(jié)點(diǎn)葉子節(jié)點(diǎn)沒(méi)有孩子本身就已經(jīng)滿(mǎn)足堆的性質(zhì)不需要調(diào)整。從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始倒序遍歷每個(gè)節(jié)點(diǎn)最多和它的子樹(shù)做一次交換時(shí)間復(fù)雜度是O(n)這里很多人有誤解以為建堆要O(nlogn)實(shí)際上這樣做是“每個(gè)節(jié)點(diǎn)調(diào)整一次”整體是O(n)。堆排序的特點(diǎn)是時(shí)間復(fù)雜度穩(wěn)定在O(nlogn)而且空間復(fù)雜度O(1)是“原地排序”。但它在工程上的使用頻率遠(yuǎn)低于快速排序原因有二一是它訪(fǎng)問(wèn)數(shù)組的方式是跳躍式的對(duì)CPU緩存極不友好實(shí)際運(yùn)行常數(shù)很大二是它不穩(wěn)定。不過(guò)在優(yōu)先級(jí)隊(duì)列和Top K這類(lèi)問(wèn)題上堆的結(jié)構(gòu)本身而非堆排序反而是極其高效的。5. 歸并排序分治思路與穩(wěn)定性之王歸并排序是七種排序里唯一一個(gè)既滿(mǎn)足O(nlogn)最壞時(shí)間復(fù)雜度又穩(wěn)定的排序算法。它的思路再清晰不過(guò)把一個(gè)數(shù)組分成兩半分別把兩半都排好序再合并兩個(gè)有序序列成一個(gè)大的有序序列。整個(gè)過(guò)程用遞歸來(lái)實(shí)現(xiàn)先分到底再一層層“治”回去。public static void mergeSort(int[] arr) { if (arr null || arr.length 2) return; int[] temp new int[arr.length]; // 一次性創(chuàng)建輔助數(shù)組 sort(arr, 0, arr.length - 1, temp); } private static void sort(int[] arr, int left, int right, int[] temp) { if (left right) return; int mid left (right - left) / 2; sort(arr, left, mid, temp); sort(arr, mid 1, right, temp); merge(arr, left, mid, right, temp); } private static void merge(int[] arr, int left, int mid, int right, int[] temp) { int i left, j mid 1, k left; while (i mid j right) { // 這里用 保證穩(wěn)定性相等時(shí)先取左半部分 if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } while (i mid) temp[k] arr[i]; while (j right) temp[k] arr[j]; // 把臨時(shí)數(shù)組里的結(jié)果拷貝回原數(shù)組 for (int p left; p right; p) { arr[p] temp[p]; } }這段代碼里有一個(gè)很關(guān)鍵的細(xì)節(jié)輔助數(shù)組temp應(yīng)該只在mergeSort里創(chuàng)建一次而不是在每次遞歸merge時(shí)都new一個(gè)新數(shù)組。如果你在merge方法里每次new一個(gè)數(shù)組數(shù)組長(zhǎng)度加起來(lái)是O(nlogn)頻繁的內(nèi)存分配和GC會(huì)讓性能大幅下降。我見(jiàn)過(guò)不少同學(xué)在這上面栽跟頭數(shù)據(jù)量一大就性能奇差無(wú)比還誤以為是遞歸本身的問(wèn)題。歸并排序?yàn)槭裁捶€(wěn)定核心就在合并時(shí)的那個(gè)判斷當(dāng)左右兩個(gè)子數(shù)組里出現(xiàn)相等的元素時(shí)我們規(guī)定先取左邊那個(gè)。這樣一來(lái)原本在數(shù)組里靠前的相等元素最終在合并后的結(jié)果里依然靠前穩(wěn)定性就保住了。歸并排序的時(shí)間和空間復(fù)雜度分別是O(nlogn)和O(n)。它在Java的JDK里使用極其廣泛對(duì)對(duì)象數(shù)組的排序Arrays.sort(T[])底層用的就是TimSort本質(zhì)上是歸并排序的改進(jìn)版本把插入排序和小規(guī)模歸并結(jié)合了起來(lái)。原因很簡(jiǎn)單對(duì)象排序要求穩(wěn)定。而Arrays.sort(int[])底層則用的雙軸快排這是因?yàn)榛绢?lèi)型的排序不要求穩(wěn)定性可以追求更快的平均速度。6. 七種排序橫向?qū)Ρ扰cJava工程選型實(shí)戰(zhàn)到了這一步七種排序算法我已經(jīng)全部講完了代碼層面的實(shí)現(xiàn)。但作為從業(yè)者我心里很清楚一件事考完試、面完試之后真正決定你排序性能的不是哪段代碼寫(xiě)得華麗而是你在具體場(chǎng)景下能不能選對(duì)方案。所以這一章我直接講工程選型。真正的Java程序員在日常開(kāi)發(fā)中新寫(xiě)排序邏輯的機(jī)會(huì)非常少因?yàn)镴DK自帶的Arrays.sort和Collections.sort已經(jīng)足夠優(yōu)秀它們?cè)趦?nèi)部根據(jù)數(shù)據(jù)類(lèi)型和數(shù)據(jù)量自動(dòng)切換排序策略。但理解它們的策略邏輯對(duì)寫(xiě)出高性能代碼很有幫助。Arrays.sort(int[])在數(shù)據(jù)量小于47時(shí)采用插入排序大于47采用雙軸快排Arrays.sort(Object[])則使用TimSort它會(huì)在數(shù)據(jù)接近有序時(shí)利用天然有序片段達(dá)到O(n)級(jí)別的效率。什么場(chǎng)景下我會(huì)選擇手寫(xiě)排序而不是直接用JDK方法大概只有兩種第一種是你面對(duì)的是自定義結(jié)構(gòu)體且不想寫(xiě)比較器想通過(guò)一次排序完成某種特殊分組邏輯第二種是算法題環(huán)境中要求你實(shí)現(xiàn)某個(gè)特定排序來(lái)證明復(fù)雜度。除此之外請(qǐng)你務(wù)必使用JDK自帶排序因?yàn)樗隽藰O致的工程優(yōu)化手寫(xiě)版本在大部分情況下性能是打不過(guò)它的。如果你確實(shí)需要自己封裝一個(gè)排序工具類(lèi)我給一個(gè)比較通用的“混合排序”模板思路數(shù)據(jù)規(guī)模數(shù)據(jù)特征推薦算法原因 50任意直接插入排序常數(shù)極小無(wú)額外空間代碼簡(jiǎn)單50 ~ 100000大部分隨機(jī)快速排序三數(shù)取中小區(qū)間插排平均性能最佳緩存友好 100000要求穩(wěn)定性歸并排序可迭代版避免遞歸棧溢出最壞復(fù)雜度有保證且穩(wěn)定 100000要求原地排序堆排序空間O(1)時(shí)間復(fù)雜度穩(wěn)定任意規(guī)模數(shù)據(jù)基本有序插入排序或TimSort思路接近O(n)利用有序性這個(gè)表格是我踩過(guò)不少坑之后總結(jié)出來(lái)的經(jīng)驗(yàn)。一個(gè)很典型的坑是對(duì)100萬(wàn)級(jí)數(shù)據(jù)強(qiáng)行用簡(jiǎn)單選擇排序——你覺(jué)得每輪只交換一次成本低但你忽略了每輪都要掃描接近整個(gè)數(shù)組的比較成本O(n2)的增長(zhǎng)曲線(xiàn)在數(shù)據(jù)量翻倍時(shí)的代價(jià)是四倍的時(shí)間。另外多說(shuō)一句排序穩(wěn)定性對(duì)工程設(shè)計(jì)的實(shí)際影響。舉個(gè)場(chǎng)景一個(gè)交易系統(tǒng)里你先把流水按交易金額排序再把相同金額的流水按時(shí)間排序。如果第二次排序用的是穩(wěn)定排序那么相同金額的流水自然保持了時(shí)間上的先后順序如果用了不穩(wěn)定的排序同金額流水的時(shí)間順序可能被打亂最終報(bào)表展示會(huì)有一種“不專(zhuān)業(yè)”的凌亂感。這就是很多底層庫(kù)在排序?qū)ο髷?shù)據(jù)時(shí)堅(jiān)持用歸并思想的原因。7. 排序算法避坑指南與實(shí)戰(zhàn)測(cè)試心得這一章我把自己平時(shí)在寫(xiě)排序和調(diào)試排序時(shí)遇到最多的問(wèn)題匯總一下很多坑只有真正實(shí)現(xiàn)過(guò)一遍才會(huì)懂。7.1 死循環(huán)與棧溢出的排查思路快速排序和歸并排序的遞歸版本最容易出棧溢出。排查棧溢出時(shí)第一反應(yīng)應(yīng)該是遞歸終止條件是否在極端輸入下永遠(yuǎn)不會(huì)觸發(fā)?？炫爬镒畛Ｒ?jiàn)的死循環(huán)是分區(qū)后某一邊長(zhǎng)度等于原長(zhǎng)度導(dǎo)致無(wú)限遞歸。比如基準(zhǔn)值選到了最小值partition之后左邊區(qū)間長(zhǎng)度為0右邊為n-1如果遞歸調(diào)用沒(méi)有正確處理邊界就可能陷入死循環(huán)。還有一個(gè)小細(xì)節(jié)遞歸版本在大數(shù)據(jù)量下容易棧溢出的可以考慮手寫(xiě)棧將遞歸轉(zhuǎn)迭代。歸并排序可以寫(xiě)成自底向上的迭代版本先兩兩合并再四四合并……快排可以用棧保存待處理區(qū)間。這個(gè)過(guò)程在面試中也常被考察你如果能現(xiàn)場(chǎng)把遞歸改成迭代會(huì)是一個(gè)加分項(xiàng)。7.2 用測(cè)試數(shù)據(jù)“拷問(wèn)”排序算法寫(xiě)排序算法之后想要驗(yàn)證正確性不能只跑一兩個(gè)從小到大排列的數(shù)組就收工。我建議至少構(gòu)造這五類(lèi)測(cè)試數(shù)據(jù)隨機(jī)打亂的數(shù)據(jù)驗(yàn)證基本正確性完全逆序的數(shù)據(jù)比如 [n, n-1, ..., 1]考驗(yàn)最壞情況完全有序的數(shù)據(jù)考驗(yàn)最好情況與快速排序的退化問(wèn)題包含大量重復(fù)元素的數(shù)據(jù)考驗(yàn)內(nèi)層循環(huán)里相等值的處理極端邊界空數(shù)組、只有一個(gè)元素的數(shù)組、兩個(gè)元素的數(shù)組我測(cè)試時(shí)會(huì)寫(xiě)一個(gè)簡(jiǎn)單的校驗(yàn)方法先復(fù)制一份測(cè)試數(shù)據(jù)調(diào)用Arrays.sort排好再和我自己的排序結(jié)果逐位比較。這種自動(dòng)校驗(yàn)比肉眼觀察可靠得多。7.3 性能對(duì)比的“體感”數(shù)據(jù)這里分享一組我本地跑過(guò)的參考數(shù)據(jù)僅供參考不同機(jī)器差異很大1萬(wàn)個(gè)隨機(jī)int插入排序和冒泡排序耗時(shí)在幾十毫秒級(jí)別快排和歸并在個(gè)位數(shù)毫秒級(jí)當(dāng)數(shù)據(jù)量上升到10萬(wàn)級(jí)別O(n2)算法的耗時(shí)可能已經(jīng)到秒級(jí)而O(nlogn)算法依然輕松。100萬(wàn)隨機(jī)int手寫(xiě)快排大概幾百毫秒而Arrays.sort優(yōu)化過(guò)的雙軸快排可能只有它的一半。這組數(shù)據(jù)的意義在于讓你建立起“復(fù)雜度差距到底意味著什么”的直覺(jué)。很多人學(xué)算法時(shí)覺(jué)得O(n2)和O(nlogn)只是一個(gè)符號(hào)但當(dāng)數(shù)據(jù)量達(dá)到百萬(wàn)級(jí)二者差距是幾十倍到上百倍的體感差距這在生產(chǎn)環(huán)境里直接影響用戶(hù)體驗(yàn)。7.4 我踩過(guò)的三個(gè)具體的“坑”第一個(gè)坑希爾排序的gap序列選擇。有一陣我為了讓代碼看起來(lái)“高級(jí)”用了比較復(fù)雜的步長(zhǎng)序列結(jié)果在小數(shù)據(jù)集上性能反而不如簡(jiǎn)單折半。后來(lái)我明白了步長(zhǎng)序列優(yōu)劣的差距在數(shù)據(jù)量很小時(shí)顯現(xiàn)不出來(lái)而“可讀性”和“可維護(hù)性”反而更值錢(qián)。第二個(gè)坑快速排序在數(shù)據(jù)完全有序時(shí)的退化。如果每次選第一個(gè)元素當(dāng)基準(zhǔn)值對(duì)[1, 2, 3, ..., 10000]這樣的數(shù)組每輪分區(qū)都是極端不均衡的遞歸深度接近10000直接導(dǎo)致StackOverflowError。我改用了三數(shù)取中之后這個(gè)問(wèn)題徹底消失。這個(gè)坑幾乎每個(gè)手寫(xiě)快排的人都會(huì)踩到。第三個(gè)坑忘記更新循環(huán)邊界條件。寫(xiě)歸并排序的merge時(shí)如果最后把temp數(shù)組拷貝回原數(shù)組時(shí)循環(huán)邊界寫(xiě)錯(cuò)比如從0開(kāi)始而不是從left開(kāi)始你會(huì)發(fā)現(xiàn)排序結(jié)果總是“部分有序、部分混亂”而且這種bug非常難通過(guò)小數(shù)據(jù)量樣例發(fā)現(xiàn)因?yàn)閯偤门銮蛇吔缯_的情況經(jīng)常發(fā)生。排查這類(lèi)問(wèn)題最有效的方式還是構(gòu)造大隨機(jī)數(shù)據(jù)做自動(dòng)校驗(yàn)。7.5 一份可以保底自檢的對(duì)照表面試考點(diǎn)常見(jiàn)誤區(qū)正確的理解快排空間復(fù)雜度誤答O(1)遞歸調(diào)用棧深度平均O(logn)最壞O(n)歸并空間復(fù)雜度忽略輔助數(shù)組需要O(n)的臨時(shí)數(shù)組空間堆排序時(shí)間復(fù)雜度以為建堆是O(nlogn)堆化過(guò)程是O(n)整體是O(nlogn)穩(wěn)定性搞不清哪些穩(wěn)定哪些不穩(wěn)定插入、冒泡、歸并穩(wěn)定其余不穩(wěn)定希爾排序不穩(wěn)定以為分組內(nèi)部插入排序是穩(wěn)定跨組交換破壞了穩(wěn)定性把這張表爛熟于心你在面試中應(yīng)對(duì)排序部分的追問(wèn)時(shí)至少不會(huì)出現(xiàn)方向性硬傷。8. 總結(jié)一點(diǎn)個(gè)人體會(huì)寫(xiě)排序算法這件事我最大的體會(huì)是它教會(huì)你的從來(lái)不只是“排序”而是遞歸、分治、復(fù)雜度分析、以及“把問(wèn)題分解成更小問(wèn)題”的思維方式。從直接插入到希爾從冒泡到快排從簡(jiǎn)單選擇到堆排序再到歸并排序你能清晰地看到一條不斷“往前提性能上限”的演進(jìn)路線(xiàn)用空間換時(shí)間歸并、用隨機(jī)化保證平均性能快排、用二叉樹(shù)結(jié)構(gòu)優(yōu)化選擇過(guò)程堆排序。我強(qiáng)烈建議你拿出一兩個(gè)小時(shí)把這七種排序全部手寫(xiě)一遍然后跑一遍我上面說(shuō)的測(cè)試數(shù)據(jù)集親眼看一看不同算法在不同數(shù)據(jù)下的表現(xiàn)差異。這個(gè)過(guò)程比看十篇博客都有用。另外一個(gè)小技巧在你寫(xiě)完某個(gè)排序后嘗試把你的實(shí)現(xiàn)和JDK的Arrays.sort做個(gè)對(duì)比然后問(wèn)自己三個(gè)問(wèn)題——我的實(shí)現(xiàn)能否處理極端輸入我的實(shí)現(xiàn)是否浪費(fèi)了空間我的實(shí)現(xiàn)能否在復(fù)雜度上壓住最壞情況這三個(gè)問(wèn)題每次都會(huì)讓你有所收獲。排序算法是很好的“分治思想的微型實(shí)驗(yàn)田”吃透了它們你再去看二叉樹(shù)遍歷、圖的最短路徑這些更復(fù)雜的問(wèn)題會(huì)覺(jué)得思路順暢很多。希望這篇內(nèi)容能幫你在排序這塊少踩點(diǎn)坑真正把這些算法變成你的肌肉記憶。 Java排序算法全詳解：七大經(jīng)典排序?qū)崿F(xiàn)與工程選型
排序算法是數(shù)據(jù)結(jié)構(gòu)課里那塊最“硬”的骨頭也是各大廠(chǎng)筆試面試中出場(chǎng)率極高的?？?。這次梳理的是Java視角下的七大排序算法也就是直接插入排序、希爾排序、冒泡排序、快速排序、簡(jiǎn)單選擇排序、堆排序和歸并排序。無(wú)論你是正在準(zhǔn)備校招的應(yīng)屆生還是在公司里做業(yè)務(wù)開(kāi)發(fā)時(shí)偶爾需要手寫(xiě)一段排序邏輯或者純粹想把這些經(jīng)典算法吃透這篇內(nèi)容都能給你一個(gè)完整、可直接參考的脈絡(luò)。我會(huì)把每種算法的核心思想、Java實(shí)現(xiàn)、復(fù)雜度推導(dǎo)以及只有在真正寫(xiě)代碼時(shí)才會(huì)遇到的那些坑全都攤開(kāi)來(lái)講。這篇內(nèi)容不是單純的代碼堆砌我會(huì)按照“家族”把它們分組插入排序家族、交換排序家族、選擇排序家族再加上歸并排序這個(gè)“分治王者”這樣分類(lèi)的好處是你能從設(shè)計(jì)思路上去理解而不是死記硬背代碼。每一類(lèi)我都會(huì)給出完整的Java代碼并且標(biāo)注清楚哪些地方容易寫(xiě)錯(cuò)哪些細(xì)節(jié)是面試官特別喜歡追問(wèn)的。我還會(huì)分享一些在實(shí)際工程項(xiàng)目里篩選排序方案的經(jīng)驗(yàn)比如面對(duì)幾萬(wàn)條數(shù)據(jù)時(shí)該無(wú)腦選哪種、什么時(shí)候別手寫(xiě)排序而應(yīng)該直接調(diào)JDK自帶的方法。1. 七大排序全景透視復(fù)雜度與場(chǎng)景選型先把七種算法放到一張表里看全貌。這張表是你復(fù)習(xí)和面試前必須刻在腦子里的東西它決定了你在不同場(chǎng)景下第一時(shí)間該掏出哪種排序。排序算法平均時(shí)間復(fù)雜度最壞時(shí)間復(fù)雜度最好時(shí)間復(fù)雜度空間復(fù)雜度穩(wěn)定性直接插入排序O(n2)O(n2)O(n)O(1)穩(wěn)定希爾排序O(n^1.3~1.5)O(n2)O(n)O(1)不穩(wěn)定冒泡排序O(n2)O(n2)O(n)O(1)穩(wěn)定快速排序O(nlogn)O(n2)O(nlogn)O(logn)~O(n)不穩(wěn)定簡(jiǎn)單選擇排序O(n2)O(n2)O(n2)O(1)不穩(wěn)定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不穩(wěn)定歸并排序O(nlogn)O(nlogn)O(nlogn)O(n)穩(wěn)定讀這張表有個(gè)規(guī)律希望你能記下來(lái)大多數(shù)“不穩(wěn)定”的排序算法問(wèn)題都出在“跳躍式交換元素”這個(gè)動(dòng)作上。比如希爾排序是跳著組內(nèi)比較交換快速排序是基準(zhǔn)值左右跳躍式交換簡(jiǎn)單選擇排序是每輪把最小的元素直接甩到前面堆排序更是隔著整個(gè)堆在交換。反而是那些只在相鄰元素之間“小步挪動(dòng)”的算法——插入排序、冒泡排序、歸并排序——天然就能保證穩(wěn)定性。穩(wěn)定性這個(gè)詞很多初學(xué)者覺(jué)得無(wú)所謂但我舉個(gè)例子你就明白了。假設(shè)你要給一個(gè)班級(jí)的學(xué)生表排序先按年齡排好序再按姓名排序如果排序算法不穩(wěn)定第二次按姓名排序時(shí)年齡相同的學(xué)生順序可能就亂了你前面按年齡排的順序等于白做了。實(shí)際系統(tǒng)里這種情況太常見(jiàn)了先按主鍵排序再按副鍵排序穩(wěn)定的排序算法能保證兩次排序結(jié)果可疊加。選型的邏輯我一般看三個(gè)指標(biāo)數(shù)據(jù)量大小、數(shù)據(jù)初始有序程度、是否要求穩(wěn)定。數(shù)據(jù)量很小比如50個(gè)以?xún)?nèi)直接插入排序幾乎無(wú)敵因?yàn)槌?shù)極小沒(méi)有額外空間消耗。數(shù)據(jù)量中等幾千到幾萬(wàn)快速排序是最優(yōu)選平均性能最強(qiáng)但要注意最壞退化問(wèn)題。數(shù)據(jù)量超大百萬(wàn)級(jí)以上且要求最壞時(shí)間復(fù)雜度可控歸并排序或堆排序更穩(wěn)。要求穩(wěn)定且數(shù)據(jù)量不小歸并排序是你的唯一選擇Java的Collections.sort底層也是這個(gè)思路。幾乎有序的數(shù)據(jù)插入排序的最好情況O(n)優(yōu)勢(shì)就體現(xiàn)出來(lái)了很多商用的混合排序會(huì)用它來(lái)收尾。2. 插入排序家族直接插入與希爾2.1 直接插入排序像整理手牌一樣簡(jiǎn)單如果你打撲克牌時(shí)習(xí)慣把摸到的新牌插入到手里已經(jīng)排好序的牌堆中那你已經(jīng)懂了直接插入排序的核心思想。把數(shù)組看成兩部分左邊是已排序區(qū)右邊是待排序區(qū)每次從待排序區(qū)拿出第一個(gè)數(shù)把它往左插到合適位置。Java實(shí)現(xiàn)如下public static void insertSort(int[] arr) { if (arr null || arr.length 2) return; // 默認(rèn)arr[0]是已排序區(qū)從arr[1]開(kāi)始依次處理 for (int i 1; i arr.length; i) { int current arr[i]; // 待插入的數(shù) int j i - 1; // 從右往左找合適位置同時(shí)把元素向右挪動(dòng)給current騰位置 while (j 0 arr[j] current) { arr[j 1] arr[j]; j--; } arr[j 1] current; } }這段代碼里最容易出錯(cuò)的地方是最后那句arr[j 1] current;。很多初學(xué)者搞不清為什么是j1而不是j因?yàn)閣hile循環(huán)退出時(shí)有兩種情況要么j已經(jīng)小于0了說(shuō)明current應(yīng)該放在數(shù)組最前面要么arr[j]已經(jīng)不大于current了說(shuō)明current應(yīng)該插在arr[j]的后面。不管是哪種正確的位置都是索引j1。復(fù)雜度這塊最壞和平均都是O(n2)——你每次插入都要把前面一大片元素往后挪。但最好情況很討喜如果數(shù)據(jù)本來(lái)就是有序的while循環(huán)一次都不進(jìn)外層循環(huán)掃一遍就結(jié)束時(shí)間復(fù)雜度直接降到O(n)。所以它特別適合那種“基本有序”的數(shù)據(jù)。2.2 希爾排序給插入排序裝上“渦輪增壓”希爾排序是直接插入排序的改進(jìn)版思路非常聰明先讓數(shù)據(jù)整體變得“基本有序”再去做最后一次直接插入排序。怎么讓數(shù)據(jù)基本有序答案是對(duì)數(shù)組進(jìn)行分組組內(nèi)排序。關(guān)鍵點(diǎn)是分組的方式不是簡(jiǎn)單的連續(xù)分塊而是“按間隔取元素”分組。假設(shè)數(shù)組長(zhǎng)度是8間隔gap先取4那么下標(biāo)0、4一組1、5一組2、6一組3、7一組分別做插入排序。然后gap縮小為2再按新的間隔分組排序。最后gap變成1就是標(biāo)準(zhǔn)的直接插入排序了。public static void shellSort(int[] arr) { if (arr null || arr.length 2) return; int n arr.length; // 初始間隔取數(shù)組長(zhǎng)度的一半以后每輪砍半 for (int gap n / 2; gap 0; gap / 2) { // 從gap開(kāi)始逐個(gè)對(duì)“邏輯分組”做插入排序 for (int i gap; i n; i) { int current arr[i]; int j i; // 組內(nèi)做插入排序比較時(shí)跨越gap距離 while (j - gap 0 arr[j - gap] current) { arr[j] arr[j - gap]; j - gap; } arr[j] current; } } }注意這里的雙層循環(huán)變成了三層嵌套初看容易暈但你可以這樣理解i從gap掃到n-1每次處理時(shí)它都是在處理某個(gè)分組里的“下一個(gè)元素”內(nèi)層while負(fù)責(zé)在當(dāng)前分組里往前插入。這個(gè)寫(xiě)法比起先按組循環(huán)再組內(nèi)排序代碼更簡(jiǎn)潔但理解難度稍高。關(guān)于間隔序列經(jīng)典的“每次除以2”不是最優(yōu)的目前比較常用的是Sedgewick序列比如1、5、19、41、109……這種序列能達(dá)到O(n^1.3)級(jí)別的時(shí)間復(fù)雜度。我在實(shí)際項(xiàng)目里除非數(shù)據(jù)特征特別明確一般不會(huì)手寫(xiě)希爾排序但在算法題里偶爾有奇效尤其是某些對(duì)空間要求苛刻的場(chǎng)景。2.3 為什么希爾排序不穩(wěn)定希爾排序的不穩(wěn)定性是個(gè)經(jīng)典面試點(diǎn)。原因是分組排序時(shí)兩個(gè)數(shù)值相等的元素可能因?yàn)榉纸M的不同而被拆散后面某個(gè)組內(nèi)交換時(shí)讓原本靠前的那個(gè)元素跑到后面去了。舉個(gè)具體例子數(shù)組[2, 1, 2]gap1時(shí)直接插入排序沒(méi)問(wèn)題但如果gap2分組下標(biāo)0和下標(biāo)2這兩個(gè)“2”被分到同一組組內(nèi)排序時(shí)如果發(fā)生交換兩個(gè)2的相對(duì)位置就可能顛倒。這種跨越間隔的移動(dòng)是破壞穩(wěn)定性的元兇。3. 交換排序家族冒泡與快速3.1 冒泡排序教學(xué)常客工程棄兒冒泡排序的思路就是“大的往下沉小的往上浮”。每輪從頭開(kāi)始兩兩比較相鄰元素如果順序反了就交換一輪下來(lái)最大的數(shù)被“冒泡”到了最后。重復(fù)n輪就全部有序。public static void bubbleSort(int[] arr) { if (arr null || arr.length 2) return; int n arr.length; for (int i 0; i n - 1; i) { boolean swapped false; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; swapped true; } } // 如果某一輪沒(méi)有任何交換說(shuō)明已經(jīng)有序直接結(jié)束 if (!swapped) break; } }我加了一個(gè)swapped標(biāo)志位這是冒泡排序最重要的優(yōu)化——數(shù)據(jù)本來(lái)就有序時(shí)第一輪結(jié)束就能提前退出時(shí)間復(fù)雜度降到O(n)。還有一個(gè)優(yōu)化思路是記錄最后一次發(fā)生交換的位置這個(gè)位置之后的數(shù)據(jù)已經(jīng)排好了下一輪就不需要再遍歷到末尾。但說(shuō)句大實(shí)話(huà)冒泡排序在實(shí)際工程里幾乎不會(huì)被用到哪怕是幾百條數(shù)據(jù)處理直接插入排序都比它快得多因?yàn)樗龅慕粨Q次數(shù)太多了。它存在的最大意義就是當(dāng)作教學(xué)案例讓你理解最樸素的交換排序思想。3.2 快速排序最常用的“分治王者”快排的核心思想是分治隨便挑一個(gè)數(shù)當(dāng)基準(zhǔn)值pivot通過(guò)一次遍歷把數(shù)組分成兩撥比pivot小的放左邊、大的放右邊然后對(duì)左右兩撥分別遞歸做同樣的事最終整個(gè)數(shù)組有序?？焖倥判虻膶?shí)現(xiàn)版本很多寫(xiě)法差異很大我分享一個(gè)我用了很多年的經(jīng)典寫(xiě)法它叫“挖坑法”比較容易理解也不會(huì)寫(xiě)錯(cuò)public static void quickSort(int[] arr, int left, int right) { if (left right) return; // 三數(shù)取中優(yōu)化下面單獨(dú)講 int midIndex left (right - left) / 2; if (arr[left] arr[midIndex]) swap(arr, left, midIndex); if (arr[left] arr[right]) swap(arr, left, right); if (arr[midIndex] arr[right]) swap(arr, midIndex, right); swap(arr, left, midIndex); // 把基準(zhǔn)值放到最左邊 int pivot arr[left]; int i left, j right; while (i j) { // 必須先從右往左找比pivot小的 while (i j arr[j] pivot) j--; if (i j) { arr[i] arr[j]; i; } // 再?gòu)淖笸艺冶萷ivot大的 while (i j arr[i] pivot) i; if (i j) { arr[j] arr[i]; j--; } } arr[i] pivot; // i和j相遇的位置就是基準(zhǔn)值的最終位置 quickSort(arr, left, i - 1); quickSort(arr, i 1, right); } private static void swap(int[] arr, int a, int b) { int tmp arr[a]; arr[a] arr[b]; arr[b] tmp; }這個(gè)寫(xiě)法里有兩個(gè)隱藏很深的坑。第一個(gè)坑是為什么內(nèi)層循環(huán)必須先從右往左走因?yàn)槟惆鸦鶞?zhǔn)值放在了最左邊相當(dāng)于左邊“挖了個(gè)坑”你需要先從右邊找一個(gè)比基準(zhǔn)值小的數(shù)來(lái)填左邊的坑。如果先從左往右找左邊第一個(gè)元素可能就直接把坑越過(guò)了邏輯會(huì)亂。第二個(gè)坑是內(nèi)層while里的條件必須是和不能寫(xiě)成和。如果用嚴(yán)格大于或小于遇到和基準(zhǔn)值相等的元素時(shí)i和j都可能卡住不動(dòng)導(dǎo)致死循環(huán)或者無(wú)限遞歸。關(guān)于三數(shù)取中的優(yōu)化我簡(jiǎn)單解釋一下為什么需要它。快排最怕的是每次選基準(zhǔn)值都選到最大值或最小值那樣分區(qū)極不平衡遞歸深度達(dá)到n層時(shí)間復(fù)雜度退化成O(n2)。取數(shù)組左端、中間、右端三個(gè)數(shù)的中間值作為基準(zhǔn)值可以在很大程度上避免這個(gè)問(wèn)題尤其是對(duì)“已經(jīng)有序”的數(shù)組效果立竿見(jiàn)影。還有一個(gè)工程上的優(yōu)化細(xì)節(jié)當(dāng)子數(shù)組長(zhǎng)度比較小比如小于10時(shí)遞歸調(diào)用的開(kāi)銷(xiāo)占比很大很多版本的快排會(huì)切換到直接插入排序來(lái)收尾。JDK內(nèi)部實(shí)現(xiàn)的排序就是這么干的大區(qū)間用快排思路小區(qū)間用插入排序整體性能能提升不少。3.3 快排的空間復(fù)雜度與穩(wěn)定性快排的空間復(fù)雜度是O(logn)這里的空間不是指額外的數(shù)組而是遞歸調(diào)用棧的深度。理想情況下每次分區(qū)都均衡遞歸層數(shù)是logn最壞情況下每次都只拆出一個(gè)元素遞歸層數(shù)是n棧溢出風(fēng)險(xiǎn)很高。這也就是為什么面試官會(huì)追問(wèn)“快排空間復(fù)雜度是多少”很多人會(huì)答O(1)這就錯(cuò)了——遞歸本身在消耗調(diào)用?？臻g。快速排序不穩(wěn)定原因在于它的交換是“跳躍式”的——基準(zhǔn)值可能被直接換到很遠(yuǎn)的位置兩個(gè)數(shù)值相同的元素的相對(duì)順序在這個(gè)過(guò)程中可能被改變。所以如果業(yè)務(wù)上有穩(wěn)定排序要求快排不能直接上。4. 選擇排序家族簡(jiǎn)單選擇與堆排序4.1 簡(jiǎn)單選擇排序最直觀但毫無(wú)“亮點(diǎn)”簡(jiǎn)單選擇排序的思路比冒泡還直觀第一輪從0到n-1里找到最小的數(shù)放到下標(biāo)0的位置第二輪從1到n-1里找到最小的放到下標(biāo)1的位置以此類(lèi)推。public static void selectSort(int[] arr) { if (arr null || arr.length 2) return; for (int i 0; i arr.length - 1; i) { int minIndex i; for (int j i 1; j arr.length; j) { if (arr[j] arr[minIndex]) { minIndex j; } } if (minIndex ! i) { int tmp arr[i]; arr[i] arr[minIndex]; arr[minIndex] tmp; } } }這個(gè)算法的時(shí)間復(fù)雜度不管是最好、最壞還是平均都是O(n2)因?yàn)樗恳惠喍家暾麙呙枰槐槭Ｓ鄶?shù)組來(lái)找最小元素不能利用數(shù)據(jù)原本的有序性。它的交換次數(shù)很少每輪最多一次理論上比冒泡的交換成本低但比較次數(shù)一樣多實(shí)際性能并不占優(yōu)。簡(jiǎn)單選擇排序的不穩(wěn)定性值得拿出來(lái)專(zhuān)門(mén)講。考慮數(shù)組 [5, 5, 1]第一輪找到最小元素1然后把它和下標(biāo)0的5交換結(jié)果是 [1, 5, 5]。你會(huì)看到原來(lái)在前面的那個(gè)“5”被第一次交換到了數(shù)組末尾兩個(gè)5的相對(duì)順序顛倒了。這給我們的啟示是凡是“把最值直接換到目標(biāo)區(qū)”的排序都得小心穩(wěn)定性問(wèn)題。4.2 堆排序建堆、調(diào)整與樸素“堆”的誤區(qū)堆排序的核心是“完全二叉樹(shù)”和“大頂堆”。升序排序用大頂堆堆頂元素永遠(yuǎn)是整個(gè)堆的最大值每次把堆頂和當(dāng)前未排序區(qū)域的最后一個(gè)元素交換堆頂?shù)淖畲笾稻汀皾L”到數(shù)組末尾去了然后重新調(diào)整堆結(jié)構(gòu)讓新的堆頂繼續(xù)成為剩余元素里的最大值。堆排序的兩個(gè)關(guān)鍵步驟簡(jiǎn)稱(chēng)為“建堆”和“調(diào)整”。建堆的意思是從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始從下往上做堆化heapify調(diào)整的意思是把堆頂和末尾交換后從堆頂開(kāi)始向下調(diào)整恢復(fù)大頂堆的性質(zhì)。public static void heapSort(int[] arr) { if (arr null || arr.length 2) return; int n arr.length; // 建堆從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始向上調(diào)整 for (int i n / 2 - 1; i 0; i--) { heapify(arr, n, i); } // 逐個(gè)把堆頂最大元素放到末尾 for (int i n - 1; i 0; i--) { swap(arr, 0, i); heapify(arr, i, 0); } } private static void heapify(int[] arr, int size, int root) { int largest root; int left 2 * root 1; int right 2 * root 2; if (left size arr[left] arr[largest]) largest left; if (right size arr[right] arr[largest]) largest right; if (largest ! root) { swap(arr, largest, root); heapify(arr, size, largest); // 遞歸調(diào)整被換下去的子樹(shù) } }很多初學(xué)者會(huì)問(wèn)為什么建堆的循環(huán)是從n/2 - 1開(kāi)始而不是從n-1開(kāi)始因?yàn)橥耆鏄?shù)里下標(biāo)n/2到n-1全部是葉子節(jié)點(diǎn)葉子節(jié)點(diǎn)沒(méi)有孩子本身就已經(jīng)滿(mǎn)足堆的性質(zhì)不需要調(diào)整。從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始倒序遍歷每個(gè)節(jié)點(diǎn)最多和它的子樹(shù)做一次交換時(shí)間復(fù)雜度是O(n)這里很多人有誤解以為建堆要O(nlogn)實(shí)際上這樣做是“每個(gè)節(jié)點(diǎn)調(diào)整一次”整體是O(n)。堆排序的特點(diǎn)是時(shí)間復(fù)雜度穩(wěn)定在O(nlogn)而且空間復(fù)雜度O(1)是“原地排序”。但它在工程上的使用頻率遠(yuǎn)低于快速排序原因有二一是它訪(fǎng)問(wèn)數(shù)組的方式是跳躍式的對(duì)CPU緩存極不友好實(shí)際運(yùn)行常數(shù)很大二是它不穩(wěn)定。不過(guò)在優(yōu)先級(jí)隊(duì)列和Top K這類(lèi)問(wèn)題上堆的結(jié)構(gòu)本身而非堆排序反而是極其高效的。5. 歸并排序分治思路與穩(wěn)定性之王歸并排序是七種排序里唯一一個(gè)既滿(mǎn)足O(nlogn)最壞時(shí)間復(fù)雜度又穩(wěn)定的排序算法。它的思路再清晰不過(guò)把一個(gè)數(shù)組分成兩半分別把兩半都排好序再合并兩個(gè)有序序列成一個(gè)大的有序序列。整個(gè)過(guò)程用遞歸來(lái)實(shí)現(xiàn)先分到底再一層層“治”回去。public static void mergeSort(int[] arr) { if (arr null || arr.length 2) return; int[] temp new int[arr.length]; // 一次性創(chuàng)建輔助數(shù)組 sort(arr, 0, arr.length - 1, temp); } private static void sort(int[] arr, int left, int right, int[] temp) { if (left right) return; int mid left (right - left) / 2; sort(arr, left, mid, temp); sort(arr, mid 1, right, temp); merge(arr, left, mid, right, temp); } private static void merge(int[] arr, int left, int mid, int right, int[] temp) { int i left, j mid 1, k left; while (i mid j right) { // 這里用 保證穩(wěn)定性相等時(shí)先取左半部分 if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } while (i mid) temp[k] arr[i]; while (j right) temp[k] arr[j]; // 把臨時(shí)數(shù)組里的結(jié)果拷貝回原數(shù)組 for (int p left; p right; p) { arr[p] temp[p]; } }這段代碼里有一個(gè)很關(guān)鍵的細(xì)節(jié)輔助數(shù)組temp應(yīng)該只在mergeSort里創(chuàng)建一次而不是在每次遞歸merge時(shí)都new一個(gè)新數(shù)組。如果你在merge方法里每次new一個(gè)數(shù)組數(shù)組長(zhǎng)度加起來(lái)是O(nlogn)頻繁的內(nèi)存分配和GC會(huì)讓性能大幅下降。我見(jiàn)過(guò)不少同學(xué)在這上面栽跟頭數(shù)據(jù)量一大就性能奇差無(wú)比還誤以為是遞歸本身的問(wèn)題。歸并排序?yàn)槭裁捶€(wěn)定核心就在合并時(shí)的那個(gè)判斷當(dāng)左右兩個(gè)子數(shù)組里出現(xiàn)相等的元素時(shí)我們規(guī)定先取左邊那個(gè)。這樣一來(lái)原本在數(shù)組里靠前的相等元素最終在合并后的結(jié)果里依然靠前穩(wěn)定性就保住了。歸并排序的時(shí)間和空間復(fù)雜度分別是O(nlogn)和O(n)。它在Java的JDK里使用極其廣泛對(duì)對(duì)象數(shù)組的排序Arrays.sort(T[])底層用的就是TimSort本質(zhì)上是歸并排序的改進(jìn)版本把插入排序和小規(guī)模歸并結(jié)合了起來(lái)。原因很簡(jiǎn)單對(duì)象排序要求穩(wěn)定。而Arrays.sort(int[])底層則用的雙軸快排這是因?yàn)榛绢?lèi)型的排序不要求穩(wěn)定性可以追求更快的平均速度。6. 七種排序橫向?qū)Ρ扰cJava工程選型實(shí)戰(zhàn)到了這一步七種排序算法我已經(jīng)全部講完了代碼層面的實(shí)現(xiàn)。但作為從業(yè)者我心里很清楚一件事考完試、面完試之后真正決定你排序性能的不是哪段代碼寫(xiě)得華麗而是你在具體場(chǎng)景下能不能選對(duì)方案。所以這一章我直接講工程選型。真正的Java程序員在日常開(kāi)發(fā)中新寫(xiě)排序邏輯的機(jī)會(huì)非常少因?yàn)镴DK自帶的Arrays.sort和Collections.sort已經(jīng)足夠優(yōu)秀它們?cè)趦?nèi)部根據(jù)數(shù)據(jù)類(lèi)型和數(shù)據(jù)量自動(dòng)切換排序策略。但理解它們的策略邏輯對(duì)寫(xiě)出高性能代碼很有幫助。Arrays.sort(int[])在數(shù)據(jù)量小于47時(shí)采用插入排序大于47采用雙軸快排Arrays.sort(Object[])則使用TimSort它會(huì)在數(shù)據(jù)接近有序時(shí)利用天然有序片段達(dá)到O(n)級(jí)別的效率。什么場(chǎng)景下我會(huì)選擇手寫(xiě)排序而不是直接用JDK方法大概只有兩種第一種是你面對(duì)的是自定義結(jié)構(gòu)體且不想寫(xiě)比較器想通過(guò)一次排序完成某種特殊分組邏輯第二種是算法題環(huán)境中要求你實(shí)現(xiàn)某個(gè)特定排序來(lái)證明復(fù)雜度。除此之外請(qǐng)你務(wù)必使用JDK自帶排序因?yàn)樗隽藰O致的工程優(yōu)化手寫(xiě)版本在大部分情況下性能是打不過(guò)它的。如果你確實(shí)需要自己封裝一個(gè)排序工具類(lèi)我給一個(gè)比較通用的“混合排序”模板思路數(shù)據(jù)規(guī)模數(shù)據(jù)特征推薦算法原因 50任意直接插入排序常數(shù)極小無(wú)額外空間代碼簡(jiǎn)單50 ~ 100000大部分隨機(jī)快速排序三數(shù)取中小區(qū)間插排平均性能最佳緩存友好 100000要求穩(wěn)定性歸并排序可迭代版避免遞歸棧溢出最壞復(fù)雜度有保證且穩(wěn)定 100000要求原地排序堆排序空間O(1)時(shí)間復(fù)雜度穩(wěn)定任意規(guī)模數(shù)據(jù)基本有序插入排序或TimSort思路接近O(n)利用有序性這個(gè)表格是我踩過(guò)不少坑之后總結(jié)出來(lái)的經(jīng)驗(yàn)。一個(gè)很典型的坑是對(duì)100萬(wàn)級(jí)數(shù)據(jù)強(qiáng)行用簡(jiǎn)單選擇排序——你覺(jué)得每輪只交換一次成本低但你忽略了每輪都要掃描接近整個(gè)數(shù)組的比較成本O(n2)的增長(zhǎng)曲線(xiàn)在數(shù)據(jù)量翻倍時(shí)的代價(jià)是四倍的時(shí)間。另外多說(shuō)一句排序穩(wěn)定性對(duì)工程設(shè)計(jì)的實(shí)際影響。舉個(gè)場(chǎng)景一個(gè)交易系統(tǒng)里你先把流水按交易金額排序再把相同金額的流水按時(shí)間排序。如果第二次排序用的是穩(wěn)定排序那么相同金額的流水自然保持了時(shí)間上的先后順序如果用了不穩(wěn)定的排序同金額流水的時(shí)間順序可能被打亂最終報(bào)表展示會(huì)有一種“不專(zhuān)業(yè)”的凌亂感。這就是很多底層庫(kù)在排序?qū)ο髷?shù)據(jù)時(shí)堅(jiān)持用歸并思想的原因。7. 排序算法避坑指南與實(shí)戰(zhàn)測(cè)試心得這一章我把自己平時(shí)在寫(xiě)排序和調(diào)試排序時(shí)遇到最多的問(wèn)題匯總一下很多坑只有真正實(shí)現(xiàn)過(guò)一遍才會(huì)懂。7.1 死循環(huán)與棧溢出的排查思路快速排序和歸并排序的遞歸版本最容易出棧溢出。排查棧溢出時(shí)第一反應(yīng)應(yīng)該是遞歸終止條件是否在極端輸入下永遠(yuǎn)不會(huì)觸發(fā)?？炫爬镒畛Ｒ?jiàn)的死循環(huán)是分區(qū)后某一邊長(zhǎng)度等于原長(zhǎng)度導(dǎo)致無(wú)限遞歸。比如基準(zhǔn)值選到了最小值partition之后左邊區(qū)間長(zhǎng)度為0右邊為n-1如果遞歸調(diào)用沒(méi)有正確處理邊界就可能陷入死循環(huán)。還有一個(gè)小細(xì)節(jié)遞歸版本在大數(shù)據(jù)量下容易棧溢出的可以考慮手寫(xiě)棧將遞歸轉(zhuǎn)迭代。歸并排序可以寫(xiě)成自底向上的迭代版本先兩兩合并再四四合并……快排可以用棧保存待處理區(qū)間。這個(gè)過(guò)程在面試中也常被考察你如果能現(xiàn)場(chǎng)把遞歸改成迭代會(huì)是一個(gè)加分項(xiàng)。7.2 用測(cè)試數(shù)據(jù)“拷問(wèn)”排序算法寫(xiě)排序算法之后想要驗(yàn)證正確性不能只跑一兩個(gè)從小到大排列的數(shù)組就收工。我建議至少構(gòu)造這五類(lèi)測(cè)試數(shù)據(jù)隨機(jī)打亂的數(shù)據(jù)驗(yàn)證基本正確性完全逆序的數(shù)據(jù)比如 [n, n-1, ..., 1]考驗(yàn)最壞情況完全有序的數(shù)據(jù)考驗(yàn)最好情況與快速排序的退化問(wèn)題包含大量重復(fù)元素的數(shù)據(jù)考驗(yàn)內(nèi)層循環(huán)里相等值的處理極端邊界空數(shù)組、只有一個(gè)元素的數(shù)組、兩個(gè)元素的數(shù)組我測(cè)試時(shí)會(huì)寫(xiě)一個(gè)簡(jiǎn)單的校驗(yàn)方法先復(fù)制一份測(cè)試數(shù)據(jù)調(diào)用Arrays.sort排好再和我自己的排序結(jié)果逐位比較。這種自動(dòng)校驗(yàn)比肉眼觀察可靠得多。7.3 性能對(duì)比的“體感”數(shù)據(jù)這里分享一組我本地跑過(guò)的參考數(shù)據(jù)僅供參考不同機(jī)器差異很大1萬(wàn)個(gè)隨機(jī)int插入排序和冒泡排序耗時(shí)在幾十毫秒級(jí)別快排和歸并在個(gè)位數(shù)毫秒級(jí)當(dāng)數(shù)據(jù)量上升到10萬(wàn)級(jí)別O(n2)算法的耗時(shí)可能已經(jīng)到秒級(jí)而O(nlogn)算法依然輕松。100萬(wàn)隨機(jī)int手寫(xiě)快排大概幾百毫秒而Arrays.sort優(yōu)化過(guò)的雙軸快排可能只有它的一半。這組數(shù)據(jù)的意義在于讓你建立起“復(fù)雜度差距到底意味著什么”的直覺(jué)。很多人學(xué)算法時(shí)覺(jué)得O(n2)和O(nlogn)只是一個(gè)符號(hào)但當(dāng)數(shù)據(jù)量達(dá)到百萬(wàn)級(jí)二者差距是幾十倍到上百倍的體感差距這在生產(chǎn)環(huán)境里直接影響用戶(hù)體驗(yàn)。7.4 我踩過(guò)的三個(gè)具體的“坑”第一個(gè)坑希爾排序的gap序列選擇。有一陣我為了讓代碼看起來(lái)“高級(jí)”用了比較復(fù)雜的步長(zhǎng)序列結(jié)果在小數(shù)據(jù)集上性能反而不如簡(jiǎn)單折半。后來(lái)我明白了步長(zhǎng)序列優(yōu)劣的差距在數(shù)據(jù)量很小時(shí)顯現(xiàn)不出來(lái)而“可讀性”和“可維護(hù)性”反而更值錢(qián)。第二個(gè)坑快速排序在數(shù)據(jù)完全有序時(shí)的退化。如果每次選第一個(gè)元素當(dāng)基準(zhǔn)值對(duì)[1, 2, 3, ..., 10000]這樣的數(shù)組每輪分區(qū)都是極端不均衡的遞歸深度接近10000直接導(dǎo)致StackOverflowError。我改用了三數(shù)取中之后這個(gè)問(wèn)題徹底消失。這個(gè)坑幾乎每個(gè)手寫(xiě)快排的人都會(huì)踩到。第三個(gè)坑忘記更新循環(huán)邊界條件。寫(xiě)歸并排序的merge時(shí)如果最后把temp數(shù)組拷貝回原數(shù)組時(shí)循環(huán)邊界寫(xiě)錯(cuò)比如從0開(kāi)始而不是從left開(kāi)始你會(huì)發(fā)現(xiàn)排序結(jié)果總是“部分有序、部分混亂”而且這種bug非常難通過(guò)小數(shù)據(jù)量樣例發(fā)現(xiàn)因?yàn)閯偤门銮蛇吔缯_的情況經(jīng)常發(fā)生。排查這類(lèi)問(wèn)題最有效的方式還是構(gòu)造大隨機(jī)數(shù)據(jù)做自動(dòng)校驗(yàn)。7.5 一份可以保底自檢的對(duì)照表面試考點(diǎn)常見(jiàn)誤區(qū)正確的理解快排空間復(fù)雜度誤答O(1)遞歸調(diào)用棧深度平均O(logn)最壞O(n)歸并空間復(fù)雜度忽略輔助數(shù)組需要O(n)的臨時(shí)數(shù)組空間堆排序時(shí)間復(fù)雜度以為建堆是O(nlogn)堆化過(guò)程是O(n)整體是O(nlogn)穩(wěn)定性搞不清哪些穩(wěn)定哪些不穩(wěn)定插入、冒泡、歸并穩(wěn)定其余不穩(wěn)定希爾排序不穩(wěn)定以為分組內(nèi)部插入排序是穩(wěn)定跨組交換破壞了穩(wěn)定性把這張表爛熟于心你在面試中應(yīng)對(duì)排序部分的追問(wèn)時(shí)至少不會(huì)出現(xiàn)方向性硬傷。8. 總結(jié)一點(diǎn)個(gè)人體會(huì)寫(xiě)排序算法這件事我最大的體會(huì)是它教會(huì)你的從來(lái)不只是“排序”而是遞歸、分治、復(fù)雜度分析、以及“把問(wèn)題分解成更小問(wèn)題”的思維方式。從直接插入到希爾從冒泡到快排從簡(jiǎn)單選擇到堆排序再到歸并排序你能清晰地看到一條不斷“往前提性能上限”的演進(jìn)路線(xiàn)用空間換時(shí)間歸并、用隨機(jī)化保證平均性能快排、用二叉樹(shù)結(jié)構(gòu)優(yōu)化選擇過(guò)程堆排序。我強(qiáng)烈建議你拿出一兩個(gè)小時(shí)把這七種排序全部手寫(xiě)一遍然后跑一遍我上面說(shuō)的測(cè)試數(shù)據(jù)集親眼看一看不同算法在不同數(shù)據(jù)下的表現(xiàn)差異。這個(gè)過(guò)程比看十篇博客都有用。另外一個(gè)小技巧在你寫(xiě)完某個(gè)排序后嘗試把你的實(shí)現(xiàn)和JDK的Arrays.sort做個(gè)對(duì)比然后問(wèn)自己三個(gè)問(wèn)題——我的實(shí)現(xiàn)能否處理極端輸入我的實(shí)現(xiàn)是否浪費(fèi)了空間我的實(shí)現(xiàn)能否在復(fù)雜度上壓住最壞情況這三個(gè)問(wèn)題每次都會(huì)讓你有所收獲。排序算法是很好的“分治思想的微型實(shí)驗(yàn)田”吃透了它們你再去看二叉樹(shù)遍歷、圖的最短路徑這些更復(fù)雜的問(wèn)題會(huì)覺(jué)得思路順暢很多。希望這篇內(nèi)容能幫你在排序這塊少踩點(diǎn)坑真正把這些算法變成你的肌肉記憶。