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