排序算法是数据结构课里那块最“硬”的骨头也是各大厂笔试面试中出场率极高的常客。这次梳理的是Java视角下的七大排序算法也就是直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序和归并排序。无论你是正在准备校招的应届生还是在公司里做业务开发时偶尔需要手写一段排序逻辑或者纯粹想把这些经典算法吃透这篇内容都能给你一个完整、可直接参考的脉络。我会把每种算法的核心思想、Java实现、复杂度推导以及只有在真正写代码时才会遇到的那些坑全都摊开来讲。这篇内容不是单纯的代码堆砌我会按照“家族”把它们分组插入排序家族、交换排序家族、选择排序家族再加上归并排序这个“分治王者”这样分类的好处是你能从设计思路上去理解而不是死记硬背代码。每一类我都会给出完整的Java代码并且标注清楚哪些地方容易写错哪些细节是面试官特别喜欢追问的。我还会分享一些在实际工程项目里筛选排序方案的经验比如面对几万条数据时该无脑选哪种、什么时候别手写排序而应该直接调JDK自带的方法。1. 七大排序全景透视复杂度与场景选型先把七种算法放到一张表里看全貌。这张表是你复习和面试前必须刻在脑子里的东西它决定了你在不同场景下第一时间该掏出哪种排序。排序算法平均时间复杂度最坏时间复杂度最好时间复杂度空间复杂度稳定性直接插入排序O(n²)O(n²)O(n)O(1)稳定希尔排序O(n^1.3~1.5)O(n²)O(n)O(1)不稳定冒泡排序O(n²)O(n²)O(n)O(1)稳定快速排序O(nlogn)O(n²)O(nlogn)O(logn)~O(n)不稳定简单选择排序O(n²)O(n²)O(n²)O(1)不稳定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定读这张表有个规律希望你能记下来大多数“不稳定”的排序算法问题都出在“跳跃式交换元素”这个动作上。比如希尔排序是跳着组内比较交换快速排序是基准值左右跳跃式交换简单选择排序是每轮把最小的元素直接甩到前面堆排序更是隔着整个堆在交换。反而是那些只在相邻元素之间“小步挪动”的算法——插入排序、冒泡排序、归并排序——天然就能保证稳定性。稳定性这个词很多初学者觉得无所谓但我举个例子你就明白了。假设你要给一个班级的学生表排序先按年龄排好序再按姓名排序如果排序算法不稳定第二次按姓名排序时年龄相同的学生顺序可能就乱了你前面按年龄排的顺序等于白做了。实际系统里这种情况太常见了先按主键排序再按副键排序稳定的排序算法能保证两次排序结果可叠加。选型的逻辑我一般看三个指标数据量大小、数据初始有序程度、是否要求稳定。数据量很小比如50个以内直接插入排序几乎无敌因为常数极小没有额外空间消耗。数据量中等几千到几万快速排序是最优选平均性能最强但要注意最坏退化问题。数据量超大百万级以上且要求最坏时间复杂度可控归并排序或堆排序更稳。要求稳定且数据量不小归并排序是你的唯一选择Java的Collections.sort底层也是这个思路。几乎有序的数据插入排序的最好情况O(n)优势就体现出来了很多商用的混合排序会用它来收尾。2. 插入排序家族直接插入与希尔2.1 直接插入排序像整理手牌一样简单如果你打扑克牌时习惯把摸到的新牌插入到手里已经排好序的牌堆中那你已经懂了直接插入排序的核心思想。把数组看成两部分左边是已排序区右边是待排序区每次从待排序区拿出第一个数把它往左插到合适位置。Java实现如下public static void insertSort(int[] arr) { if (arr null || arr.length 2) return; // 默认arr[0]是已排序区从arr[1]开始依次处理 for (int i 1; i arr.length; i) { int current arr[i]; // 待插入的数 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;。很多初学者搞不清为什么是j1而不是j因为while循环退出时有两种情况要么j已经小于0了说明current应该放在数组最前面要么arr[j]已经不大于current了说明current应该插在arr[j]的后面。不管是哪种正确的位置都是索引j1。复杂度这块最坏和平均都是O(n²)——你每次插入都要把前面一大片元素往后挪。但最好情况很讨喜如果数据本来就是有序的while循环一次都不进外层循环扫一遍就结束时间复杂度直接降到O(n)。所以它特别适合那种“基本有序”的数据。2.2 希尔排序给插入排序装上“涡轮增压”希尔排序是直接插入排序的改进版思路非常聪明先让数据整体变得“基本有序”再去做最后一次直接插入排序。怎么让数据基本有序答案是对数组进行分组组内排序。关键点是分组的方式不是简单的连续分块而是“按间隔取元素”分组。假设数组长度是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; // 初始间隔取数组长度的一半以后每轮砍半 for (int gap n / 2; gap 0; gap / 2) { // 从gap开始逐个对“逻辑分组”做插入排序 for (int i gap; i n; i) { int current arr[i]; int j i; // 组内做插入排序比较时跨越gap距离 while (j - gap 0 arr[j - gap] current) { arr[j] arr[j - gap]; j - gap; } arr[j] current; } } }注意这里的双层循环变成了三层嵌套初看容易晕但你可以这样理解i从gap扫到n-1每次处理时它都是在处理某个分组里的“下一个元素”内层while负责在当前分组里往前插入。这个写法比起先按组循环再组内排序代码更简洁但理解难度稍高。关于间隔序列经典的“每次除以2”不是最优的目前比较常用的是Sedgewick序列比如1、5、19、41、109……这种序列能达到O(n^1.3)级别的时间复杂度。我在实际项目里除非数据特征特别明确一般不会手写希尔排序但在算法题里偶尔有奇效尤其是某些对空间要求苛刻的场景。2.3 为什么希尔排序不稳定希尔排序的不稳定性是个经典面试点。原因是分组排序时两个数值相等的元素可能因为分组的不同而被拆散后面某个组内交换时让原本靠前的那个元素跑到后面去了。举个具体例子数组[2, 1, 2]gap1时直接插入排序没问题但如果gap2分组下标0和下标2这两个“2”被分到同一组组内排序时如果发生交换两个2的相对位置就可能颠倒。这种跨越间隔的移动是破坏稳定性的元凶。3. 交换排序家族冒泡与快速3.1 冒泡排序教学常客工程弃儿冒泡排序的思路就是“大的往下沉小的往上浮”。每轮从头开始两两比较相邻元素如果顺序反了就交换一轮下来最大的数被“冒泡”到了最后。重复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; } } // 如果某一轮没有任何交换说明已经有序直接结束 if (!swapped) break; } }我加了一个swapped标志位这是冒泡排序最重要的优化——数据本来就有序时第一轮结束就能提前退出时间复杂度降到O(n)。还有一个优化思路是记录最后一次发生交换的位置这个位置之后的数据已经排好了下一轮就不需要再遍历到末尾。但说句大实话冒泡排序在实际工程里几乎不会被用到哪怕是几百条数据处理直接插入排序都比它快得多因为它要做的交换次数太多了。它存在的最大意义就是当作教学案例让你理解最朴素的交换排序思想。3.2 快速排序最常用的“分治王者”快排的核心思想是分治随便挑一个数当基准值pivot通过一次遍历把数组分成两拨比pivot小的放左边、大的放右边然后对左右两拨分别递归做同样的事最终整个数组有序。快速排序的实现版本很多写法差异很大我分享一个我用了很多年的经典写法它叫“挖坑法”比较容易理解也不会写错public static void quickSort(int[] arr, int left, int right) { if (left right) return; // 三数取中优化下面单独讲 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; }这个写法里有两个隐藏很深的坑。第一个坑是为什么内层循环必须先从右往左走因为你把基准值放在了最左边相当于左边“挖了个坑”你需要先从右边找一个比基准值小的数来填左边的坑。如果先从左往右找左边第一个元素可能就直接把坑越过了逻辑会乱。第二个坑是内层while里的条件必须是和不能写成和。如果用严格大于或小于遇到和基准值相等的元素时i和j都可能卡住不动导致死循环或者无限递归。关于三数取中的优化我简单解释一下为什么需要它。快排最怕的是每次选基准值都选到最大值或最小值那样分区极不平衡递归深度达到n层时间复杂度退化成O(n²)。取数组左端、中间、右端三个数的中间值作为基准值可以在很大程度上避免这个问题尤其是对“已经有序”的数组效果立竿见影。还有一个工程上的优化细节当子数组长度比较小比如小于10时递归调用的开销占比很大很多版本的快排会切换到直接插入排序来收尾。JDK内部实现的排序就是这么干的大区间用快排思路小区间用插入排序整体性能能提升不少。3.3 快排的空间复杂度与稳定性快排的空间复杂度是O(logn)这里的空间不是指额外的数组而是递归调用栈的深度。理想情况下每次分区都均衡递归层数是logn最坏情况下每次都只拆出一个元素递归层数是n栈溢出风险很高。这也就是为什么面试官会追问“快排空间复杂度是多少”很多人会答O(1)这就错了——递归本身在消耗调用栈空间。快速排序不稳定原因在于它的交换是“跳跃式”的——基准值可能被直接换到很远的位置两个数值相同的元素的相对顺序在这个过程中可能被改变。所以如果业务上有稳定排序要求快排不能直接上。4. 选择排序家族简单选择与堆排序4.1 简单选择排序最直观但毫无“亮点”简单选择排序的思路比冒泡还直观第一轮从0到n-1里找到最小的数放到下标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; } } }这个算法的时间复杂度不管是最好、最坏还是平均都是O(n²)因为它每一轮都要完整扫描一遍剩余数组来找最小元素不能利用数据原本的有序性。它的交换次数很少每轮最多一次理论上比冒泡的交换成本低但比较次数一样多实际性能并不占优。简单选择排序的不稳定性值得拿出来专门讲。考虑数组 [5, 5, 1]第一轮找到最小元素1然后把它和下标0的5交换结果是 [1, 5, 5]。你会看到原来在前面的那个“5”被第一次交换到了数组末尾两个5的相对顺序颠倒了。这给我们的启示是凡是“把最值直接换到目标区”的排序都得小心稳定性问题。4.2 堆排序建堆、调整与朴素“堆”的误区堆排序的核心是“完全二叉树”和“大顶堆”。升序排序用大顶堆堆顶元素永远是整个堆的最大值每次把堆顶和当前未排序区域的最后一个元素交换堆顶的最大值就“滚”到数组末尾去了然后重新调整堆结构让新的堆顶继续成为剩余元素里的最大值。堆排序的两个关键步骤简称为“建堆”和“调整”。建堆的意思是从最后一个非叶子节点开始从下往上做堆化heapify调整的意思是把堆顶和末尾交换后从堆顶开始向下调整恢复大顶堆的性质。public static void heapSort(int[] arr) { if (arr null || arr.length 2) return; int n arr.length; // 建堆从最后一个非叶子节点开始向上调整 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); // 递归调整被换下去的子树 } }很多初学者会问为什么建堆的循环是从n/2 - 1开始而不是从n-1开始因为完全二叉树里下标n/2到n-1全部是叶子节点叶子节点没有孩子本身就已经满足堆的性质不需要调整。从最后一个非叶子节点开始倒序遍历每个节点最多和它的子树做一次交换时间复杂度是O(n)这里很多人有误解以为建堆要O(nlogn)实际上这样做是“每个节点调整一次”整体是O(n)。堆排序的特点是时间复杂度稳定在O(nlogn)而且空间复杂度O(1)是“原地排序”。但它在工程上的使用频率远低于快速排序原因有二一是它访问数组的方式是跳跃式的对CPU缓存极不友好实际运行常数很大二是它不稳定。不过在优先级队列和Top K这类问题上堆的结构本身而非堆排序反而是极其高效的。5. 归并排序分治思路与稳定性之王归并排序是七种排序里唯一一个既满足O(nlogn)最坏时间复杂度又稳定的排序算法。它的思路再清晰不过把一个数组分成两半分别把两半都排好序再合并两个有序序列成一个大的有序序列。整个过程用递归来实现先分到底再一层层“治”回去。public static void mergeSort(int[] arr) { if (arr null || arr.length 2) return; int[] temp new int[arr.length]; // 一次性创建辅助数组 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) { // 这里用 保证稳定性相等时先取左半部分 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]; // 把临时数组里的结果拷贝回原数组 for (int p left; p right; p) { arr[p] temp[p]; } }这段代码里有一个很关键的细节辅助数组temp应该只在mergeSort里创建一次而不是在每次递归merge时都new一个新数组。如果你在merge方法里每次new一个数组数组长度加起来是O(nlogn)频繁的内存分配和GC会让性能大幅下降。我见过不少同学在这上面栽跟头数据量一大就性能奇差无比还误以为是递归本身的问题。归并排序为什么稳定核心就在合并时的那个判断当左右两个子数组里出现相等的元素时我们规定先取左边那个。这样一来原本在数组里靠前的相等元素最终在合并后的结果里依然靠前稳定性就保住了。归并排序的时间和空间复杂度分别是O(nlogn)和O(n)。它在Java的JDK里使用极其广泛对对象数组的排序Arrays.sort(T[])底层用的就是TimSort本质上是归并排序的改进版本把插入排序和小规模归并结合了起来。原因很简单对象排序要求稳定。而Arrays.sort(int[])底层则用的双轴快排这是因为基本类型的排序不要求稳定性可以追求更快的平均速度。6. 七种排序横向对比与Java工程选型实战到了这一步七种排序算法我已经全部讲完了代码层面的实现。但作为从业者我心里很清楚一件事考完试、面完试之后真正决定你排序性能的不是哪段代码写得华丽而是你在具体场景下能不能选对方案。所以这一章我直接讲工程选型。真正的Java程序员在日常开发中新写排序逻辑的机会非常少因为JDK自带的Arrays.sort和Collections.sort已经足够优秀它们在内部根据数据类型和数据量自动切换排序策略。但理解它们的策略逻辑对写出高性能代码很有帮助。Arrays.sort(int[])在数据量小于47时采用插入排序大于47采用双轴快排Arrays.sort(Object[])则使用TimSort它会在数据接近有序时利用天然有序片段达到O(n)级别的效率。什么场景下我会选择手写排序而不是直接用JDK方法大概只有两种第一种是你面对的是自定义结构体且不想写比较器想通过一次排序完成某种特殊分组逻辑第二种是算法题环境中要求你实现某个特定排序来证明复杂度。除此之外请你务必使用JDK自带排序因为它做了极致的工程优化手写版本在大部分情况下性能是打不过它的。如果你确实需要自己封装一个排序工具类我给一个比较通用的“混合排序”模板思路数据规模数据特征推荐算法原因 50任意直接插入排序常数极小无额外空间代码简单50 ~ 100000大部分随机快速排序三数取中小区间插排平均性能最佳缓存友好 100000要求稳定性归并排序可迭代版避免递归栈溢出最坏复杂度有保证且稳定 100000要求原地排序堆排序空间O(1)时间复杂度稳定任意规模数据基本有序插入排序或TimSort思路接近O(n)利用有序性这个表格是我踩过不少坑之后总结出来的经验。一个很典型的坑是对100万级数据强行用简单选择排序——你觉得每轮只交换一次成本低但你忽略了每轮都要扫描接近整个数组的比较成本O(n²)的增长曲线在数据量翻倍时的代价是四倍的时间。另外多说一句排序稳定性对工程设计的实际影响。举个场景一个交易系统里你先把流水按交易金额排序再把相同金额的流水按时间排序。如果第二次排序用的是稳定排序那么相同金额的流水自然保持了时间上的先后顺序如果用了不稳定的排序同金额流水的时间顺序可能被打乱最终报表展示会有一种“不专业”的凌乱感。这就是很多底层库在排序对象数据时坚持用归并思想的原因。7. 排序算法避坑指南与实战测试心得这一章我把自己平时在写排序和调试排序时遇到最多的问题汇总一下很多坑只有真正实现过一遍才会懂。7.1 死循环与栈溢出的排查思路快速排序和归并排序的递归版本最容易出栈溢出。排查栈溢出时第一反应应该是递归终止条件是否在极端输入下永远不会触发。快排里最常见的死循环是分区后某一边长度等于原长度导致无限递归。比如基准值选到了最小值partition之后左边区间长度为0右边为n-1如果递归调用没有正确处理边界就可能陷入死循环。还有一个小细节递归版本在大数据量下容易栈溢出的可以考虑手写栈将递归转迭代。归并排序可以写成自底向上的迭代版本先两两合并再四四合并……快排可以用栈保存待处理区间。这个过程在面试中也常被考察你如果能现场把递归改成迭代会是一个加分项。7.2 用测试数据“拷问”排序算法写排序算法之后想要验证正确性不能只跑一两个从小到大排列的数组就收工。我建议至少构造这五类测试数据随机打乱的数据验证基本正确性完全逆序的数据比如 [n, n-1, ..., 1]考验最坏情况完全有序的数据考验最好情况与快速排序的退化问题包含大量重复元素的数据考验内层循环里相等值的处理极端边界空数组、只有一个元素的数组、两个元素的数组我测试时会写一个简单的校验方法先复制一份测试数据调用Arrays.sort排好再和我自己的排序结果逐位比较。这种自动校验比肉眼观察可靠得多。7.3 性能对比的“体感”数据这里分享一组我本地跑过的参考数据仅供参考不同机器差异很大1万个随机int插入排序和冒泡排序耗时在几十毫秒级别快排和归并在个位数毫秒级当数据量上升到10万级别O(n²)算法的耗时可能已经到秒级而O(nlogn)算法依然轻松。100万随机int手写快排大概几百毫秒而Arrays.sort优化过的双轴快排可能只有它的一半。这组数据的意义在于让你建立起“复杂度差距到底意味着什么”的直觉。很多人学算法时觉得O(n²)和O(nlogn)只是一个符号但当数据量达到百万级二者差距是几十倍到上百倍的体感差距这在生产环境里直接影响用户体验。7.4 我踩过的三个具体的“坑”第一个坑希尔排序的gap序列选择。有一阵我为了让代码看起来“高级”用了比较复杂的步长序列结果在小数据集上性能反而不如简单折半。后来我明白了步长序列优劣的差距在数据量很小时显现不出来而“可读性”和“可维护性”反而更值钱。第二个坑快速排序在数据完全有序时的退化。如果每次选第一个元素当基准值对[1, 2, 3, ..., 10000]这样的数组每轮分区都是极端不均衡的递归深度接近10000直接导致StackOverflowError。我改用了三数取中之后这个问题彻底消失。这个坑几乎每个手写快排的人都会踩到。第三个坑忘记更新循环边界条件。写归并排序的merge时如果最后把temp数组拷贝回原数组时循环边界写错比如从0开始而不是从left开始你会发现排序结果总是“部分有序、部分混乱”而且这种bug非常难通过小数据量样例发现因为刚好碰巧边界正确的情况经常发生。排查这类问题最有效的方式还是构造大随机数据做自动校验。7.5 一份可以保底自检的对照表面试考点常见误区正确的理解快排空间复杂度误答O(1)递归调用栈深度平均O(logn)最坏O(n)归并空间复杂度忽略辅助数组需要O(n)的临时数组空间堆排序时间复杂度以为建堆是O(nlogn)堆化过程是O(n)整体是O(nlogn)稳定性搞不清哪些稳定哪些不稳定插入、冒泡、归并稳定其余不稳定希尔排序不稳定以为分组内部插入排序是稳定跨组交换破坏了稳定性把这张表烂熟于心你在面试中应对排序部分的追问时至少不会出现方向性硬伤。8. 总结一点个人体会写排序算法这件事我最大的体会是它教会你的从来不只是“排序”而是递归、分治、复杂度分析、以及“把问题分解成更小问题”的思维方式。从直接插入到希尔从冒泡到快排从简单选择到堆排序再到归并排序你能清晰地看到一条不断“往前提性能上限”的演进路线用空间换时间归并、用随机化保证平均性能快排、用二叉树结构优化选择过程堆排序。我强烈建议你拿出一两个小时把这七种排序全部手写一遍然后跑一遍我上面说的测试数据集亲眼看一看不同算法在不同数据下的表现差异。这个过程比看十篇博客都有用。另外一个小技巧在你写完某个排序后尝试把你的实现和JDK的Arrays.sort做个对比然后问自己三个问题——我的实现能否处理极端输入我的实现是否浪费了空间我的实现能否在复杂度上压住最坏情况这三个问题每次都会让你有所收获。排序算法是很好的“分治思想的微型实验田”吃透了它们你再去看二叉树遍历、图的最短路径这些更复杂的问题会觉得思路顺畅很多。希望这篇内容能帮你在排序这块少踩点坑真正把这些算法变成你的肌肉记忆。 Java排序算法全详解：七大经典排序实现与工程选型
排序算法是数据结构课里那块最“硬”的骨头也是各大厂笔试面试中出场率极高的常客。这次梳理的是Java视角下的七大排序算法也就是直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序和归并排序。无论你是正在准备校招的应届生还是在公司里做业务开发时偶尔需要手写一段排序逻辑或者纯粹想把这些经典算法吃透这篇内容都能给你一个完整、可直接参考的脉络。我会把每种算法的核心思想、Java实现、复杂度推导以及只有在真正写代码时才会遇到的那些坑全都摊开来讲。这篇内容不是单纯的代码堆砌我会按照“家族”把它们分组插入排序家族、交换排序家族、选择排序家族再加上归并排序这个“分治王者”这样分类的好处是你能从设计思路上去理解而不是死记硬背代码。每一类我都会给出完整的Java代码并且标注清楚哪些地方容易写错哪些细节是面试官特别喜欢追问的。我还会分享一些在实际工程项目里筛选排序方案的经验比如面对几万条数据时该无脑选哪种、什么时候别手写排序而应该直接调JDK自带的方法。1. 七大排序全景透视复杂度与场景选型先把七种算法放到一张表里看全貌。这张表是你复习和面试前必须刻在脑子里的东西它决定了你在不同场景下第一时间该掏出哪种排序。排序算法平均时间复杂度最坏时间复杂度最好时间复杂度空间复杂度稳定性直接插入排序O(n²)O(n²)O(n)O(1)稳定希尔排序O(n^1.3~1.5)O(n²)O(n)O(1)不稳定冒泡排序O(n²)O(n²)O(n)O(1)稳定快速排序O(nlogn)O(n²)O(nlogn)O(logn)~O(n)不稳定简单选择排序O(n²)O(n²)O(n²)O(1)不稳定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定读这张表有个规律希望你能记下来大多数“不稳定”的排序算法问题都出在“跳跃式交换元素”这个动作上。比如希尔排序是跳着组内比较交换快速排序是基准值左右跳跃式交换简单选择排序是每轮把最小的元素直接甩到前面堆排序更是隔着整个堆在交换。反而是那些只在相邻元素之间“小步挪动”的算法——插入排序、冒泡排序、归并排序——天然就能保证稳定性。稳定性这个词很多初学者觉得无所谓但我举个例子你就明白了。假设你要给一个班级的学生表排序先按年龄排好序再按姓名排序如果排序算法不稳定第二次按姓名排序时年龄相同的学生顺序可能就乱了你前面按年龄排的顺序等于白做了。实际系统里这种情况太常见了先按主键排序再按副键排序稳定的排序算法能保证两次排序结果可叠加。选型的逻辑我一般看三个指标数据量大小、数据初始有序程度、是否要求稳定。数据量很小比如50个以内直接插入排序几乎无敌因为常数极小没有额外空间消耗。数据量中等几千到几万快速排序是最优选平均性能最强但要注意最坏退化问题。数据量超大百万级以上且要求最坏时间复杂度可控归并排序或堆排序更稳。要求稳定且数据量不小归并排序是你的唯一选择Java的Collections.sort底层也是这个思路。几乎有序的数据插入排序的最好情况O(n)优势就体现出来了很多商用的混合排序会用它来收尾。2. 插入排序家族直接插入与希尔2.1 直接插入排序像整理手牌一样简单如果你打扑克牌时习惯把摸到的新牌插入到手里已经排好序的牌堆中那你已经懂了直接插入排序的核心思想。把数组看成两部分左边是已排序区右边是待排序区每次从待排序区拿出第一个数把它往左插到合适位置。Java实现如下public static void insertSort(int[] arr) { if (arr null || arr.length 2) return; // 默认arr[0]是已排序区从arr[1]开始依次处理 for (int i 1; i arr.length; i) { int current arr[i]; // 待插入的数 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;。很多初学者搞不清为什么是j1而不是j因为while循环退出时有两种情况要么j已经小于0了说明current应该放在数组最前面要么arr[j]已经不大于current了说明current应该插在arr[j]的后面。不管是哪种正确的位置都是索引j1。复杂度这块最坏和平均都是O(n²)——你每次插入都要把前面一大片元素往后挪。但最好情况很讨喜如果数据本来就是有序的while循环一次都不进外层循环扫一遍就结束时间复杂度直接降到O(n)。所以它特别适合那种“基本有序”的数据。2.2 希尔排序给插入排序装上“涡轮增压”希尔排序是直接插入排序的改进版思路非常聪明先让数据整体变得“基本有序”再去做最后一次直接插入排序。怎么让数据基本有序答案是对数组进行分组组内排序。关键点是分组的方式不是简单的连续分块而是“按间隔取元素”分组。假设数组长度是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; // 初始间隔取数组长度的一半以后每轮砍半 for (int gap n / 2; gap 0; gap / 2) { // 从gap开始逐个对“逻辑分组”做插入排序 for (int i gap; i n; i) { int current arr[i]; int j i; // 组内做插入排序比较时跨越gap距离 while (j - gap 0 arr[j - gap] current) { arr[j] arr[j - gap]; j - gap; } arr[j] current; } } }注意这里的双层循环变成了三层嵌套初看容易晕但你可以这样理解i从gap扫到n-1每次处理时它都是在处理某个分组里的“下一个元素”内层while负责在当前分组里往前插入。这个写法比起先按组循环再组内排序代码更简洁但理解难度稍高。关于间隔序列经典的“每次除以2”不是最优的目前比较常用的是Sedgewick序列比如1、5、19、41、109……这种序列能达到O(n^1.3)级别的时间复杂度。我在实际项目里除非数据特征特别明确一般不会手写希尔排序但在算法题里偶尔有奇效尤其是某些对空间要求苛刻的场景。2.3 为什么希尔排序不稳定希尔排序的不稳定性是个经典面试点。原因是分组排序时两个数值相等的元素可能因为分组的不同而被拆散后面某个组内交换时让原本靠前的那个元素跑到后面去了。举个具体例子数组[2, 1, 2]gap1时直接插入排序没问题但如果gap2分组下标0和下标2这两个“2”被分到同一组组内排序时如果发生交换两个2的相对位置就可能颠倒。这种跨越间隔的移动是破坏稳定性的元凶。3. 交换排序家族冒泡与快速3.1 冒泡排序教学常客工程弃儿冒泡排序的思路就是“大的往下沉小的往上浮”。每轮从头开始两两比较相邻元素如果顺序反了就交换一轮下来最大的数被“冒泡”到了最后。重复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; } } // 如果某一轮没有任何交换说明已经有序直接结束 if (!swapped) break; } }我加了一个swapped标志位这是冒泡排序最重要的优化——数据本来就有序时第一轮结束就能提前退出时间复杂度降到O(n)。还有一个优化思路是记录最后一次发生交换的位置这个位置之后的数据已经排好了下一轮就不需要再遍历到末尾。但说句大实话冒泡排序在实际工程里几乎不会被用到哪怕是几百条数据处理直接插入排序都比它快得多因为它要做的交换次数太多了。它存在的最大意义就是当作教学案例让你理解最朴素的交换排序思想。3.2 快速排序最常用的“分治王者”快排的核心思想是分治随便挑一个数当基准值pivot通过一次遍历把数组分成两拨比pivot小的放左边、大的放右边然后对左右两拨分别递归做同样的事最终整个数组有序。快速排序的实现版本很多写法差异很大我分享一个我用了很多年的经典写法它叫“挖坑法”比较容易理解也不会写错public static void quickSort(int[] arr, int left, int right) { if (left right) return; // 三数取中优化下面单独讲 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; }这个写法里有两个隐藏很深的坑。第一个坑是为什么内层循环必须先从右往左走因为你把基准值放在了最左边相当于左边“挖了个坑”你需要先从右边找一个比基准值小的数来填左边的坑。如果先从左往右找左边第一个元素可能就直接把坑越过了逻辑会乱。第二个坑是内层while里的条件必须是和不能写成和。如果用严格大于或小于遇到和基准值相等的元素时i和j都可能卡住不动导致死循环或者无限递归。关于三数取中的优化我简单解释一下为什么需要它。快排最怕的是每次选基准值都选到最大值或最小值那样分区极不平衡递归深度达到n层时间复杂度退化成O(n²)。取数组左端、中间、右端三个数的中间值作为基准值可以在很大程度上避免这个问题尤其是对“已经有序”的数组效果立竿见影。还有一个工程上的优化细节当子数组长度比较小比如小于10时递归调用的开销占比很大很多版本的快排会切换到直接插入排序来收尾。JDK内部实现的排序就是这么干的大区间用快排思路小区间用插入排序整体性能能提升不少。3.3 快排的空间复杂度与稳定性快排的空间复杂度是O(logn)这里的空间不是指额外的数组而是递归调用栈的深度。理想情况下每次分区都均衡递归层数是logn最坏情况下每次都只拆出一个元素递归层数是n栈溢出风险很高。这也就是为什么面试官会追问“快排空间复杂度是多少”很多人会答O(1)这就错了——递归本身在消耗调用栈空间。快速排序不稳定原因在于它的交换是“跳跃式”的——基准值可能被直接换到很远的位置两个数值相同的元素的相对顺序在这个过程中可能被改变。所以如果业务上有稳定排序要求快排不能直接上。4. 选择排序家族简单选择与堆排序4.1 简单选择排序最直观但毫无“亮点”简单选择排序的思路比冒泡还直观第一轮从0到n-1里找到最小的数放到下标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; } } }这个算法的时间复杂度不管是最好、最坏还是平均都是O(n²)因为它每一轮都要完整扫描一遍剩余数组来找最小元素不能利用数据原本的有序性。它的交换次数很少每轮最多一次理论上比冒泡的交换成本低但比较次数一样多实际性能并不占优。简单选择排序的不稳定性值得拿出来专门讲。考虑数组 [5, 5, 1]第一轮找到最小元素1然后把它和下标0的5交换结果是 [1, 5, 5]。你会看到原来在前面的那个“5”被第一次交换到了数组末尾两个5的相对顺序颠倒了。这给我们的启示是凡是“把最值直接换到目标区”的排序都得小心稳定性问题。4.2 堆排序建堆、调整与朴素“堆”的误区堆排序的核心是“完全二叉树”和“大顶堆”。升序排序用大顶堆堆顶元素永远是整个堆的最大值每次把堆顶和当前未排序区域的最后一个元素交换堆顶的最大值就“滚”到数组末尾去了然后重新调整堆结构让新的堆顶继续成为剩余元素里的最大值。堆排序的两个关键步骤简称为“建堆”和“调整”。建堆的意思是从最后一个非叶子节点开始从下往上做堆化heapify调整的意思是把堆顶和末尾交换后从堆顶开始向下调整恢复大顶堆的性质。public static void heapSort(int[] arr) { if (arr null || arr.length 2) return; int n arr.length; // 建堆从最后一个非叶子节点开始向上调整 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); // 递归调整被换下去的子树 } }很多初学者会问为什么建堆的循环是从n/2 - 1开始而不是从n-1开始因为完全二叉树里下标n/2到n-1全部是叶子节点叶子节点没有孩子本身就已经满足堆的性质不需要调整。从最后一个非叶子节点开始倒序遍历每个节点最多和它的子树做一次交换时间复杂度是O(n)这里很多人有误解以为建堆要O(nlogn)实际上这样做是“每个节点调整一次”整体是O(n)。堆排序的特点是时间复杂度稳定在O(nlogn)而且空间复杂度O(1)是“原地排序”。但它在工程上的使用频率远低于快速排序原因有二一是它访问数组的方式是跳跃式的对CPU缓存极不友好实际运行常数很大二是它不稳定。不过在优先级队列和Top K这类问题上堆的结构本身而非堆排序反而是极其高效的。5. 归并排序分治思路与稳定性之王归并排序是七种排序里唯一一个既满足O(nlogn)最坏时间复杂度又稳定的排序算法。它的思路再清晰不过把一个数组分成两半分别把两半都排好序再合并两个有序序列成一个大的有序序列。整个过程用递归来实现先分到底再一层层“治”回去。public static void mergeSort(int[] arr) { if (arr null || arr.length 2) return; int[] temp new int[arr.length]; // 一次性创建辅助数组 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) { // 这里用 保证稳定性相等时先取左半部分 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]; // 把临时数组里的结果拷贝回原数组 for (int p left; p right; p) { arr[p] temp[p]; } }这段代码里有一个很关键的细节辅助数组temp应该只在mergeSort里创建一次而不是在每次递归merge时都new一个新数组。如果你在merge方法里每次new一个数组数组长度加起来是O(nlogn)频繁的内存分配和GC会让性能大幅下降。我见过不少同学在这上面栽跟头数据量一大就性能奇差无比还误以为是递归本身的问题。归并排序为什么稳定核心就在合并时的那个判断当左右两个子数组里出现相等的元素时我们规定先取左边那个。这样一来原本在数组里靠前的相等元素最终在合并后的结果里依然靠前稳定性就保住了。归并排序的时间和空间复杂度分别是O(nlogn)和O(n)。它在Java的JDK里使用极其广泛对对象数组的排序Arrays.sort(T[])底层用的就是TimSort本质上是归并排序的改进版本把插入排序和小规模归并结合了起来。原因很简单对象排序要求稳定。而Arrays.sort(int[])底层则用的双轴快排这是因为基本类型的排序不要求稳定性可以追求更快的平均速度。6. 七种排序横向对比与Java工程选型实战到了这一步七种排序算法我已经全部讲完了代码层面的实现。但作为从业者我心里很清楚一件事考完试、面完试之后真正决定你排序性能的不是哪段代码写得华丽而是你在具体场景下能不能选对方案。所以这一章我直接讲工程选型。真正的Java程序员在日常开发中新写排序逻辑的机会非常少因为JDK自带的Arrays.sort和Collections.sort已经足够优秀它们在内部根据数据类型和数据量自动切换排序策略。但理解它们的策略逻辑对写出高性能代码很有帮助。Arrays.sort(int[])在数据量小于47时采用插入排序大于47采用双轴快排Arrays.sort(Object[])则使用TimSort它会在数据接近有序时利用天然有序片段达到O(n)级别的效率。什么场景下我会选择手写排序而不是直接用JDK方法大概只有两种第一种是你面对的是自定义结构体且不想写比较器想通过一次排序完成某种特殊分组逻辑第二种是算法题环境中要求你实现某个特定排序来证明复杂度。除此之外请你务必使用JDK自带排序因为它做了极致的工程优化手写版本在大部分情况下性能是打不过它的。如果你确实需要自己封装一个排序工具类我给一个比较通用的“混合排序”模板思路数据规模数据特征推荐算法原因 50任意直接插入排序常数极小无额外空间代码简单50 ~ 100000大部分随机快速排序三数取中小区间插排平均性能最佳缓存友好 100000要求稳定性归并排序可迭代版避免递归栈溢出最坏复杂度有保证且稳定 100000要求原地排序堆排序空间O(1)时间复杂度稳定任意规模数据基本有序插入排序或TimSort思路接近O(n)利用有序性这个表格是我踩过不少坑之后总结出来的经验。一个很典型的坑是对100万级数据强行用简单选择排序——你觉得每轮只交换一次成本低但你忽略了每轮都要扫描接近整个数组的比较成本O(n²)的增长曲线在数据量翻倍时的代价是四倍的时间。另外多说一句排序稳定性对工程设计的实际影响。举个场景一个交易系统里你先把流水按交易金额排序再把相同金额的流水按时间排序。如果第二次排序用的是稳定排序那么相同金额的流水自然保持了时间上的先后顺序如果用了不稳定的排序同金额流水的时间顺序可能被打乱最终报表展示会有一种“不专业”的凌乱感。这就是很多底层库在排序对象数据时坚持用归并思想的原因。7. 排序算法避坑指南与实战测试心得这一章我把自己平时在写排序和调试排序时遇到最多的问题汇总一下很多坑只有真正实现过一遍才会懂。7.1 死循环与栈溢出的排查思路快速排序和归并排序的递归版本最容易出栈溢出。排查栈溢出时第一反应应该是递归终止条件是否在极端输入下永远不会触发。快排里最常见的死循环是分区后某一边长度等于原长度导致无限递归。比如基准值选到了最小值partition之后左边区间长度为0右边为n-1如果递归调用没有正确处理边界就可能陷入死循环。还有一个小细节递归版本在大数据量下容易栈溢出的可以考虑手写栈将递归转迭代。归并排序可以写成自底向上的迭代版本先两两合并再四四合并……快排可以用栈保存待处理区间。这个过程在面试中也常被考察你如果能现场把递归改成迭代会是一个加分项。7.2 用测试数据“拷问”排序算法写排序算法之后想要验证正确性不能只跑一两个从小到大排列的数组就收工。我建议至少构造这五类测试数据随机打乱的数据验证基本正确性完全逆序的数据比如 [n, n-1, ..., 1]考验最坏情况完全有序的数据考验最好情况与快速排序的退化问题包含大量重复元素的数据考验内层循环里相等值的处理极端边界空数组、只有一个元素的数组、两个元素的数组我测试时会写一个简单的校验方法先复制一份测试数据调用Arrays.sort排好再和我自己的排序结果逐位比较。这种自动校验比肉眼观察可靠得多。7.3 性能对比的“体感”数据这里分享一组我本地跑过的参考数据仅供参考不同机器差异很大1万个随机int插入排序和冒泡排序耗时在几十毫秒级别快排和归并在个位数毫秒级当数据量上升到10万级别O(n²)算法的耗时可能已经到秒级而O(nlogn)算法依然轻松。100万随机int手写快排大概几百毫秒而Arrays.sort优化过的双轴快排可能只有它的一半。这组数据的意义在于让你建立起“复杂度差距到底意味着什么”的直觉。很多人学算法时觉得O(n²)和O(nlogn)只是一个符号但当数据量达到百万级二者差距是几十倍到上百倍的体感差距这在生产环境里直接影响用户体验。7.4 我踩过的三个具体的“坑”第一个坑希尔排序的gap序列选择。有一阵我为了让代码看起来“高级”用了比较复杂的步长序列结果在小数据集上性能反而不如简单折半。后来我明白了步长序列优劣的差距在数据量很小时显现不出来而“可读性”和“可维护性”反而更值钱。第二个坑快速排序在数据完全有序时的退化。如果每次选第一个元素当基准值对[1, 2, 3, ..., 10000]这样的数组每轮分区都是极端不均衡的递归深度接近10000直接导致StackOverflowError。我改用了三数取中之后这个问题彻底消失。这个坑几乎每个手写快排的人都会踩到。第三个坑忘记更新循环边界条件。写归并排序的merge时如果最后把temp数组拷贝回原数组时循环边界写错比如从0开始而不是从left开始你会发现排序结果总是“部分有序、部分混乱”而且这种bug非常难通过小数据量样例发现因为刚好碰巧边界正确的情况经常发生。排查这类问题最有效的方式还是构造大随机数据做自动校验。7.5 一份可以保底自检的对照表面试考点常见误区正确的理解快排空间复杂度误答O(1)递归调用栈深度平均O(logn)最坏O(n)归并空间复杂度忽略辅助数组需要O(n)的临时数组空间堆排序时间复杂度以为建堆是O(nlogn)堆化过程是O(n)整体是O(nlogn)稳定性搞不清哪些稳定哪些不稳定插入、冒泡、归并稳定其余不稳定希尔排序不稳定以为分组内部插入排序是稳定跨组交换破坏了稳定性把这张表烂熟于心你在面试中应对排序部分的追问时至少不会出现方向性硬伤。8. 总结一点个人体会写排序算法这件事我最大的体会是它教会你的从来不只是“排序”而是递归、分治、复杂度分析、以及“把问题分解成更小问题”的思维方式。从直接插入到希尔从冒泡到快排从简单选择到堆排序再到归并排序你能清晰地看到一条不断“往前提性能上限”的演进路线用空间换时间归并、用随机化保证平均性能快排、用二叉树结构优化选择过程堆排序。我强烈建议你拿出一两个小时把这七种排序全部手写一遍然后跑一遍我上面说的测试数据集亲眼看一看不同算法在不同数据下的表现差异。这个过程比看十篇博客都有用。另外一个小技巧在你写完某个排序后尝试把你的实现和JDK的Arrays.sort做个对比然后问自己三个问题——我的实现能否处理极端输入我的实现是否浪费了空间我的实现能否在复杂度上压住最坏情况这三个问题每次都会让你有所收获。排序算法是很好的“分治思想的微型实验田”吃透了它们你再去看二叉树遍历、图的最短路径这些更复杂的问题会觉得思路顺畅很多。希望这篇内容能帮你在排序这块少踩点坑真正把这些算法变成你的肌肉记忆。