排序算法是每个程序员绕不开的基础功。学过数据结构的人基本都清楚这块内容在面试、工程实践、底层框架源码里出现频率极高。也是很多初学者的分水岭——有人觉得排序就是调库完事有人却能在排序里悟出分治、递归、堆结构这些进阶思维。这篇博文就基于实际教学和编码中沉淀的经验把七种经典排序算法重新捋一遍不绕弯子直接讲清楚它们是什么、能解决什么问题、适合谁来学以及每一轮操作背后到底在做什么。如果你正准备刷算法题、准备面试或者只是写业务代码时想优化一下排序性能这篇内容都能给你提供一套可以照着动手练的路径。每一个算法我都会拆开讲配上可运行的核心代码片段、复杂度推导思路和易错点提醒尽量让零基础的读者也能看得懂、跑得起来。1. 排序算法的整体设计与思路拆解在没接触排序算法之前很多初学者会想排序不就是把一个数组从小到大排一遍吗确实从结果上看所有排序都是一样的。但不同算法在处理同一份数据时的“过程”差异巨大运行时间差出几个数量级也毫不夸张。为什么排序值得单独花大量时间去学一个很直接的原因是排序是无数高级算法的前置步骤。二分查找的前提是有序数据去重操作中排序后相邻元素比对是一种经典解很多数据聚合统计也先依赖排序。换句话说把排序练熟等于给后续学习打了一层底子。另一个原因是排序算法覆盖了算法设计里几乎所有基础思维方式暴力枚举、分而治之、递归、堆结构、空间时间互换。这些思维不是排序独有的但排序给了它们一个最直观、最容易验证的载体。初阶阶段常见的排序选型思路是这样的数据量小、代码要简单优先考虑冒泡、插入、选择数据量中等、要求稳定插入排序表现可能比冒泡更好数据量大快排、归并、堆排序是主场数据近似有序插入排序的优化版本发挥异常出色稳定性作为硬指标时归并和插入是首选这个选型逻辑背后其实藏着不同排序的“性格”。有些排序代码写起来短但性能上限明显有些排序思想复杂但综合表现优异。初学者最大的误区是一上来就想抓住所有算法没有理解它们各自适合的土壤。我先讲一个基础的认知框架排序算法可以按排序过程是否基于“比较”来分类也可以按是否稳定来分类还可以按时间复杂度分类。初阶阶段最重要的三条线就是冒泡、插入、选择归并、快排、堆排序外加一个希尔排序作为插入排序的升级版本。其实不必急着同时学会七种。我建议的学习顺序是先花两三天把冒泡、插入、选择彻底写熟再进入归并和快排最后攻克堆排序。这个顺序对应的正好是思维难度的爬坡曲线。2. 冒泡、插入、选择三种最基础的比较排序这三个排序有一个共同点实现简单、思路直观是理解更高级排序的跳板。很多教学会把它们放在一节课里因为代码形态上确实非常相似——都是两层循环但内层循环的指针移动方式截然不同。2.1 冒泡排序交换相邻逆序对冒泡排序的思路用大白话说每一轮从头到尾扫描一遍发现相邻两个数是降序就交换它们这样每一轮结束时最大的数就会“沉底”或者最小的数“浮到最前”取决于你从哪个方向遍历。重复执行n-1轮数组自然有序。以数组[5, 1, 4, 2, 8]为例第一轮比较相邻元素5和1交换5和4交换5和2交换5和8不用交换。第一轮结束数组变成[1, 4, 2, 5, 8]8已经在最后一位。下一轮继续处理前四个元素直至完全有序。这里有个经常被忽略的优化点如果某一轮扫描过程中完全没有发生交换说明数组已经有序可以直接退出循环。这个优化对小规模近似有序数据效果显著我实测过接近有序的长数组优化后速度提升十倍以上。public void bubbleSort(int[] arr) { 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]) { swap(arr, j, j 1); swapped true; } } if (!swapped) { break; } } }冒泡的时间复杂度最好O(n)最坏和平均O(n²)。空间复杂度O(1)。因为它只在相邻元素逆序时交换相等元素不会被跨越交换所以是稳定排序。不过说实话工程中很少直接用冒泡它的主要价值在教学场景——它是理解“交换排序”和“稳定性”这两件事的最佳起点。2.2 插入排序打扑克牌式整理插入排序的思路最贴近日常生活就像你打扑克牌时每摸到一张新牌就把它插入到手里已经有序的牌堆里正确的位置。也就是把数组分成“已排序区”和“未排序区”每次从未排序区取第一个元素在已排序区从后往前找位置插入。举个例子数组[6, 3, 2, 7, 1]。初始已排序区是第一个元素[6]然后处理33比6小所以6后移一位3放在开头变成[3, 6]。接着处理22与6比较、后移再与3比较、后移最终放在最前面变成[2, 3, 6]。这个过程持续下去直到所有元素都在已排序区。实现上有一次“经典后移”操作容易写错值得唠叨一句不要先把待插入元素赋进去再移动那样会覆盖数据。正确做法是先用临时变量存下待插入的值再把所有比它大的元素逐个后移最后在空出的位置写入临时变量。public void insertionSort(int[] arr) { for (int i 1; i arr.length; i) { int cur arr[i]; int j i - 1; while (j 0 arr[j] cur) { arr[j 1] arr[j]; j--; } arr[j 1] cur; } }插入排序的最好时间复杂度可以达到O(n)这时候数组几乎有序内层while循环往往一次都不执行。平均和最坏是O(n²)。空间O(1)稳定。实际应用中插入排序常作为高级排序的“底层小数据排序方案”因为它在数据量很小比如十几个元素时的常数因子极小反而比归并、快排还要快。很多语言内置于排序库里的小规模优化就用了插入排序。2.3 选择排序每轮挑选最小元素选择排序的思路非常“直男”每轮从未排序区挑出最小的元素直接放到未排序区的最前面也就是已排序区的末尾。对比插入排序一个是“拿着一张牌找位置插”一个是“从剩下一堆里挑最小的牌接在手牌后面”。还是用上面的例子数组[6, 3, 2, 7, 1]。第一轮找到最小元素1与下标0的6交换数组变成[1, 3, 2, 7, 6]。第二轮在剩余元素中找到最小元素2与下标1的3交换数组变成[1, 2, 3, 7, 6]。第三轮最小元素3已经在正确位置与下标2的自己交换数组不变。每一轮固定解决一个位置直到全部到位。选择排序有一个容易被误解的点它被认为是不稳定排序。举例说明数组[2a, 2b, 1]第一轮选出最小的1和下标0的2a交换数组变成[1, 2b, 2a]两个相等的2顺序反转了。因为“远距离跨元素交换”可能跳过相同值所以选择排序不能保证稳定性。public void selectionSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (arr[j] arr[minIdx]) { minIdx j; } } if (minIdx ! i) { swap(arr, i, minIdx); } } }选择排序时间复杂度无论好坏都是O(n²)因为它每一轮都要完整地扫一遍未排序区。空间O(1)不稳定。这三兄弟在实际工程里单独作为完整排序方案都不太常见但它们是理解后续高级算法的良好铺垫尤其是插入排序的“部分有序扩展”思想直接启发了希尔排序。3. 进阶思路为什么需要分治与递归三种基础排序都是O(n²)级别问题在于数据量增长到一万以上时它们会明显变慢。排序n个元素的比较次数如果增长到n²级别当n10000时就是一亿次基本操作真实运行起来会有肉眼可见的卡顿。这时就需要更聪明的策略。计算机科学给出的答案之一就是分治Divide and Conquer把一个大规模问题拆解成几个规模更小的子问题分别解决再合并结果。归并排序和快速排序就是分治思想在排序领域最典型的两个落地。分治天然和递归绑定在一起。递归不必理解为高深概念它就是“函数调用自身”但一定要保证每次调用都在往规模更小的方向走而且要有一个明确的终止条件。初学排序时不少人卡在了递归上其实把递归过程画成“把大数组拆开→拆到不能再拆→逐步合并”的图一下子就能想通。归并排序是“先分后合”把数组二分左边排好右边排好再合并两个有序数组。快速排序是“先定后分”选一个基准值把小于基准值的放左边大于的放右边基准值落到了它最终应该在的位置然后递归处理左右两边。这两个算法在均等情况下都能达到O(n log n)的时间复杂度这也是排序领域“比较类排序”的理论最优级别。它们本质上是绕过了“全局比较太多”的笨办法通过把问题切小来摊薄总操作量。虽然归并和快排都用了分治但它们的性格差异很大。归并有额外空间开销但是稳定快排是原地排序、常数小但稳定性不好。理解这一层差异才能在业务和面试中正确选型。4. 归并排序与快速排序分治思想的双子星分治思想是排序算法从O(n²)跨越到O(n log n)的关键桥梁。归并排序和快速排序是这条思路上最有代表性的两个实现但很多初学者在同一节课上接触这两个算法时容易把它们的递归过程搞混。我个人经验是用一个细节就能区分开——归并排序的“合并”发生在递归之后先拆到底再回程合并快速排序的“划分”发生在递归之前先定基准再往下拆分。4.1 归并排序先把数组拆碎再有序合并归并排序的代码可以拆成两个函数一个负责递归拆分一个负责合并两个有序数组。拆分的原则是找到数组中间位置mid把当前区间一分为二递归排序左半部分和右半部分。合并的原则是同时从左右两个子数组的头部取更小的元素放入一个临时数组直到一方耗尽另一方剩余元素全部挪过去。public void mergeSort(int[] arr, int left, int right) { if (left right) { return; } int mid (left right) 1; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } private void merge(int[] arr, int left, int mid, int right) { int[] temp new int[right - left 1]; int i left, j mid 1, k 0; 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]; } System.arraycopy(temp, 0, arr, left, temp.length); }这里有一个非常重要的细节合并时用还是决定了排序的稳定性。用时左边数组中相等的元素会被优先放入临时数组两个相等元素的相对顺序得以保留用时右边相等的元素会先被写入稳定性就被打破了。这个差别极容易在紧张时写错值得重点记忆。归并排序的时间复杂度恒定为O(n log n)代价是需要O(n)的额外空间来存放临时数组。它擅长处理链表排序也适合无法随机访问的数据结构。在需要稳定排序的常规场景中归并是首选。4.2 快速排序选定基准原地划分快速排序的核心操作是partition划分关键在于选基准值和交换逻辑。常规选法是取区间最右侧或最左侧元素作为基准然后通过双指针把数组划分成“小于基准”和“大于基准”两个部分。我常用的写法是Lomuto划分用两个指针一个慢指针记录“小于基准区的末尾”一个快指针遍历数组。遇到比基准小的元素就把它和慢指针位置的元素交换慢指针前进。遍历结束后把基准元素放到慢指针位置基准的最终位置就确定下来。public void quickSort(int[] arr, int low, int high) { if (low high) { return; } int pivotIndex partition(arr, low, high); quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex 1, high); } private int partition(int[] arr, int low, int high) { int pivot arr[high]; int i low; for (int j low; j high; j) { if (arr[j] pivot) { swap(arr, i, j); i; } } swap(arr, i, high); return i; }快速排序最理想的情况是每次划分都能把数组均匀切分这样递归深度为log n总时间复杂度是O(n log n)。最坏情况是每次划分都极端不平衡比如已经有序的数组每次都取最右侧为基准递归深度变成n最终退化到O(n²)。工程上不会放着最坏情况不管优化手段有很多随机选基准、三数取中法选基准、当数据量小到某个阈值时切换到插入排序。这些优化让快排在极大多数真实场景里都能保持优异性能这也是快排被称为“实际应用中最快的通用排序”的原因。4.3 归并与快排的取舍我建议初学者从三个维度做取舍空间快排原地操作空间O(log n)来自递归栈归并始终需要O(n)辅助数组稳定归并稳定快排不稳定速度常量相同复杂度下快排的常数因子通常更小局部性也更好实际工程中两个算法都有广泛使用。归并适合大数据外部排序比如无法一次性读入内存的内容快排是许多编程语言排序库的默认方案之一。5. 稳定性问题容易被忽视的关键指标很多初学者在看排序算法时会把注意力全部放在时间和空间复杂度上忽略掉稳定性这个指标。但在真实业务场景里稳定性会直接影响功能正确性。先解释一下稳定性的定义如果待排序序列中存在两个相等元素a和b且a原本排在b前面排序完成后这个前后关系仍然保持那这个排序就是稳定的如果有可能反了就是不稳定的。这个性质看起来是细节在表格类数据排序时会放大成大事。假设你在一个电商系统里按“销量”给商品排序销量相同的时候期望按“上架时间”的先后顺序展示。如果直接用不稳定的排序算法按销量排列销量相同的商品间的上架时间顺序会被打乱用户看到的结果就不符合预期。正确做法是如果排序列包含“主排序关键字”和“次排序关键字”可以先按次要关键字排再按主要关键字做一个稳定排序。两次稳定排序能保证最终结果满足两个维度的顺序要求。这一点在业务代码里非常常见。初阶阶段必须记住的稳定性结论稳定冒泡、插入、归并不稳定选择、希尔、快排、堆排再延伸一句面试里常见的提问是“为什么托马斯不是稳定排序”或者“快排怎样改为稳定排序”。前者反正就是不稳定的因为划分过程中会跨度交换很难保证相等的元素相对次序后者要改成稳定版本比较麻烦一般需要引入额外空间失去原地排序的优势。这也是为什么实际设计排序库时对于大型对象数组会倾向使用归并排序而基本类型数组则可以直接用快排——基本类型的相等性无须保持顺序。6. 堆排序借助完全二叉树结构实现原地排序堆排序的路数比归并和快排更曲折一点它不采用分治的思路而是借助一种特殊的数据结构——堆。堆是一棵完全二叉树用数组可以非常紧凑地存储。初看起来堆排序代码量偏大但只要理解了堆的两个核心操作建堆和下沉heapify代码就能顺利写出来。堆排序的第一步是把整个数组整理成一个最大堆也就是每个父节点的值都大于等于其孩子节点的值第二步是反复把堆顶元素也就是当前最大值移到最后再把剩余部分重新调整为最大堆。建堆可以用从最后一个非叶子节点开始的“下沉”操作完成。我用下沉法编写的代码如下public void heapSort(int[] arr) { 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 void heapify(int[] arr, int size, int index) { int largest index; int left 2 * index 1; int right 2 * index 2; if (left size arr[left] arr[largest]) { largest left; } if (right size arr[right] arr[largest]) { largest right; } if (largest ! index) { swap(arr, index, largest); heapify(arr, size, largest); } }堆排序的时间复杂度稳定在O(n log n)且不需要额外的辅助数组空间O(1)。但它的不足也很明显不稳定元素跳来跳去访问对缓存不友好常数因子比快排大。在大多数通用排序场景里快排仍然优于堆排序。堆排序真正的舞台反而是“优先队列”和“求Top K”这类场景不一定需要完整排序时堆能高效地维护前K个最大或最小元素。学堆排序时不用背代码先把堆的性质、下沉操作的逻辑吃透写成代码是水到渠成的事。我见过不少同学把堆排序写成每次取出堆顶后再重新建堆性能变成O(n²)原因就是没有理解“交换堆顶到末尾后只需要对堆顶做一次下沉”这个关键降本操作。7. 希尔排序插入排序的跳跃升级版希尔排序是插入排序的改进版本。插入排序的问题在于它只会逐个比较相邻元素如果某个很小的元素在数组尾部它必须一步一步挪到最前面移动次数非常多。希尔排序的做法是先让元素可以进行“大跨度”移动再逐渐缩小跨度最后用普通的插入排序收尾。跨度也就是gap通常初始为数组长度的一半然后不断缩小。以gapg进行排序时我把下标按模g分成g组每一组内部做插入排序。这是预处理让数组变得“基本有序”——整体上看元素离最终位置不会太远。最后一轮gap1时相当于完整插入排序但因为数组基本有序插入排序的性能非常好。public void shellSort(int[] arr) { int n arr.length; for (int gap n / 2; gap 0; gap / 2) { for (int i gap; i n; i) { int cur arr[i]; int j i; while (j gap arr[j - gap] cur) { arr[j] arr[j - gap]; j - gap; } arr[j] cur; } } }希尔排序的时间复杂度分析比前几个算法复杂它依赖于间隔序列的选取。简单gap折半策略下时间复杂度大约在O(n²)到O(n log² n)之间这是“退化为插入排序”这个下限所决定的。它不稳定原因在于跨越gap交换时可能让相等元素的相对位置改变。实际工程中希尔排序用得不多但它在中等规模数据和内存受限环境下依然有一席之地。从教学角度看它是对“插入排序劣势”的绝佳延伸讲解——通过跳跃式移动克服局部性瓶颈。8. 七种排序的性能对比与选型建议把所有排序放在一起做横向对比时表格最好用。我这里直接给出总结过的数据基于普通随机数据的常见运行表现排序算法平均时间最坏时间额外空间稳定性冒泡O(n²)O(n²)O(1)稳定选择O(n²)O(n²)O(1)不稳定插入O(n²)O(n²)O(1)稳定希尔O(n log² n)依间隔序列而定O(1)不稳定快排O(n log n)O(n²)O(log n)不稳定归并O(n log n)O(n log n)O(n)稳定堆排O(n log n)O(n log n)O(1)不稳定数据量在几十到几百这个区间时插入排序的实测速度很可能超过快排。原因很好理解快排有递归函数调用开销和划分循环里相对复杂的分支逻辑而插入排序的代码路径非常紧凑。很多语言内置排序库对小规模数据切换到插入排序就是这个原因。选型的参考逻辑是这样的如果在内存很紧张的环境又要保证最坏情况可控选择堆排序如果排序结果需要保持原有相同元素的相对顺序选择归并或插入如果大部分场景追求平均性能最优且不强求稳定性选择快排如果数据量很小比如十几个数直接选插入排序写起来简单跑得也快稳定性方面冒泡和插入稳定选择不稳定这几乎是面试中必问的高频知识点。希尔和快排由于引入跳跃式交换稳定性都被破坏。归并通过临时数组按顺序合并在不额外增加比较次数的情况下天然稳定。没有万能排序这就是为什么现实中的排序库通常都是混合策略。语言底层往往会把快排、插入排序、堆排序组合在一起根据递归深度和数据规模在运行时动态选择具体方案。理解这一点比死记硬背某一种排序更贴近工程。9. 实操过程从零手写一个排序效率检测器只看不练、只背不写排序算法基本等于没学。我强烈建议大家不要只在IDE里跑通代码就算了而是写一个最简单的测试框架在同一份随机数据上跑不同排序记录耗时再用系统方法验证排序结果是否正确。这个“效率检测器”的思路很简单生成一组随机数分别调用你写的排序函数前后打印时间戳最后用断言检查数组是否严格升序。通过实际打印数据你还会意外发现很多“写时一时爽跑时火葬场”的问题。完整代码如下import java.util.Random; public class SortTester { public static void main(String[] args) { int size 20000; int[] base generateRandomArray(size); testSort(冒泡排序, base, SortTester::bubbleSort); testSort(选择排序, base, SortTester::selectionSort); testSort(插入排序, base, SortTester::insertionSort); testSort(快速排序, base, SortTester::quickSort); testSort(归并排序, base, SortTester::mergeSort); testSort(堆排序, base, SortTester::heapSort); testSort(希尔排序, base, SortTester::shellSort); } private static void testSort(String name, int[] source, Sorter sorter) { int[] arr source.clone(); long start System.nanoTime(); sorter.sort(arr); long cost System.nanoTime() - start; System.out.printf(%s 耗时 %.3f ms, 是否有序: %s%n, name, cost / 1e6, isSorted(arr)); } private static int[] generateRandomArray(int size) { Random random new Random(); int[] arr new int[size]; for (int i 0; i size; i) { arr[i] random.nextInt(size * 10); } return arr; } private static boolean isSorted(int[] arr) { for (int i 1; i arr.length; i) { if (arr[i] arr[i - 1]) { return false; } } return true; } private interface Sorter { void sort(int[] arr); } // 各排序方法实现省略 }有几点实际经验值得分享必须克隆原始数组再测否则第一个排序跑完后面的排序接收到的就是有序数组测出来的时间完全失真数据尺寸可以从1000、10000、100000逐级增加观察不同排序的增长趋势数据内容也要做变换完全随机、近似有序、完全逆序三类数据能暴露算法的最高和最低水平看运行结果时会发现一个有趣现象数据规模在两万以内时插入排序干掉归并和快排完全有可能但数据量冲到百万级插入排序会彻底掉队快排和归并的时间曲线还在稳定爬坡。这种直观体验比任何理论都更能让人记住复杂度分析的实际含义。10. 常见问题与排查技巧实录排序算法的代码量虽然不大但很容易在一些隐蔽细节上出错。操作过程中我积累了不少常见问题的排查经验整理如下。问题1递归没有终止条件导致栈溢出排查方法快速排序和归并排序递归调用的第一行要先判断区间是否无效。快速排序里常见判断是low high时直接返回归并排序同理。这个判断漏掉后递归会无限拆下去直到抛出栈溢出报错。问题2归并排序合并结果不对出现丢失元素排查方法多半是临时数组copy回原数组时下标没对齐。我见过很多次把System.arraycopy(temp, 0, arr, left, temp.length)中起始位置left误写为0导致有序结果覆盖到数组开头。归并排序的合并过程虽然短但每个下标都是从左边界开始的不能想当然写绝对位置。问题3快速排序基准元素位置没处理好导致死循环排查方法分区函数返回的基准下标分割区间时要排除掉基准本身。有些场景基准被选区最大值划分后基准被交换到数组末尾如果递归调用时多包了一个基准位置就会造成不可预期的结果。最稳妥的是每次打印当前区间看是不是在逐步缩短而不是原地踏步。问题4堆排序建堆循环起始点计算错误很多初学者从n - 1开始建堆其实应该从最后一个非叶子节点n / 2 - 1开始。即使从n - 1开始也能运行叶子节点没有孩子下沉操作只会空转浪费性能堆排序因此退化。这个点建议直接用n / 2 - 1既符合完全二叉树的性质也省掉多余遍历。问题5数据量巨大时快排递归树过深最坏情况接近O(n²)这种情况常出现在数组已经完全有序时。解决方案是在数据有规律时主动打乱数据或者用三数取中策略提前干预。工程上更稳妥的做法是在递归深度超过一定阈值时切换成堆排序。另外有一个容易忽视的问题在测试排序性能时需要先保证测试数据完全一致。我用过某个同学的测试代码他在测试不同排序前重新生成了数组导致各排序处理的数据完全不同结果对排序性能评价毫无意义。在一个测试框架内共享克隆同一个源数组才具备可比性。10.1 一种值得多练的调试秘法排序算法有时候一眼看不出问题我的习惯是写一个“小数据可视化打印”。把排序数组长度限制在10以内每完成一轮操作打印一步。比如冒泡每轮打印结果、快速排序打印中间划分结果、归并排序打印合并后的数组这样能非常直观地看到数据是从哪里开始跑偏的。用这种方法我排查过不下十次快速排序边界问题的经验强烈推荐初学者在头脑一时转不过来时借助这个调试手段。等到写熟之后就不需要了但初学阶段的帮助立竿见影。11. 我的实操体会与后续扩展建议七种排序写完、性能检测器跑通之后我建议你做这几件事来巩固和扩展。第一尝试把所有排序改成泛型版本。Java里可以用ComparableT这样能排序任意对象类型。改造过程中你会意识到基本类型和对象类型的不同处理方式也会更清楚稳定性对于对象排序的意义。第二把归并排序的递归版本改成迭代版本。这个练习能帮你理解递归栈等价于手动栈维护同时强化对“分治回溯”过程的认识。迭代归并用“宽度优先”的方式层层合并代码结构完全不同但结果一致。第三练习写“Top K”问题和“求中位数”问题把堆排序思想迁移过去。这两个问题在实践中出现频率很高数据不需要全排序只需要维护一个容量为K的堆。最后说说我个人写排序过程中踩过的坑。我记得刚接触归并排序时总想着在拆分的函数里直接合并结果每次递归都新建了临时数组空间开销剧增性能一塌糊涂。后来理解了“分离拆分与合并”这个分工思路代码一眼清晰。这是我学排序收获最大的一个体验排序算法看似是死代码实际上每一处的代码组织方式都受到时间空间复杂度目标的牵制想通这个很多代码就自然能写出来。还有一个小经验面试中如果要求写排序不要一上来就写快排。先和面试官确认清楚数据规模、稳定性要求、是否原地排序再选择算法这本身就是给面试官留下好印象的关键。工程里也一样没有最好只有最合适的排序方案。
排序算法是每个程序员绕不开的基础功。学过数据结构的人基本都清楚这块内容在面试、工程实践、底层框架源码里出现频率极高。也是很多初学者的分水岭——有人觉得排序就是调库完事有人却能在排序里悟出分治、递归、堆结构这些进阶思维。这篇博文就基于实际教学和编码中沉淀的经验把七种经典排序算法重新捋一遍不绕弯子直接讲清楚它们是什么、能解决什么问题、适合谁来学以及每一轮操作背后到底在做什么。如果你正准备刷算法题、准备面试或者只是写业务代码时想优化一下排序性能这篇内容都能给你提供一套可以照着动手练的路径。每一个算法我都会拆开讲配上可运行的核心代码片段、复杂度推导思路和易错点提醒尽量让零基础的读者也能看得懂、跑得起来。1. 排序算法的整体设计与思路拆解在没接触排序算法之前很多初学者会想排序不就是把一个数组从小到大排一遍吗确实从结果上看所有排序都是一样的。但不同算法在处理同一份数据时的“过程”差异巨大运行时间差出几个数量级也毫不夸张。为什么排序值得单独花大量时间去学一个很直接的原因是排序是无数高级算法的前置步骤。二分查找的前提是有序数据去重操作中排序后相邻元素比对是一种经典解很多数据聚合统计也先依赖排序。换句话说把排序练熟等于给后续学习打了一层底子。另一个原因是排序算法覆盖了算法设计里几乎所有基础思维方式暴力枚举、分而治之、递归、堆结构、空间时间互换。这些思维不是排序独有的但排序给了它们一个最直观、最容易验证的载体。初阶阶段常见的排序选型思路是这样的数据量小、代码要简单优先考虑冒泡、插入、选择数据量中等、要求稳定插入排序表现可能比冒泡更好数据量大快排、归并、堆排序是主场数据近似有序插入排序的优化版本发挥异常出色稳定性作为硬指标时归并和插入是首选这个选型逻辑背后其实藏着不同排序的“性格”。有些排序代码写起来短但性能上限明显有些排序思想复杂但综合表现优异。初学者最大的误区是一上来就想抓住所有算法没有理解它们各自适合的土壤。我先讲一个基础的认知框架排序算法可以按排序过程是否基于“比较”来分类也可以按是否稳定来分类还可以按时间复杂度分类。初阶阶段最重要的三条线就是冒泡、插入、选择归并、快排、堆排序外加一个希尔排序作为插入排序的升级版本。其实不必急着同时学会七种。我建议的学习顺序是先花两三天把冒泡、插入、选择彻底写熟再进入归并和快排最后攻克堆排序。这个顺序对应的正好是思维难度的爬坡曲线。2. 冒泡、插入、选择三种最基础的比较排序这三个排序有一个共同点实现简单、思路直观是理解更高级排序的跳板。很多教学会把它们放在一节课里因为代码形态上确实非常相似——都是两层循环但内层循环的指针移动方式截然不同。2.1 冒泡排序交换相邻逆序对冒泡排序的思路用大白话说每一轮从头到尾扫描一遍发现相邻两个数是降序就交换它们这样每一轮结束时最大的数就会“沉底”或者最小的数“浮到最前”取决于你从哪个方向遍历。重复执行n-1轮数组自然有序。以数组[5, 1, 4, 2, 8]为例第一轮比较相邻元素5和1交换5和4交换5和2交换5和8不用交换。第一轮结束数组变成[1, 4, 2, 5, 8]8已经在最后一位。下一轮继续处理前四个元素直至完全有序。这里有个经常被忽略的优化点如果某一轮扫描过程中完全没有发生交换说明数组已经有序可以直接退出循环。这个优化对小规模近似有序数据效果显著我实测过接近有序的长数组优化后速度提升十倍以上。public void bubbleSort(int[] arr) { 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]) { swap(arr, j, j 1); swapped true; } } if (!swapped) { break; } } }冒泡的时间复杂度最好O(n)最坏和平均O(n²)。空间复杂度O(1)。因为它只在相邻元素逆序时交换相等元素不会被跨越交换所以是稳定排序。不过说实话工程中很少直接用冒泡它的主要价值在教学场景——它是理解“交换排序”和“稳定性”这两件事的最佳起点。2.2 插入排序打扑克牌式整理插入排序的思路最贴近日常生活就像你打扑克牌时每摸到一张新牌就把它插入到手里已经有序的牌堆里正确的位置。也就是把数组分成“已排序区”和“未排序区”每次从未排序区取第一个元素在已排序区从后往前找位置插入。举个例子数组[6, 3, 2, 7, 1]。初始已排序区是第一个元素[6]然后处理33比6小所以6后移一位3放在开头变成[3, 6]。接着处理22与6比较、后移再与3比较、后移最终放在最前面变成[2, 3, 6]。这个过程持续下去直到所有元素都在已排序区。实现上有一次“经典后移”操作容易写错值得唠叨一句不要先把待插入元素赋进去再移动那样会覆盖数据。正确做法是先用临时变量存下待插入的值再把所有比它大的元素逐个后移最后在空出的位置写入临时变量。public void insertionSort(int[] arr) { for (int i 1; i arr.length; i) { int cur arr[i]; int j i - 1; while (j 0 arr[j] cur) { arr[j 1] arr[j]; j--; } arr[j 1] cur; } }插入排序的最好时间复杂度可以达到O(n)这时候数组几乎有序内层while循环往往一次都不执行。平均和最坏是O(n²)。空间O(1)稳定。实际应用中插入排序常作为高级排序的“底层小数据排序方案”因为它在数据量很小比如十几个元素时的常数因子极小反而比归并、快排还要快。很多语言内置于排序库里的小规模优化就用了插入排序。2.3 选择排序每轮挑选最小元素选择排序的思路非常“直男”每轮从未排序区挑出最小的元素直接放到未排序区的最前面也就是已排序区的末尾。对比插入排序一个是“拿着一张牌找位置插”一个是“从剩下一堆里挑最小的牌接在手牌后面”。还是用上面的例子数组[6, 3, 2, 7, 1]。第一轮找到最小元素1与下标0的6交换数组变成[1, 3, 2, 7, 6]。第二轮在剩余元素中找到最小元素2与下标1的3交换数组变成[1, 2, 3, 7, 6]。第三轮最小元素3已经在正确位置与下标2的自己交换数组不变。每一轮固定解决一个位置直到全部到位。选择排序有一个容易被误解的点它被认为是不稳定排序。举例说明数组[2a, 2b, 1]第一轮选出最小的1和下标0的2a交换数组变成[1, 2b, 2a]两个相等的2顺序反转了。因为“远距离跨元素交换”可能跳过相同值所以选择排序不能保证稳定性。public void selectionSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (arr[j] arr[minIdx]) { minIdx j; } } if (minIdx ! i) { swap(arr, i, minIdx); } } }选择排序时间复杂度无论好坏都是O(n²)因为它每一轮都要完整地扫一遍未排序区。空间O(1)不稳定。这三兄弟在实际工程里单独作为完整排序方案都不太常见但它们是理解后续高级算法的良好铺垫尤其是插入排序的“部分有序扩展”思想直接启发了希尔排序。3. 进阶思路为什么需要分治与递归三种基础排序都是O(n²)级别问题在于数据量增长到一万以上时它们会明显变慢。排序n个元素的比较次数如果增长到n²级别当n10000时就是一亿次基本操作真实运行起来会有肉眼可见的卡顿。这时就需要更聪明的策略。计算机科学给出的答案之一就是分治Divide and Conquer把一个大规模问题拆解成几个规模更小的子问题分别解决再合并结果。归并排序和快速排序就是分治思想在排序领域最典型的两个落地。分治天然和递归绑定在一起。递归不必理解为高深概念它就是“函数调用自身”但一定要保证每次调用都在往规模更小的方向走而且要有一个明确的终止条件。初学排序时不少人卡在了递归上其实把递归过程画成“把大数组拆开→拆到不能再拆→逐步合并”的图一下子就能想通。归并排序是“先分后合”把数组二分左边排好右边排好再合并两个有序数组。快速排序是“先定后分”选一个基准值把小于基准值的放左边大于的放右边基准值落到了它最终应该在的位置然后递归处理左右两边。这两个算法在均等情况下都能达到O(n log n)的时间复杂度这也是排序领域“比较类排序”的理论最优级别。它们本质上是绕过了“全局比较太多”的笨办法通过把问题切小来摊薄总操作量。虽然归并和快排都用了分治但它们的性格差异很大。归并有额外空间开销但是稳定快排是原地排序、常数小但稳定性不好。理解这一层差异才能在业务和面试中正确选型。4. 归并排序与快速排序分治思想的双子星分治思想是排序算法从O(n²)跨越到O(n log n)的关键桥梁。归并排序和快速排序是这条思路上最有代表性的两个实现但很多初学者在同一节课上接触这两个算法时容易把它们的递归过程搞混。我个人经验是用一个细节就能区分开——归并排序的“合并”发生在递归之后先拆到底再回程合并快速排序的“划分”发生在递归之前先定基准再往下拆分。4.1 归并排序先把数组拆碎再有序合并归并排序的代码可以拆成两个函数一个负责递归拆分一个负责合并两个有序数组。拆分的原则是找到数组中间位置mid把当前区间一分为二递归排序左半部分和右半部分。合并的原则是同时从左右两个子数组的头部取更小的元素放入一个临时数组直到一方耗尽另一方剩余元素全部挪过去。public void mergeSort(int[] arr, int left, int right) { if (left right) { return; } int mid (left right) 1; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } private void merge(int[] arr, int left, int mid, int right) { int[] temp new int[right - left 1]; int i left, j mid 1, k 0; 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]; } System.arraycopy(temp, 0, arr, left, temp.length); }这里有一个非常重要的细节合并时用还是决定了排序的稳定性。用时左边数组中相等的元素会被优先放入临时数组两个相等元素的相对顺序得以保留用时右边相等的元素会先被写入稳定性就被打破了。这个差别极容易在紧张时写错值得重点记忆。归并排序的时间复杂度恒定为O(n log n)代价是需要O(n)的额外空间来存放临时数组。它擅长处理链表排序也适合无法随机访问的数据结构。在需要稳定排序的常规场景中归并是首选。4.2 快速排序选定基准原地划分快速排序的核心操作是partition划分关键在于选基准值和交换逻辑。常规选法是取区间最右侧或最左侧元素作为基准然后通过双指针把数组划分成“小于基准”和“大于基准”两个部分。我常用的写法是Lomuto划分用两个指针一个慢指针记录“小于基准区的末尾”一个快指针遍历数组。遇到比基准小的元素就把它和慢指针位置的元素交换慢指针前进。遍历结束后把基准元素放到慢指针位置基准的最终位置就确定下来。public void quickSort(int[] arr, int low, int high) { if (low high) { return; } int pivotIndex partition(arr, low, high); quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex 1, high); } private int partition(int[] arr, int low, int high) { int pivot arr[high]; int i low; for (int j low; j high; j) { if (arr[j] pivot) { swap(arr, i, j); i; } } swap(arr, i, high); return i; }快速排序最理想的情况是每次划分都能把数组均匀切分这样递归深度为log n总时间复杂度是O(n log n)。最坏情况是每次划分都极端不平衡比如已经有序的数组每次都取最右侧为基准递归深度变成n最终退化到O(n²)。工程上不会放着最坏情况不管优化手段有很多随机选基准、三数取中法选基准、当数据量小到某个阈值时切换到插入排序。这些优化让快排在极大多数真实场景里都能保持优异性能这也是快排被称为“实际应用中最快的通用排序”的原因。4.3 归并与快排的取舍我建议初学者从三个维度做取舍空间快排原地操作空间O(log n)来自递归栈归并始终需要O(n)辅助数组稳定归并稳定快排不稳定速度常量相同复杂度下快排的常数因子通常更小局部性也更好实际工程中两个算法都有广泛使用。归并适合大数据外部排序比如无法一次性读入内存的内容快排是许多编程语言排序库的默认方案之一。5. 稳定性问题容易被忽视的关键指标很多初学者在看排序算法时会把注意力全部放在时间和空间复杂度上忽略掉稳定性这个指标。但在真实业务场景里稳定性会直接影响功能正确性。先解释一下稳定性的定义如果待排序序列中存在两个相等元素a和b且a原本排在b前面排序完成后这个前后关系仍然保持那这个排序就是稳定的如果有可能反了就是不稳定的。这个性质看起来是细节在表格类数据排序时会放大成大事。假设你在一个电商系统里按“销量”给商品排序销量相同的时候期望按“上架时间”的先后顺序展示。如果直接用不稳定的排序算法按销量排列销量相同的商品间的上架时间顺序会被打乱用户看到的结果就不符合预期。正确做法是如果排序列包含“主排序关键字”和“次排序关键字”可以先按次要关键字排再按主要关键字做一个稳定排序。两次稳定排序能保证最终结果满足两个维度的顺序要求。这一点在业务代码里非常常见。初阶阶段必须记住的稳定性结论稳定冒泡、插入、归并不稳定选择、希尔、快排、堆排再延伸一句面试里常见的提问是“为什么托马斯不是稳定排序”或者“快排怎样改为稳定排序”。前者反正就是不稳定的因为划分过程中会跨度交换很难保证相等的元素相对次序后者要改成稳定版本比较麻烦一般需要引入额外空间失去原地排序的优势。这也是为什么实际设计排序库时对于大型对象数组会倾向使用归并排序而基本类型数组则可以直接用快排——基本类型的相等性无须保持顺序。6. 堆排序借助完全二叉树结构实现原地排序堆排序的路数比归并和快排更曲折一点它不采用分治的思路而是借助一种特殊的数据结构——堆。堆是一棵完全二叉树用数组可以非常紧凑地存储。初看起来堆排序代码量偏大但只要理解了堆的两个核心操作建堆和下沉heapify代码就能顺利写出来。堆排序的第一步是把整个数组整理成一个最大堆也就是每个父节点的值都大于等于其孩子节点的值第二步是反复把堆顶元素也就是当前最大值移到最后再把剩余部分重新调整为最大堆。建堆可以用从最后一个非叶子节点开始的“下沉”操作完成。我用下沉法编写的代码如下public void heapSort(int[] arr) { 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 void heapify(int[] arr, int size, int index) { int largest index; int left 2 * index 1; int right 2 * index 2; if (left size arr[left] arr[largest]) { largest left; } if (right size arr[right] arr[largest]) { largest right; } if (largest ! index) { swap(arr, index, largest); heapify(arr, size, largest); } }堆排序的时间复杂度稳定在O(n log n)且不需要额外的辅助数组空间O(1)。但它的不足也很明显不稳定元素跳来跳去访问对缓存不友好常数因子比快排大。在大多数通用排序场景里快排仍然优于堆排序。堆排序真正的舞台反而是“优先队列”和“求Top K”这类场景不一定需要完整排序时堆能高效地维护前K个最大或最小元素。学堆排序时不用背代码先把堆的性质、下沉操作的逻辑吃透写成代码是水到渠成的事。我见过不少同学把堆排序写成每次取出堆顶后再重新建堆性能变成O(n²)原因就是没有理解“交换堆顶到末尾后只需要对堆顶做一次下沉”这个关键降本操作。7. 希尔排序插入排序的跳跃升级版希尔排序是插入排序的改进版本。插入排序的问题在于它只会逐个比较相邻元素如果某个很小的元素在数组尾部它必须一步一步挪到最前面移动次数非常多。希尔排序的做法是先让元素可以进行“大跨度”移动再逐渐缩小跨度最后用普通的插入排序收尾。跨度也就是gap通常初始为数组长度的一半然后不断缩小。以gapg进行排序时我把下标按模g分成g组每一组内部做插入排序。这是预处理让数组变得“基本有序”——整体上看元素离最终位置不会太远。最后一轮gap1时相当于完整插入排序但因为数组基本有序插入排序的性能非常好。public void shellSort(int[] arr) { int n arr.length; for (int gap n / 2; gap 0; gap / 2) { for (int i gap; i n; i) { int cur arr[i]; int j i; while (j gap arr[j - gap] cur) { arr[j] arr[j - gap]; j - gap; } arr[j] cur; } } }希尔排序的时间复杂度分析比前几个算法复杂它依赖于间隔序列的选取。简单gap折半策略下时间复杂度大约在O(n²)到O(n log² n)之间这是“退化为插入排序”这个下限所决定的。它不稳定原因在于跨越gap交换时可能让相等元素的相对位置改变。实际工程中希尔排序用得不多但它在中等规模数据和内存受限环境下依然有一席之地。从教学角度看它是对“插入排序劣势”的绝佳延伸讲解——通过跳跃式移动克服局部性瓶颈。8. 七种排序的性能对比与选型建议把所有排序放在一起做横向对比时表格最好用。我这里直接给出总结过的数据基于普通随机数据的常见运行表现排序算法平均时间最坏时间额外空间稳定性冒泡O(n²)O(n²)O(1)稳定选择O(n²)O(n²)O(1)不稳定插入O(n²)O(n²)O(1)稳定希尔O(n log² n)依间隔序列而定O(1)不稳定快排O(n log n)O(n²)O(log n)不稳定归并O(n log n)O(n log n)O(n)稳定堆排O(n log n)O(n log n)O(1)不稳定数据量在几十到几百这个区间时插入排序的实测速度很可能超过快排。原因很好理解快排有递归函数调用开销和划分循环里相对复杂的分支逻辑而插入排序的代码路径非常紧凑。很多语言内置排序库对小规模数据切换到插入排序就是这个原因。选型的参考逻辑是这样的如果在内存很紧张的环境又要保证最坏情况可控选择堆排序如果排序结果需要保持原有相同元素的相对顺序选择归并或插入如果大部分场景追求平均性能最优且不强求稳定性选择快排如果数据量很小比如十几个数直接选插入排序写起来简单跑得也快稳定性方面冒泡和插入稳定选择不稳定这几乎是面试中必问的高频知识点。希尔和快排由于引入跳跃式交换稳定性都被破坏。归并通过临时数组按顺序合并在不额外增加比较次数的情况下天然稳定。没有万能排序这就是为什么现实中的排序库通常都是混合策略。语言底层往往会把快排、插入排序、堆排序组合在一起根据递归深度和数据规模在运行时动态选择具体方案。理解这一点比死记硬背某一种排序更贴近工程。9. 实操过程从零手写一个排序效率检测器只看不练、只背不写排序算法基本等于没学。我强烈建议大家不要只在IDE里跑通代码就算了而是写一个最简单的测试框架在同一份随机数据上跑不同排序记录耗时再用系统方法验证排序结果是否正确。这个“效率检测器”的思路很简单生成一组随机数分别调用你写的排序函数前后打印时间戳最后用断言检查数组是否严格升序。通过实际打印数据你还会意外发现很多“写时一时爽跑时火葬场”的问题。完整代码如下import java.util.Random; public class SortTester { public static void main(String[] args) { int size 20000; int[] base generateRandomArray(size); testSort(冒泡排序, base, SortTester::bubbleSort); testSort(选择排序, base, SortTester::selectionSort); testSort(插入排序, base, SortTester::insertionSort); testSort(快速排序, base, SortTester::quickSort); testSort(归并排序, base, SortTester::mergeSort); testSort(堆排序, base, SortTester::heapSort); testSort(希尔排序, base, SortTester::shellSort); } private static void testSort(String name, int[] source, Sorter sorter) { int[] arr source.clone(); long start System.nanoTime(); sorter.sort(arr); long cost System.nanoTime() - start; System.out.printf(%s 耗时 %.3f ms, 是否有序: %s%n, name, cost / 1e6, isSorted(arr)); } private static int[] generateRandomArray(int size) { Random random new Random(); int[] arr new int[size]; for (int i 0; i size; i) { arr[i] random.nextInt(size * 10); } return arr; } private static boolean isSorted(int[] arr) { for (int i 1; i arr.length; i) { if (arr[i] arr[i - 1]) { return false; } } return true; } private interface Sorter { void sort(int[] arr); } // 各排序方法实现省略 }有几点实际经验值得分享必须克隆原始数组再测否则第一个排序跑完后面的排序接收到的就是有序数组测出来的时间完全失真数据尺寸可以从1000、10000、100000逐级增加观察不同排序的增长趋势数据内容也要做变换完全随机、近似有序、完全逆序三类数据能暴露算法的最高和最低水平看运行结果时会发现一个有趣现象数据规模在两万以内时插入排序干掉归并和快排完全有可能但数据量冲到百万级插入排序会彻底掉队快排和归并的时间曲线还在稳定爬坡。这种直观体验比任何理论都更能让人记住复杂度分析的实际含义。10. 常见问题与排查技巧实录排序算法的代码量虽然不大但很容易在一些隐蔽细节上出错。操作过程中我积累了不少常见问题的排查经验整理如下。问题1递归没有终止条件导致栈溢出排查方法快速排序和归并排序递归调用的第一行要先判断区间是否无效。快速排序里常见判断是low high时直接返回归并排序同理。这个判断漏掉后递归会无限拆下去直到抛出栈溢出报错。问题2归并排序合并结果不对出现丢失元素排查方法多半是临时数组copy回原数组时下标没对齐。我见过很多次把System.arraycopy(temp, 0, arr, left, temp.length)中起始位置left误写为0导致有序结果覆盖到数组开头。归并排序的合并过程虽然短但每个下标都是从左边界开始的不能想当然写绝对位置。问题3快速排序基准元素位置没处理好导致死循环排查方法分区函数返回的基准下标分割区间时要排除掉基准本身。有些场景基准被选区最大值划分后基准被交换到数组末尾如果递归调用时多包了一个基准位置就会造成不可预期的结果。最稳妥的是每次打印当前区间看是不是在逐步缩短而不是原地踏步。问题4堆排序建堆循环起始点计算错误很多初学者从n - 1开始建堆其实应该从最后一个非叶子节点n / 2 - 1开始。即使从n - 1开始也能运行叶子节点没有孩子下沉操作只会空转浪费性能堆排序因此退化。这个点建议直接用n / 2 - 1既符合完全二叉树的性质也省掉多余遍历。问题5数据量巨大时快排递归树过深最坏情况接近O(n²)这种情况常出现在数组已经完全有序时。解决方案是在数据有规律时主动打乱数据或者用三数取中策略提前干预。工程上更稳妥的做法是在递归深度超过一定阈值时切换成堆排序。另外有一个容易忽视的问题在测试排序性能时需要先保证测试数据完全一致。我用过某个同学的测试代码他在测试不同排序前重新生成了数组导致各排序处理的数据完全不同结果对排序性能评价毫无意义。在一个测试框架内共享克隆同一个源数组才具备可比性。10.1 一种值得多练的调试秘法排序算法有时候一眼看不出问题我的习惯是写一个“小数据可视化打印”。把排序数组长度限制在10以内每完成一轮操作打印一步。比如冒泡每轮打印结果、快速排序打印中间划分结果、归并排序打印合并后的数组这样能非常直观地看到数据是从哪里开始跑偏的。用这种方法我排查过不下十次快速排序边界问题的经验强烈推荐初学者在头脑一时转不过来时借助这个调试手段。等到写熟之后就不需要了但初学阶段的帮助立竿见影。11. 我的实操体会与后续扩展建议七种排序写完、性能检测器跑通之后我建议你做这几件事来巩固和扩展。第一尝试把所有排序改成泛型版本。Java里可以用ComparableT这样能排序任意对象类型。改造过程中你会意识到基本类型和对象类型的不同处理方式也会更清楚稳定性对于对象排序的意义。第二把归并排序的递归版本改成迭代版本。这个练习能帮你理解递归栈等价于手动栈维护同时强化对“分治回溯”过程的认识。迭代归并用“宽度优先”的方式层层合并代码结构完全不同但结果一致。第三练习写“Top K”问题和“求中位数”问题把堆排序思想迁移过去。这两个问题在实践中出现频率很高数据不需要全排序只需要维护一个容量为K的堆。最后说说我个人写排序过程中踩过的坑。我记得刚接触归并排序时总想着在拆分的函数里直接合并结果每次递归都新建了临时数组空间开销剧增性能一塌糊涂。后来理解了“分离拆分与合并”这个分工思路代码一眼清晰。这是我学排序收获最大的一个体验排序算法看似是死代码实际上每一处的代码组织方式都受到时间空间复杂度目标的牵制想通这个很多代码就自然能写出来。还有一个小经验面试中如果要求写排序不要一上来就写快排。先和面试官确认清楚数据规模、稳定性要求、是否原地排序再选择算法这本身就是给面试官留下好印象的关键。工程里也一样没有最好只有最合适的排序方案。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
