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