1. 從“排序”說起為什么我們還在討論這些“老古董”算法在面試?yán)锉粏柕健笆謱懸粋€(gè)快排”或者在代碼評審時(shí)看到同事用了冒泡排序你心里是不是會嘀咕這都什么年代了Java里Arrays.sort()、Collections.sort()那么好用為什么還要關(guān)心這些底層實(shí)現(xiàn)我剛開始工作那會兒也這么想直到有一次處理一個(gè)需要自定義比較邏輯、且對內(nèi)存和穩(wěn)定性有特殊要求的超大對象數(shù)組時(shí)直接調(diào)用庫函數(shù)要么性能不達(dá)標(biāo)要么根本沒法滿足需求。那一刻我才明白理解這些“基于比較的排序算法”的里子不是為了炫技而是為了在關(guān)鍵時(shí)刻你能清楚地知道手里的工具為什么快、為什么慢、以及什么時(shí)候該換哪把“扳手”。排序本質(zhì)上就是讓一堆雜亂無章的數(shù)據(jù)按照某種規(guī)則比如數(shù)字大小、字典序重新排列整齊。基于比較的排序是所有排序思想的基石它的核心動作就是反復(fù)問“元素A和元素B誰應(yīng)該排在前面”我們今天要聊的冒泡、插入、堆、歸并、快速這五種算法就是回答這個(gè)問題的五種經(jīng)典“策略”。它們各有各的脾氣和適用場景沒有絕對的“最好”只有“最合適”。接下來我不只是給你看Java代碼更重要的是拆解每種策略背后的“作戰(zhàn)思路”以及我在實(shí)際編碼和調(diào)優(yōu)中踩過的那些坑。2. 排序算法的“體檢報(bào)告”理解核心評價(jià)維度在深入每個(gè)算法之前我們必須統(tǒng)一“度量衡”。評價(jià)一個(gè)排序算法不能光說“它快”得看它在什么情況下快以及為此付出了什么代價(jià)。主要看三個(gè)硬指標(biāo)和一個(gè)軟指標(biāo)。2.1 時(shí)間復(fù)雜度算法速度的“理論標(biāo)尺”時(shí)間復(fù)雜度描述的是算法執(zhí)行時(shí)間隨數(shù)據(jù)量增長的趨勢。我們通常關(guān)注最壞情況、平均情況和最好情況。O(n2)像冒泡、插入排序當(dāng)數(shù)據(jù)是逆序最壞情況時(shí)需要進(jìn)行的比較和交換次數(shù)與數(shù)據(jù)量的平方成正比。這意味著數(shù)據(jù)量翻倍時(shí)間可能變?yōu)樵瓉淼乃谋丁τ诖笠?guī)模數(shù)據(jù)這是災(zāi)難性的。O(n log n)像堆、歸并、快速排序平均情況。這個(gè)效率就高多了數(shù)據(jù)量翻倍時(shí)間大概只增加一倍多一點(diǎn)。這是基于比較的排序算法理論上能達(dá)到的“天花板”效率。O(n)在最好情況下某些算法可能達(dá)到。比如插入排序?qū)缀跻呀?jīng)有序的數(shù)據(jù)排序會非常快。2.2 空間復(fù)雜度算法對內(nèi)存的“占用情況”空間復(fù)雜度描述的是算法運(yùn)行所需額外內(nèi)存空間隨數(shù)據(jù)量增長的趨勢。O(1)原地排序。算法只用到常數(shù)級別的額外空間幾個(gè)臨時(shí)變量。冒泡、插入、堆、快速排序大部分實(shí)現(xiàn)都屬于此類對內(nèi)存友好。O(n)非原地排序。算法需要額外開辟一個(gè)和待排序數(shù)據(jù)同樣大小的空間。歸并排序是典型代表它需要額外的數(shù)組來合并有序序列。2.3 穩(wěn)定性相等元素的“原始秩序”是否保留這是一個(gè)容易被忽略但至關(guān)重要的特性。如果待排序序列中存在兩個(gè)相等的元素A和B且在原始序列中A在B之前。排序后如果A仍然在B之前那么這個(gè)排序算法就是穩(wěn)定的否則是不穩(wěn)定的。為什么重要想象一下你對一個(gè)學(xué)生列表先按成績排序再按班級排序。如果第二次排序是穩(wěn)定的那么同班級的學(xué)生其成績高的依然會排在前面。如果是不穩(wěn)定的同班級內(nèi)的成績順序就可能被打亂。冒泡、插入、歸并是穩(wěn)定的堆排序和快速排序常見實(shí)現(xiàn)是不穩(wěn)定的。2.4 實(shí)際性能的“隱形因素”常數(shù)項(xiàng)與局部性原理理論復(fù)雜度一樣實(shí)際速度可能天差地別。這是因?yàn)槌?shù)項(xiàng)時(shí)間復(fù)雜度忽略的系數(shù)和低階項(xiàng)。例如雖然都是O(n log n)但快速排序的常數(shù)項(xiàng)通常比堆排序小所以實(shí)踐中更快。局部性原理現(xiàn)代CPU有高速緩存順序訪問內(nèi)存如插入排序比隨機(jī)訪問如快速排序在特定情況下的表現(xiàn)要快得多。這能極大影響實(shí)際性能。有了這份“體檢報(bào)告”我們就能帶著標(biāo)準(zhǔn)去審視每一個(gè)算法了。3. 算法深潛原理、實(shí)現(xiàn)與實(shí)戰(zhàn)陷阱3.1 冒泡排序直觀但低效的“啟蒙老師”核心思想像水底的氣泡一樣每一輪遍歷將當(dāng)前未排序部分中最大或最小的元素“浮”到正確位置。作戰(zhàn)思路進(jìn)行 n-1 輪循環(huán)。每輪內(nèi)從開始位置依次比較相鄰元素如果順序不對就交換。這樣第一輪后最大的元素到了末尾第二輪后次大的元素到了倒數(shù)第二……Java實(shí)現(xiàn)與逐行解析public class BubbleSort { public static void bubbleSort(int[] arr) { if (arr null || arr.length 2) { return; // 邊界條件處理數(shù)組為空或只有一個(gè)元素?zé)o需排序 } int n arr.length; // 外層循環(huán)控制排序的輪數(shù)最多需要n-1輪 for (int i 0; i n - 1; i) { // 一個(gè)優(yōu)化標(biāo)志如果某一輪沒有發(fā)生交換說明已經(jīng)有序可提前結(jié)束 boolean swapped false; // 內(nèi)層循環(huán)進(jìn)行相鄰比較。注意邊界是 n-1-i因?yàn)槟┪瞚個(gè)元素已就位 for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { // 如果前一個(gè)比后一個(gè)大則交換 // 交換 arr[j] 和 arr[j1] int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; swapped true; // 發(fā)生了交換 } } // 如果這一輪沒有交換提前跳出循環(huán) if (!swapped) { break; } } } }實(shí)戰(zhàn)陷阱與心得“優(yōu)化”的錯(cuò)覺雖然加了swapped標(biāo)志位優(yōu)化最好情況完全有序時(shí)復(fù)雜度為O(n)但這改變不了其平均和最壞情況下O(n2)的本質(zhì)。絕對不要在生產(chǎn)環(huán)境對任何有一定規(guī)模的數(shù)據(jù)使用冒泡排序。它的價(jià)值僅在于教學(xué)幫助理解排序和交換的基本概念。邊界條件內(nèi)循環(huán)的邊界j n - 1 - i是關(guān)鍵寫錯(cuò)會導(dǎo)致數(shù)組越界或無意義的比較。3.2 插入排序小規(guī)模與部分有序數(shù)據(jù)的“利器”核心思想模仿打撲克牌時(shí)整理手牌的過程。將數(shù)組分為“已排序”和“未排序”兩部分逐個(gè)將“未排序”部分的元素插入到“已排序”部分的正確位置。作戰(zhàn)思路從第二個(gè)元素開始第一個(gè)元素視為已排序?qū)⑵渑c前面已排序的元素從后往前比較找到合適位置插入。這個(gè)過程需要移動元素。Java實(shí)現(xiàn)與逐行解析public class InsertionSort { public static void insertionSort(int[] arr) { if (arr null || arr.length 2) { return; } int n arr.length; // 從第二個(gè)元素開始下標(biāo)1認(rèn)為第一個(gè)元素下標(biāo)0自己是有序的 for (int i 1; i n; i) { int current arr[i]; // 當(dāng)前待插入的元素 int j i - 1; // 從當(dāng)前元素的前一個(gè)位置開始比較 // 尋找current的插入位置將比current大的元素都向后挪一位 while (j 0 arr[j] current) { arr[j 1] arr[j]; // 數(shù)據(jù)后移 j--; } // 循環(huán)結(jié)束j1 就是current應(yīng)該插入的位置 arr[j 1] current; } } }實(shí)戰(zhàn)陷阱與心得適用場景之王當(dāng)數(shù)據(jù)量很小比如n50或者數(shù)據(jù)“幾乎已經(jīng)有序”時(shí)插入排序的效率非常高甚至優(yōu)于一些O(n log n)的算法。Java中Arrays.sort()對于對象數(shù)組的排序在遞歸到小數(shù)組時(shí)就采用了類似插入排序的算法TimSort中的二分插入排序。移動而非交換注意核心操作是arr[j 1] arr[j]移動而不是交換。最后一步arr[j 1] current才是插入。這比冒泡的頻繁交換要高效。穩(wěn)定性的來源因?yàn)槭菑暮笸氨容^遇到相等的元素(arr[j] current)時(shí)會停止移動所以相等元素的相對位置不變是穩(wěn)定排序。3.3 堆排序利用“二叉堆”的原地排序核心思想先把數(shù)組構(gòu)造成一個(gè)“大頂堆”每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值此時(shí)堆頂就是最大值。將堆頂與堆末尾元素交換最大值就位。然后將剩余元素重新調(diào)整成大頂堆重復(fù)此過程。作戰(zhàn)思路分為兩大步1. 建堆。2. 反復(fù)取堆頂元素并調(diào)整堆。Java實(shí)現(xiàn)與逐行解析public class HeapSort { public static void heapSort(int[] arr) { if (arr null || arr.length 2) { return; } int n arr.length; // 1. 構(gòu)建初始大頂堆。從最后一個(gè)非葉子節(jié)點(diǎn)開始向上調(diào)整 // 最后一個(gè)非葉子節(jié)點(diǎn)的下標(biāo)是 n/2 - 1 for (int i n / 2 - 1; i 0; i--) { heapify(arr, n, i); } // 2. 逐個(gè)提取堆頂元素最大值 for (int i n - 1; i 0; i--) { // 將當(dāng)前堆頂最大值arr[0] 與末尾元素 arr[i] 交換 int temp arr[0]; arr[0] arr[i]; arr[i] temp; // 交換后堆的大小減1i并對新的堆頂進(jìn)行下沉調(diào)整重新滿足堆性質(zhì) heapify(arr, i, 0); } } /** * 堆調(diào)整函數(shù)下沉操作 * param arr 待調(diào)整的數(shù)組堆 * param n 堆的當(dāng)前有效大小 * param i 待調(diào)整的節(jié)點(diǎn)下標(biāo) */ private static void heapify(int[] arr, int n, int i) { int largest i; // 初始化最大值為當(dāng)前節(jié)點(diǎn) int left 2 * i 1; // 左子節(jié)點(diǎn)下標(biāo) int right 2 * i 2; // 右子節(jié)點(diǎn)下標(biāo) // 找出當(dāng)前節(jié)點(diǎn)、左子節(jié)點(diǎn)、右子節(jié)點(diǎn)三者中的最大值 if (left n arr[left] arr[largest]) { largest left; } if (right n arr[right] arr[largest]) { largest right; } // 如果最大值不是當(dāng)前節(jié)點(diǎn)則需要交換并繼續(xù)向下調(diào)整 if (largest ! i) { int swap arr[i]; arr[i] arr[largest]; arr[largest] swap; // 遞歸調(diào)整受影響的子樹 heapify(arr, n, largest); } } }實(shí)戰(zhàn)陷阱與心得不穩(wěn)定的根源堆排序在交換堆頂和堆尾元素時(shí)可能把原本在前面的相等元素?fù)Q到后面去所以它是不穩(wěn)定排序。原地但緩存不友好堆排序是原地排序空間復(fù)雜度O(1)。但它的數(shù)據(jù)訪問模式是跳躍式的比較父節(jié)點(diǎn)和子節(jié)點(diǎn)對CPU緩存不友好因此常數(shù)項(xiàng)較大。雖然時(shí)間復(fù)雜度穩(wěn)定為O(n log n)但實(shí)際運(yùn)行速度通常不如快速排序和歸并排序。heapify的起點(diǎn)建堆時(shí)從n/2 -1開始是因?yàn)檫@些節(jié)點(diǎn)是有子節(jié)點(diǎn)的需要向下調(diào)整。葉子節(jié)點(diǎn)本身可以看作是一個(gè)合法的堆。3.4 歸并排序穩(wěn)定高效的“分治典范”核心思想經(jīng)典的分治策略。把數(shù)組遞歸地分成兩半分別對左右兩半排序然后將兩個(gè)有序的子數(shù)組合并成一個(gè)大的有序數(shù)組。作戰(zhàn)思路先“分”到最小單元單個(gè)元素自然有序再“治”合并。Java實(shí)現(xiàn)與逐行解析public class MergeSort { public static void mergeSort(int[] arr) { if (arr null || arr.length 2) { return; } int[] temp new int[arr.length]; // 一次性分配臨時(shí)數(shù)組避免遞歸中反復(fù)創(chuàng)建 mergeSort(arr, 0, arr.length - 1, temp); } private static void mergeSort(int[] arr, int left, int right, int[] temp) { if (left right) { return; // 遞歸基子數(shù)組只有一個(gè)元素或?yàn)榭?} int mid left (right - left) / 2; // 防止溢出的取中寫法 // 分治遞歸 mergeSort(arr, left, mid, temp); mergeSort(arr, mid 1, right, temp); // 合并兩個(gè)有序子數(shù)組 [left, mid] 和 [mid1, right] merge(arr, left, mid, right, temp); } private static void merge(int[] arr, int left, int mid, int right, int[] temp) { int i left; // 左子數(shù)組起始指針 int j mid 1; // 右子數(shù)組起始指針 int t 0; // 臨時(shí)數(shù)組指針 // 1. 比較并填充臨時(shí)數(shù)組 while (i mid j right) { if (arr[i] arr[j]) { // 注意這里是 保證了穩(wěn)定性 temp[t] arr[i]; } else { temp[t] arr[j]; } } // 2. 將剩余元素拷貝到臨時(shí)數(shù)組 while (i mid) { temp[t] arr[i]; } while (j right) { temp[t] arr[j]; } // 3. 將臨時(shí)數(shù)組的數(shù)據(jù)拷貝回原數(shù)組 t 0; while (left right) { arr[left] temp[t]; } } }實(shí)戰(zhàn)陷阱與心得穩(wěn)定性的關(guān)鍵在merge函數(shù)的比較中使用arr[i] arr[j]當(dāng)相等時(shí)優(yōu)先取左子數(shù)組的元素這保證了相等元素的原始順序使歸并排序成為穩(wěn)定的排序。空間開銷需要O(n)的額外空間。這是它最大的缺點(diǎn)。在內(nèi)存極其受限的環(huán)境如嵌入式需慎用。但正因?yàn)橛羞@塊連續(xù)額外空間合并過程非常高效。性能穩(wěn)定時(shí)間復(fù)雜度嚴(yán)格為O(n log n)沒有最壞情況退化的問題。對于鏈表排序歸并排序是天然的最佳選擇因?yàn)殒湵砗喜⒉恍枰~外空間。3.5 快速排序平均最快的“實(shí)戰(zhàn)王者”核心思想也是分治但策略更激進(jìn)。選擇一個(gè)“基準(zhǔn)”元素將數(shù)組劃分為三部分小于基準(zhǔn)、等于基準(zhǔn)、大于基準(zhǔn)。然后遞歸地對小于和大于的部分進(jìn)行排序。作戰(zhàn)思路核心是partition劃分操作。有多種實(shí)現(xiàn)方式如Lomuto, Hoare這里展示經(jīng)典的Hoare分區(qū)法變種。Java實(shí)現(xiàn)與逐行解析public class QuickSort { public static void quickSort(int[] arr) { if (arr null || arr.length 2) { return; } quickSort(arr, 0, arr.length - 1); } private static void quickSort(int[] arr, int low, int high) { if (low high) { // partitionIndex 是分區(qū)操作后基準(zhǔn)元素所處的正確位置 int partitionIndex partition(arr, low, high); // 遞歸排序基準(zhǔn)左側(cè)和右側(cè)的子數(shù)組 quickSort(arr, low, partitionIndex - 1); quickSort(arr, partitionIndex 1, high); } } private static int partition(int[] arr, int low, int high) { // 選取基準(zhǔn)值。這里簡單取中間元素有助于避免最壞情況。 // 更工程化的做法是“三數(shù)取中”或隨機(jī)選取。 int pivot arr[low (high - low) / 2]; int i low - 1; // 小于基準(zhǔn)的區(qū)域的右邊界 int j high 1; // 大于基準(zhǔn)的區(qū)域的左邊界 while (true) { // 從左向右找到第一個(gè)大于等于pivot的元素 do { i; } while (arr[i] pivot); // 從右向左找到第一個(gè)小于等于pivot的元素 do { j--; } while (arr[j] pivot); // 如果指針相遇或交叉說明劃分完成 if (i j) { return j; // 返回右子數(shù)組的起始邊界前一位 } // 交換這兩個(gè)錯(cuò)位的元素 int temp arr[i]; arr[i] arr[j]; arr[j] temp; // 交換后arr[i] pivot, arr[j] pivot循環(huán)繼續(xù) } } }實(shí)戰(zhàn)陷阱與心得基準(zhǔn)pivot的選擇是命門如果每次選的基準(zhǔn)都是最大或最小值比如對已經(jīng)有序的數(shù)組選第一個(gè)元素作基準(zhǔn)會導(dǎo)致劃分極度不平衡遞歸樹退化成鏈表時(shí)間復(fù)雜度惡化到O(n2)。工程上必須優(yōu)化常用“三數(shù)取中”取頭、中、尾三個(gè)元素的中位數(shù)或隨機(jī)選擇來避免最壞情況。不穩(wěn)定的根源在partition的交換過程中相等元素可能被交換到另一邊破壞穩(wěn)定性。遞歸深度與棧溢出最壞情況下遞歸深度為n可能引發(fā)棧溢出。工業(yè)級實(shí)現(xiàn)會采用“尾遞歸優(yōu)化”或“混合排序”當(dāng)子數(shù)組較小時(shí)切換為插入排序。為何是“平均”王者盡管有最壞情況O(n2)但通過好的基準(zhǔn)選擇策略其平均情況下的常數(shù)項(xiàng)非常小且內(nèi)存訪問模式相對友好使得在絕大多數(shù)實(shí)際場景中它是基于比較的內(nèi)部排序算法里最快的。4. 同臺競技綜合對比與選型指南光看理論不夠我們拉個(gè)表格并結(jié)合場景說說怎么選特性冒泡排序插入排序堆排序歸并排序快速排序平均時(shí)間復(fù)雜度O(n2)O(n2)O(n log n)O(n log n)O(n log n)最壞時(shí)間復(fù)雜度O(n2)O(n2)O(n log n)O(n log n)O(n2)空間復(fù)雜度O(1)O(1)O(1)O(n)O(log n) ~ O(n)穩(wěn)定性穩(wěn)定穩(wěn)定不穩(wěn)定穩(wěn)定不穩(wěn)定原地排序是是是否是選型決策樹數(shù)據(jù)量很小n 50或基本有序無腦用插入排序。簡單且效率高。需要穩(wěn)定排序且不在乎O(n)額外空間選擇歸并排序。它是穩(wěn)定排序中平均性能最好的。對穩(wěn)定性沒要求追求平均速度最快且數(shù)據(jù)是隨機(jī)分布的選擇快速排序務(wù)必做好基準(zhǔn)選擇優(yōu)化。對穩(wěn)定性沒要求且需要嚴(yán)格O(n log n)最壞時(shí)間復(fù)雜度保證同時(shí)內(nèi)存緊張選擇堆排序。比如在一些實(shí)時(shí)系統(tǒng)或內(nèi)存受限的嵌入式環(huán)境。鏈表排序選擇歸并排序。鏈表版的歸并排序可以達(dá)到O(1)的額外空間。絕對不要用冒泡排序除了教學(xué)。注意Java標(biāo)準(zhǔn)庫Arrays.sort()對基本類型數(shù)組int, double等使用了雙軸快速排序的變種因?yàn)樗恍枰€(wěn)定性而對對象數(shù)組Object[]使用了TimSort一種歸并排序和插入排序的混合體因?yàn)樗枰€(wěn)定性。這本身就是一種最佳的工程實(shí)踐示范。5. 超越比較當(dāng)排序遇上真實(shí)世界的數(shù)據(jù)理解了算法本身我們還得看看它們怎么應(yīng)對真實(shí)世界的挑戰(zhàn)。5.1 面對海量數(shù)據(jù)外部排序與歸并思想的延伸當(dāng)數(shù)據(jù)大到內(nèi)存裝不下時(shí)上述所有內(nèi)部排序算法都失效了。這時(shí)需要外部排序核心思想是“歸并排序”的擴(kuò)展分段將大數(shù)據(jù)文件分割成能裝入內(nèi)存的小塊。內(nèi)部排序?qū)γ總€(gè)小塊在內(nèi)存中用快排等算法排序并寫回臨時(shí)文件。多路歸并使用一個(gè)最小堆又是堆來高效地從多個(gè)有序臨時(shí)文件中歸并出最終結(jié)果。 這個(gè)過程深刻體現(xiàn)了基礎(chǔ)算法作為“基石”的價(jià)值復(fù)雜的系統(tǒng)往往由簡單的模塊組合而成。5.2 排序不止于數(shù)字對象排序與Comparator/Comparable實(shí)際工作中我們排序的往往是復(fù)雜的對象如用戶、訂單。在Java中這通過Comparable定義自然順序或Comparator定義比較器接口實(shí)現(xiàn)。所有排序算法的比較操作arr[i] arr[j]在這里都替換為comparator.compare(obj1, obj2) 0。一個(gè)坑必須確保比較邏輯滿足自反性、對稱性和傳遞性否則可能導(dǎo)致排序結(jié)果異常甚至拋出異常。例如比較器里不要寫return o1.hashCode() - o2.hashCode();因?yàn)楣４a相減可能溢出。5.3 性能測試的“陷阱”JVM熱身與基準(zhǔn)測試自己寫代碼比較算法性能時(shí)直接跑一次就下結(jié)論是草率的。因?yàn)镴VM有JIT即時(shí)編譯優(yōu)化需要“熱身”。務(wù)必使用像JMH這樣的微基準(zhǔn)測試框架它幫你處理了熱身、循環(huán)、消除死代碼優(yōu)化等問題結(jié)果才可靠。否則你可能會發(fā)現(xiàn)插入排序在小數(shù)據(jù)量下“跑得比快排還快”這可能是測試方法的問題而非算法本身的問題。紙上得來終覺淺絕知此事要躬行。這些算法不僅僅是面試題它們的核心思想——分治、減治、利用數(shù)據(jù)結(jié)構(gòu)優(yōu)化——滲透在編程的方方面面。下次當(dāng)你需要維護(hù)一段排序相關(guān)的代碼或者設(shè)計(jì)一個(gè)需要高效組織數(shù)據(jù)的模塊時(shí)希望這些深入骨髓的理解能幫你做出更優(yōu)雅、更高效的選擇。畢竟真正的高手不是背熟了所有算法的代碼而是深刻理解了每一種策略背后的權(quán)衡從而在面臨具體問題時(shí)能云淡風(fēng)輕地選出最合適的那一把“手術(shù)刀”。