1. 为什么我要把408内部排序算法重新拆一遍每年到了备考中后期总有人问我同一个问题内部排序这一章到底该怎么学。教材上八大排序一字排开每个都给一段伪代码看完感觉都懂了合上书自己写却一个都写不利索。我当年第一次啃这块内容的时候也是这样冒泡和插入混着写归并的合并逻辑和快排的分区逻辑搅在一起考场上手写代码直接卡壳。后来我换了个思路不再按教材顺序一个个背而是按“这个算法到底在解决什么子问题”来重新归类把每个算法的核心循环、边界条件、稳定性来源全部拆开揉碎情况才彻底好转。这篇内容就是那次重新梳理的完整产物。它面向的是正在准备计算机专业统考、需要把内部排序从“看得懂”推进到“写得出、改得对、分析得清”的读者也适合已经工作但想回头补一补基础算法功底的朋友。我会把八大内部排序——直接插入、折半插入、希尔、冒泡、快速、简单选择、堆、归并外加基数排序这个常被单独拎出来的非比较类算法——逐个拆解重点讲清楚三件事代码为什么这么写、边界为什么这么卡、复杂度分析里的那些“最好最坏平均”到底从哪来。所有代码我都会给出可直接运行的精细版本而不是教材上那种省略了细节的伪代码。需要先说明一点标题里说的“简单分析”不是指内容浅而是指我尽量不用复杂的数学推导去吓人能用一句大白话讲明白的绝不上公式。但该有的严谨一点不少比如堆调整的下沉边界、归并的临时数组下标、快排的递归终止条件这些地方恰恰是手写代码最容易翻车的位置我会重点标注。下面进入正题。2. 整体设计思路按“子问题”而不是按“教材顺序”来组织2.1 八大排序其实只解决三类子问题我后来发现把八个算法按教材章节顺序去记大脑里是一团乱麻但如果按它们解决的子问题来分立刻清爽很多。第一类是逐步扩大有序区代表是插入排序家族直接插入、折半插入、希尔核心动作是“把当前元素插到前面已经有序的序列里的正确位置”。第二类是逐步确定极值位置代表是选择排序家族简单选择、堆排序核心动作是“每一趟从无序区里挑出最大或最小放到它最终该在的位置”。第三类是分而治之再合并代表是归并排序和快速排序一个先切再合一个先分再治。这个分类的意义在于同一类算法它们的代码骨架高度相似你只要吃透一个另外几个就是换汤不换药。比如你彻底搞懂了直接插入的“挪位再落座”折半插入只是把“找位置”的方式从顺序比较换成二分查找挪位的逻辑一模一样。再比如你搞懂了简单选择的“每趟选最小”堆排序只是把“选最小”这个动作从线性扫描优化成了堆顶弹出。这种组织方式让我在复习时省了大量重复记忆的成本。2.2 为什么稳定性要单独拎出来讲统考里稳定性是个高频考点但很多人只背结论“插入稳定、选择不稳定、快排不稳定、归并稳定”却说不清为什么。我的做法是每讲一个算法都追问一句“相等的两个元素在排序过程中有没有可能被交换到彼此前面”。这个追问比背表格有用得多。比如简单选择排序它每趟要把最小值和无序区第一个位置交换如果这个最小值恰好和某个相等元素隔着一段距离交换就会破坏相对顺序这就是它不稳定的根源。理解了这一点你甚至能自己构造出破坏稳定性的具体例子考试出选择题时根本不用回忆。2.3 代码风格上的取舍可读性优先于极致精简网上流传很多“一行快排”“三行归并”的写法看着很爽但对备考和面试手写极不友好。我的原则是变量命名要能自解释循环边界要显式写出关键步骤加注释。比如快排的分区函数我会明确用pivot、left、right三个变量而不是用i、j到处飞。这样写出来的代码虽然长一点但你在纸上默写时不容易丢边界调试时也一眼能看出问题在哪。下面所有代码都遵循这个风格你可以直接拿去跑也可以照着默写。3. 插入排序家族从“挪位落座”到“缩小增量”3.1 直接插入排序理解“哨兵”和“挪位”两个关键动作直接插入排序的思想特别像打扑克摸牌你手里已经有一把排好的牌新摸一张就从右往左比比它大的都往右挪一格直到找到合适位置插进去。代码实现上有两个细节值得说。第一个是从后往前比较这保证了边比较边挪位一趟就能完成不需要额外的临时数组。第二个是哨兵技巧教材里常把数组第0位留空当哨兵存当前要插入的元素这样内层循环就不用每次判断下标是否越界少一个条件判断。不过实际写代码时用普通变量存待插入值也完全够用哨兵更多是考试里的一种写法约定。void insertionSort(int a[], int n) { for (int i 1; i n; i) { int key a[i]; // 待插入元素 int j i - 1; while (j 0 a[j] key) { // 严格大于才挪保证稳定 a[j 1] a[j]; j--; } a[j 1] key; // 落座 } }注意内层条件写的是a[j] key而不是。这个细节直接决定了稳定性遇到相等元素时停止挪动待插入元素落在相等元素的右边相对顺序得以保留。如果你写成相等元素也会被挪到后面稳定性就破坏了。这种“一个符号决定性质”的地方正是手写代码时最该盯紧的。复杂度方面最好情况是原序列已经有序内层循环一次都不进总共比较 n-1 次时间复杂度 O(n)最坏是逆序第 i 趟要挪 i 次总挪动次数约 n²/2O(n²)平均下来也是 O(n²)。空间上只用了常数个辅助变量O(1)。它适合小规模或者基本有序的数据这也是为什么很多库函数在数据量很小时会退化成插入排序。3.2 折半插入排序把“找位置”从线性换成二分折半插入的改进点非常聚焦既然前面已经是有序区那找插入位置何必一个个比直接二分查找不就行了。这样比较次数从 O(n) 降到 O(log n)但注意挪位的次数一点没少因为数组插入本身就要移动元素。所以它的总时间复杂度仍然是 O(n²)改进的只是比较这一项的常数。void binaryInsertionSort(int a[], int n) { for (int i 1; i n; i) { int key a[i]; int low 0, high i - 1; while (low high) { // 找第一个大于key的位置 int mid low (high - low) / 2; if (a[mid] key) high mid - 1; else low mid 1; } for (int j i - 1; j low; j--) // 统一后移 a[j 1] a[j]; a[low] key; } }这里有个容易错的点二分结束后low指向的是第一个大于key的位置也就是key应该插入的位置。为什么因为循环里当a[mid] key时我们让low mid 1等于把小于等于key的都划到左边最终low停在第一个严格大于key的地方。这个边界推导我建议你在纸上画一遍比死记结论牢靠。另外由于我们用的是a[mid] key才收缩右边界相等元素会被归到左边插入位置在相等元素之后稳定性得以保持。3.3 希尔排序增量序列是它的灵魂也是它的软肋希尔排序是插入排序的“分组加强版”。它先取一个较大的增量 d把相隔 d 的元素分成一组做插入排序然后逐步缩小 d直到 d1 做最后一次完整插入。这样做的妙处在于前期大增量能让元素大跨度移动快速消除大量逆序对后期小增量时序列已经“基本有序”插入排序在基本有序时接近 O(n)整体效率大幅提升。void shellSort(int a[], int n) { for (int gap n / 2; gap 0; gap / 2) { // 经典折半增量 for (int i gap; i n; i) { int key a[i]; int j i - gap; while (j 0 a[j] key) { a[j gap] a[j]; j - gap; } a[j gap] key; } } }这段代码其实就是把直接插入的“1”全部换成了“gap”理解了一个另一个自然通。但希尔排序有个必须记住的结论它的时间复杂度依赖于增量序列的选择至今没有统一的最优证明。折半增量最坏能到 O(n²)而 Hibbard 增量1, 3, 7, 15...能到 O(n^1.5)。考试里如果问希尔排序的时间复杂度稳妥的回答是“与增量序列有关最坏可到 O(n²)平均优于直接插入”。另外希尔排序是不稳定的因为相同元素可能被分到不同组跨组移动会打乱相对顺序。这一点很多人会忽略因为插入排序本身是稳定的容易想当然认为它的加强版也稳定。4. 交换排序家族冒泡的稳与快排的险4.1 冒泡排序一个 flag 就能救回最好情况冒泡排序每趟把最大的“冒”到末尾思路直白。但教材版本常常不带优化导致即使序列已经有序还要傻傻跑完 n 趟。加一个swapped标志一旦某趟没有发生交换就说明已经有序直接退出最好情况就能降到 O(n)。void bubbleSort(int a[], int n) { for (int i 0; i n - 1; i) { int swapped 0; for (int j 0; j n - 1 - i; j) { if (a[j] a[j 1]) { int t a[j]; a[j] a[j 1]; a[j 1] t; swapped 1; } } if (!swapped) break; // 本趟无交换已有序 } }内层循环的上界是n - 1 - i因为每趟结束后末尾 i 个元素已经就位不用再比。条件用a[j] a[j 1]严格大于才交换相等不换所以冒泡是稳定的。它的交换次数等于序列的逆序对数这个性质在有些题目里会用到。实际工程中冒泡几乎不用因为交换操作太频繁但作为理解“相邻比较交换”这一基本范式的入门算法它的教学价值很高。4.2 快速排序分区函数是全部难点所在快排是内部排序里平均性能最好的比较类算法平均 O(n log n)但最坏会退化到 O(n²)。它的核心就两件事选基准和分区。分区做得好不好直接决定递归树是否平衡。教材最常用的是取第一个元素作基准配合左右双指针向中间靠拢的写法。int partition(int a[], int low, int high) { int pivot a[low]; // 取第一个作基准 while (low high) { while (low high a[high] pivot) high--; a[low] a[high]; // 右边小的填到左边空位 while (low high a[low] pivot) low; a[high] a[low]; // 左边大的填到右边空位 } a[low] pivot; // 基准归位 return low; } void quickSort(int a[], int low, int high) { if (low high) { int p partition(a, low, high); quickSort(a, low, p - 1); quickSort(a, p 1, high); } }这段分区代码用的是“挖坑填数”法先把基准挖出来存到pivotlow位置就成了一个坑然后从右往左找比基准小的填进左坑从左往右找比基准大的填进右坑最后把基准填回相遇点。整个过程不需要额外的交换函数写起来紧凑。但有两个坑必须注意内层两个 while 的条件里low high不能省否则指针会越界比较符号用和是为了让等于基准的元素留在原地避免死循环。快排不稳定因为分区时的远距离交换会打乱相等元素的相对顺序。最坏情况出现在每次选的基准都是当前区间的最大或最小值比如原序列已经有序且取首元素作基准此时递归深度达到 n退化为 O(n²)。工程上通常用“三数取中”或随机选基准来规避考试里如果问如何改进答这两点即可。4.3 快排递归深度与栈空间的关系很多人只记快排空间复杂度 O(log n)但说不清为什么。快排的额外空间来自递归调用栈栈的深度等于递归树的深度。平均情况下递归树比较平衡深度约 log₂n最坏情况下树退化成链深度 n空间就是 O(n)。所以严格说快排空间复杂度是“平均 O(log n)最坏 O(n)”。这个细节在选择题里经常挖坑比如问“快速排序在最坏情况下的空间复杂度”答案应该是 O(n) 而不是 O(log n)。我建议你把递归树画出来对照看比背结论直观。5. 选择排序家族从线性扫描到堆的跃迁5.1 简单选择排序交换次数最少的比较类算法简单选择的逻辑是每趟从未排序区里找出最小元素和无序区第一个位置交换。它的比较次数固定为 n(n-1)/2和初始序列无关所以最好最坏平均都是 O(n²)。但它有个独特优点交换次数最多 n-1 次是所有比较类排序里交换最少的。当元素交换成本很高比如元素很大、移动代价大时这个特性有价值。void selectionSort(int a[], int n) { for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) if (a[j] a[minIdx]) minIdx j; if (minIdx ! i) { int t a[i]; a[i] a[minIdx]; a[minIdx] t; } } }它不稳定的原因就在那个交换动作上。举个例子序列[5a, 5b, 2]第一趟找最小值 2和第一个位置 5a 交换得到[2, 5b, 5a]两个 5 的相对顺序反了。这个例子我建议记住考试出稳定性判断题时直接套。5.2 堆排序下沉调整是唯一需要吃透的操作堆排序把“每趟选最大”这个动作从线性扫描优化成了 O(log n) 的堆调整整体 O(n log n)。它分两步先自底向上建大根堆然后反复把堆顶和末尾交换、堆长度减一、对新堆顶做下沉。整个算法里下沉sift down是唯一的核心操作建堆和排序都靠它。void siftDown(int a[], int start, int end) { int root start; while (2 * root 1 end) { // 有左孩子 int child 2 * root 1; if (child 1 end a[child 1] a[child]) child; // 选较大的孩子 if (a[root] a[child]) { int t a[root]; a[root] a[child]; a[child] t; root child; // 继续往下沉 } else break; } } void heapSort(int a[], int n) { for (int i n / 2 - 1; i 0; i--) // 建堆从最后一个非叶结点开始 siftDown(a, i, n - 1); for (int i n - 1; i 0; i--) { int t a[0]; a[0] a[i]; a[i] t; // 堆顶换到末尾 siftDown(a, 0, i - 1); // 剩余部分重新下沉 } }建堆为什么从n/2 - 1开始因为下标大于n/2 - 1的结点全是叶子叶子天然满足堆性质不用调整。这个下标的推导基于完全二叉树的性质最后一个非叶结点是最后一个结点的父结点即(n-1-1)/2 n/2 - 1。建堆的总时间不是 O(n log n) 而是 O(n)因为越靠近底层的结点越多但下沉高度越小求和后收敛到线性这个结论考试常考值得单独记。堆排序不稳定因为堆顶和末尾的交换是远距离的。它的空间复杂度 O(1)是少数能在原地完成且最坏也保证 O(n log n) 的算法适合对最坏情况有要求的场景。缺点是常数因子较大且访问模式对缓存不友好实际跑起来往往不如快排快。6. 归并与基数分治合并与非比较思路6.1 归并排序合并函数写对了整个算法就对了归并排序是典型的分治把序列对半切分别排好再合并两个有序段。递归部分很简单难点全在合并函数上。合并需要一块和原数组等大的临时空间用双指针从两段头部开始比小的先放进临时数组最后把临时数组拷回原数组。void merge(int a[], int tmp[], int left, int mid, int right) { int i left, j mid 1, k left; while (i mid j right) { if (a[i] a[j]) tmp[k] a[i]; // 取等号保证稳定 else tmp[k] a[j]; } while (i mid) tmp[k] a[i]; while (j right) tmp[k] a[j]; for (int p left; p right; p) a[p] tmp[p]; } void mergeSort(int a[], int tmp[], int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(a, tmp, left, mid); mergeSort(a, tmp, mid 1, right); merge(a, tmp, left, mid, right); }合并时a[i] a[j]取等号保证左边相等元素先入临时数组稳定性得以保持。归并的时间复杂度稳定在 O(n log n)最好最坏平均都一样这是它相对快排的优势。空间复杂度 O(n)因为需要临时数组。它适合外部排序场景也适合链表排序链表归并不需要额外空间只需改指针。考试里常问“归并排序的递归深度”答案是 ⌈log₂n⌉ 1 左右因为每次对半切。6.2 基数排序不比较也能排但限制条件要记牢基数排序属于分配式排序不靠元素间比较。它按位从低位到高位每一位做一次稳定的桶分配和收集。因为每一位的分配是稳定的低位排好的顺序在高位相同时得以保留最终整体有序。void radixSort(int a[], int n) { int maxVal a[0]; for (int i 1; i n; i) if (a[i] maxVal) maxVal a[i]; int exp 1; int* tmp (int*)malloc(sizeof(int) * n); int count[10]; while (maxVal / exp 0) { memset(count, 0, sizeof(count)); for (int i 0; i n; i) count[(a[i] / exp) % 10]; for (int i 1; i 10; i) count[i] count[i - 1]; // 前缀和定位置 for (int i n - 1; i 0; i--) { // 倒序保证稳定 int d (a[i] / exp) % 10; tmp[--count[d]] a[i]; } for (int i 0; i n; i) a[i] tmp[i]; exp * 10; } free(tmp); }这里有两个关键点。第一收集时必须从后往前遍历原数组配合前缀和递减才能保证同一桶内元素的相对顺序不变这是稳定性的来源。第二基数排序的时间复杂度是 O(d(nr))d 是最大位数r 是基数十进制就是 10。它适合位数不多、数据量大的整数排序但对浮点数和负数需要额外处理通用性不如比较类排序。7. 常见问题与排查技巧实录7.1 手写代码时最容易翻车的五个边界我在帮人看代码和自测时发现错误高度集中在几个固定位置。下面这张表是我整理的“高频翻车点速查”建议默写前扫一眼。算法高频错误正确做法直接插入内层条件写成a[j] key用保稳定相等即停折半插入二分后插入位置写成high应为low它是第一个大于 key 的位置快速排序内层 while 漏写low high必须双条件防越界死循环堆排序建堆起点写成n/2应为n/2 - 1最后一个非叶结点归并排序合并时临时数组下标从 0 开始应与原数组区间对齐从 left 开始这些错误有个共同特点单看代码逻辑都对但边界差一格跑小数据可能碰巧对跑大数据立刻暴露。我的建议是每次写完用长度为 0、1、2 的极端数组各测一遍再用手工构造的逆序、全等、含重复元素的数组测一遍基本能覆盖大部分边界问题。7.2 复杂度分析里那些容易记混的结论很多人背复杂度表时把几个特殊结论记串了。我整理了一份“反直觉结论清单”这些都是考试爱考、日常容易想当然的点。快速排序最坏空间是 O(n) 不是 O(log n)建堆的总时间是 O(n) 不是 O(n log n)希尔排序的时间复杂度没有统一答案取决于增量序列简单选择排序的比较次数与初始序列无关恒为 n(n-1)/2冒泡排序的交换次数等于逆序对数。把这些单独拎出来记比混在大表里背效果好得多。7.3 稳定性判断的通用方法与其背“谁稳定谁不稳定”不如掌握一个判断套路看算法有没有远距离交换或跨组移动。插入、冒泡、归并都是相邻或顺序移动相等元素不会被越过所以稳定简单选择、快排、堆排都存在把远处元素换到前面的动作相等元素可能被越过所以不稳定希尔排序因为分组相等元素可能被分到不同组也不稳定。基数排序因为每一位收集时保持顺序所以稳定。用这个套路去推即使考场上忘了结论也能现场判断。8. 我在实际刷题和调试中的几点体会最后分享几个纯个人经验。第一不要一上来就追求默写完整代码先把每个算法的核心循环单独拎出来写比如只写快排的 partition、只写堆的 siftDown写熟这些“零件”再组装比整段硬背效率高得多。第二用打印中间状态的方式调试比如在每趟排序后把数组打出来对照教材上的过程图看哪一趟开始不对问题就出在哪一趟的逻辑里比盯着代码空想快十倍。第三同一类算法对比着写比如把直接插入和希尔放一起写你会发现只差一个 gap 变量这种对比记忆特别牢固。还有个小技巧准备一张 A4 纸把八个算法的“核心动作一句话”和“一个最简代码骨架”手写一遍贴在桌前每天扫一眼。坚持一周手写代码的流畅度会有明显变化。这个方法我自己用过也推荐给过几个一起备考的朋友反馈都不错。排序这块内容说到底就是“理解子问题 盯紧边界 反复手写”没有捷径但路径清晰。 
长河君 · 2026/10/27 5:32:29 · 阅读 1.2k 408内部排序算法拆解：从理解到手写，掌握八大排序核心逻辑
1. 为什么我要把408内部排序算法重新拆一遍每年到了备考中后期总有人问我同一个问题内部排序这一章到底该怎么学。教材上八大排序一字排开每个都给一段伪代码看完感觉都懂了合上书自己写却一个都写不利索。我当年第一次啃这块内容的时候也是这样冒泡和插入混着写归并的合并逻辑和快排的分区逻辑搅在一起考场上手写代码直接卡壳。后来我换了个思路不再按教材顺序一个个背而是按“这个算法到底在解决什么子问题”来重新归类把每个算法的核心循环、边界条件、稳定性来源全部拆开揉碎情况才彻底好转。这篇内容就是那次重新梳理的完整产物。它面向的是正在准备计算机专业统考、需要把内部排序从“看得懂”推进到“写得出、改得对、分析得清”的读者也适合已经工作但想回头补一补基础算法功底的朋友。我会把八大内部排序——直接插入、折半插入、希尔、冒泡、快速、简单选择、堆、归并外加基数排序这个常被单独拎出来的非比较类算法——逐个拆解重点讲清楚三件事代码为什么这么写、边界为什么这么卡、复杂度分析里的那些“最好最坏平均”到底从哪来。所有代码我都会给出可直接运行的精细版本而不是教材上那种省略了细节的伪代码。需要先说明一点标题里说的“简单分析”不是指内容浅而是指我尽量不用复杂的数学推导去吓人能用一句大白话讲明白的绝不上公式。但该有的严谨一点不少比如堆调整的下沉边界、归并的临时数组下标、快排的递归终止条件这些地方恰恰是手写代码最容易翻车的位置我会重点标注。下面进入正题。2. 整体设计思路按“子问题”而不是按“教材顺序”来组织2.1 八大排序其实只解决三类子问题我后来发现把八个算法按教材章节顺序去记大脑里是一团乱麻但如果按它们解决的子问题来分立刻清爽很多。第一类是逐步扩大有序区代表是插入排序家族直接插入、折半插入、希尔核心动作是“把当前元素插到前面已经有序的序列里的正确位置”。第二类是逐步确定极值位置代表是选择排序家族简单选择、堆排序核心动作是“每一趟从无序区里挑出最大或最小放到它最终该在的位置”。第三类是分而治之再合并代表是归并排序和快速排序一个先切再合一个先分再治。这个分类的意义在于同一类算法它们的代码骨架高度相似你只要吃透一个另外几个就是换汤不换药。比如你彻底搞懂了直接插入的“挪位再落座”折半插入只是把“找位置”的方式从顺序比较换成二分查找挪位的逻辑一模一样。再比如你搞懂了简单选择的“每趟选最小”堆排序只是把“选最小”这个动作从线性扫描优化成了堆顶弹出。这种组织方式让我在复习时省了大量重复记忆的成本。2.2 为什么稳定性要单独拎出来讲统考里稳定性是个高频考点但很多人只背结论“插入稳定、选择不稳定、快排不稳定、归并稳定”却说不清为什么。我的做法是每讲一个算法都追问一句“相等的两个元素在排序过程中有没有可能被交换到彼此前面”。这个追问比背表格有用得多。比如简单选择排序它每趟要把最小值和无序区第一个位置交换如果这个最小值恰好和某个相等元素隔着一段距离交换就会破坏相对顺序这就是它不稳定的根源。理解了这一点你甚至能自己构造出破坏稳定性的具体例子考试出选择题时根本不用回忆。2.3 代码风格上的取舍可读性优先于极致精简网上流传很多“一行快排”“三行归并”的写法看着很爽但对备考和面试手写极不友好。我的原则是变量命名要能自解释循环边界要显式写出关键步骤加注释。比如快排的分区函数我会明确用pivot、left、right三个变量而不是用i、j到处飞。这样写出来的代码虽然长一点但你在纸上默写时不容易丢边界调试时也一眼能看出问题在哪。下面所有代码都遵循这个风格你可以直接拿去跑也可以照着默写。3. 插入排序家族从“挪位落座”到“缩小增量”3.1 直接插入排序理解“哨兵”和“挪位”两个关键动作直接插入排序的思想特别像打扑克摸牌你手里已经有一把排好的牌新摸一张就从右往左比比它大的都往右挪一格直到找到合适位置插进去。代码实现上有两个细节值得说。第一个是从后往前比较这保证了边比较边挪位一趟就能完成不需要额外的临时数组。第二个是哨兵技巧教材里常把数组第0位留空当哨兵存当前要插入的元素这样内层循环就不用每次判断下标是否越界少一个条件判断。不过实际写代码时用普通变量存待插入值也完全够用哨兵更多是考试里的一种写法约定。void insertionSort(int a[], int n) { for (int i 1; i n; i) { int key a[i]; // 待插入元素 int j i - 1; while (j 0 a[j] key) { // 严格大于才挪保证稳定 a[j 1] a[j]; j--; } a[j 1] key; // 落座 } }注意内层条件写的是a[j] key而不是。这个细节直接决定了稳定性遇到相等元素时停止挪动待插入元素落在相等元素的右边相对顺序得以保留。如果你写成相等元素也会被挪到后面稳定性就破坏了。这种“一个符号决定性质”的地方正是手写代码时最该盯紧的。复杂度方面最好情况是原序列已经有序内层循环一次都不进总共比较 n-1 次时间复杂度 O(n)最坏是逆序第 i 趟要挪 i 次总挪动次数约 n²/2O(n²)平均下来也是 O(n²)。空间上只用了常数个辅助变量O(1)。它适合小规模或者基本有序的数据这也是为什么很多库函数在数据量很小时会退化成插入排序。3.2 折半插入排序把“找位置”从线性换成二分折半插入的改进点非常聚焦既然前面已经是有序区那找插入位置何必一个个比直接二分查找不就行了。这样比较次数从 O(n) 降到 O(log n)但注意挪位的次数一点没少因为数组插入本身就要移动元素。所以它的总时间复杂度仍然是 O(n²)改进的只是比较这一项的常数。void binaryInsertionSort(int a[], int n) { for (int i 1; i n; i) { int key a[i]; int low 0, high i - 1; while (low high) { // 找第一个大于key的位置 int mid low (high - low) / 2; if (a[mid] key) high mid - 1; else low mid 1; } for (int j i - 1; j low; j--) // 统一后移 a[j 1] a[j]; a[low] key; } }这里有个容易错的点二分结束后low指向的是第一个大于key的位置也就是key应该插入的位置。为什么因为循环里当a[mid] key时我们让low mid 1等于把小于等于key的都划到左边最终low停在第一个严格大于key的地方。这个边界推导我建议你在纸上画一遍比死记结论牢靠。另外由于我们用的是a[mid] key才收缩右边界相等元素会被归到左边插入位置在相等元素之后稳定性得以保持。3.3 希尔排序增量序列是它的灵魂也是它的软肋希尔排序是插入排序的“分组加强版”。它先取一个较大的增量 d把相隔 d 的元素分成一组做插入排序然后逐步缩小 d直到 d1 做最后一次完整插入。这样做的妙处在于前期大增量能让元素大跨度移动快速消除大量逆序对后期小增量时序列已经“基本有序”插入排序在基本有序时接近 O(n)整体效率大幅提升。void shellSort(int a[], int n) { for (int gap n / 2; gap 0; gap / 2) { // 经典折半增量 for (int i gap; i n; i) { int key a[i]; int j i - gap; while (j 0 a[j] key) { a[j gap] a[j]; j - gap; } a[j gap] key; } } }这段代码其实就是把直接插入的“1”全部换成了“gap”理解了一个另一个自然通。但希尔排序有个必须记住的结论它的时间复杂度依赖于增量序列的选择至今没有统一的最优证明。折半增量最坏能到 O(n²)而 Hibbard 增量1, 3, 7, 15...能到 O(n^1.5)。考试里如果问希尔排序的时间复杂度稳妥的回答是“与增量序列有关最坏可到 O(n²)平均优于直接插入”。另外希尔排序是不稳定的因为相同元素可能被分到不同组跨组移动会打乱相对顺序。这一点很多人会忽略因为插入排序本身是稳定的容易想当然认为它的加强版也稳定。4. 交换排序家族冒泡的稳与快排的险4.1 冒泡排序一个 flag 就能救回最好情况冒泡排序每趟把最大的“冒”到末尾思路直白。但教材版本常常不带优化导致即使序列已经有序还要傻傻跑完 n 趟。加一个swapped标志一旦某趟没有发生交换就说明已经有序直接退出最好情况就能降到 O(n)。void bubbleSort(int a[], int n) { for (int i 0; i n - 1; i) { int swapped 0; for (int j 0; j n - 1 - i; j) { if (a[j] a[j 1]) { int t a[j]; a[j] a[j 1]; a[j 1] t; swapped 1; } } if (!swapped) break; // 本趟无交换已有序 } }内层循环的上界是n - 1 - i因为每趟结束后末尾 i 个元素已经就位不用再比。条件用a[j] a[j 1]严格大于才交换相等不换所以冒泡是稳定的。它的交换次数等于序列的逆序对数这个性质在有些题目里会用到。实际工程中冒泡几乎不用因为交换操作太频繁但作为理解“相邻比较交换”这一基本范式的入门算法它的教学价值很高。4.2 快速排序分区函数是全部难点所在快排是内部排序里平均性能最好的比较类算法平均 O(n log n)但最坏会退化到 O(n²)。它的核心就两件事选基准和分区。分区做得好不好直接决定递归树是否平衡。教材最常用的是取第一个元素作基准配合左右双指针向中间靠拢的写法。int partition(int a[], int low, int high) { int pivot a[low]; // 取第一个作基准 while (low high) { while (low high a[high] pivot) high--; a[low] a[high]; // 右边小的填到左边空位 while (low high a[low] pivot) low; a[high] a[low]; // 左边大的填到右边空位 } a[low] pivot; // 基准归位 return low; } void quickSort(int a[], int low, int high) { if (low high) { int p partition(a, low, high); quickSort(a, low, p - 1); quickSort(a, p 1, high); } }这段分区代码用的是“挖坑填数”法先把基准挖出来存到pivotlow位置就成了一个坑然后从右往左找比基准小的填进左坑从左往右找比基准大的填进右坑最后把基准填回相遇点。整个过程不需要额外的交换函数写起来紧凑。但有两个坑必须注意内层两个 while 的条件里low high不能省否则指针会越界比较符号用和是为了让等于基准的元素留在原地避免死循环。快排不稳定因为分区时的远距离交换会打乱相等元素的相对顺序。最坏情况出现在每次选的基准都是当前区间的最大或最小值比如原序列已经有序且取首元素作基准此时递归深度达到 n退化为 O(n²)。工程上通常用“三数取中”或随机选基准来规避考试里如果问如何改进答这两点即可。4.3 快排递归深度与栈空间的关系很多人只记快排空间复杂度 O(log n)但说不清为什么。快排的额外空间来自递归调用栈栈的深度等于递归树的深度。平均情况下递归树比较平衡深度约 log₂n最坏情况下树退化成链深度 n空间就是 O(n)。所以严格说快排空间复杂度是“平均 O(log n)最坏 O(n)”。这个细节在选择题里经常挖坑比如问“快速排序在最坏情况下的空间复杂度”答案应该是 O(n) 而不是 O(log n)。我建议你把递归树画出来对照看比背结论直观。5. 选择排序家族从线性扫描到堆的跃迁5.1 简单选择排序交换次数最少的比较类算法简单选择的逻辑是每趟从未排序区里找出最小元素和无序区第一个位置交换。它的比较次数固定为 n(n-1)/2和初始序列无关所以最好最坏平均都是 O(n²)。但它有个独特优点交换次数最多 n-1 次是所有比较类排序里交换最少的。当元素交换成本很高比如元素很大、移动代价大时这个特性有价值。void selectionSort(int a[], int n) { for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) if (a[j] a[minIdx]) minIdx j; if (minIdx ! i) { int t a[i]; a[i] a[minIdx]; a[minIdx] t; } } }它不稳定的原因就在那个交换动作上。举个例子序列[5a, 5b, 2]第一趟找最小值 2和第一个位置 5a 交换得到[2, 5b, 5a]两个 5 的相对顺序反了。这个例子我建议记住考试出稳定性判断题时直接套。5.2 堆排序下沉调整是唯一需要吃透的操作堆排序把“每趟选最大”这个动作从线性扫描优化成了 O(log n) 的堆调整整体 O(n log n)。它分两步先自底向上建大根堆然后反复把堆顶和末尾交换、堆长度减一、对新堆顶做下沉。整个算法里下沉sift down是唯一的核心操作建堆和排序都靠它。void siftDown(int a[], int start, int end) { int root start; while (2 * root 1 end) { // 有左孩子 int child 2 * root 1; if (child 1 end a[child 1] a[child]) child; // 选较大的孩子 if (a[root] a[child]) { int t a[root]; a[root] a[child]; a[child] t; root child; // 继续往下沉 } else break; } } void heapSort(int a[], int n) { for (int i n / 2 - 1; i 0; i--) // 建堆从最后一个非叶结点开始 siftDown(a, i, n - 1); for (int i n - 1; i 0; i--) { int t a[0]; a[0] a[i]; a[i] t; // 堆顶换到末尾 siftDown(a, 0, i - 1); // 剩余部分重新下沉 } }建堆为什么从n/2 - 1开始因为下标大于n/2 - 1的结点全是叶子叶子天然满足堆性质不用调整。这个下标的推导基于完全二叉树的性质最后一个非叶结点是最后一个结点的父结点即(n-1-1)/2 n/2 - 1。建堆的总时间不是 O(n log n) 而是 O(n)因为越靠近底层的结点越多但下沉高度越小求和后收敛到线性这个结论考试常考值得单独记。堆排序不稳定因为堆顶和末尾的交换是远距离的。它的空间复杂度 O(1)是少数能在原地完成且最坏也保证 O(n log n) 的算法适合对最坏情况有要求的场景。缺点是常数因子较大且访问模式对缓存不友好实际跑起来往往不如快排快。6. 归并与基数分治合并与非比较思路6.1 归并排序合并函数写对了整个算法就对了归并排序是典型的分治把序列对半切分别排好再合并两个有序段。递归部分很简单难点全在合并函数上。合并需要一块和原数组等大的临时空间用双指针从两段头部开始比小的先放进临时数组最后把临时数组拷回原数组。void merge(int a[], int tmp[], int left, int mid, int right) { int i left, j mid 1, k left; while (i mid j right) { if (a[i] a[j]) tmp[k] a[i]; // 取等号保证稳定 else tmp[k] a[j]; } while (i mid) tmp[k] a[i]; while (j right) tmp[k] a[j]; for (int p left; p right; p) a[p] tmp[p]; } void mergeSort(int a[], int tmp[], int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(a, tmp, left, mid); mergeSort(a, tmp, mid 1, right); merge(a, tmp, left, mid, right); }合并时a[i] a[j]取等号保证左边相等元素先入临时数组稳定性得以保持。归并的时间复杂度稳定在 O(n log n)最好最坏平均都一样这是它相对快排的优势。空间复杂度 O(n)因为需要临时数组。它适合外部排序场景也适合链表排序链表归并不需要额外空间只需改指针。考试里常问“归并排序的递归深度”答案是 ⌈log₂n⌉ 1 左右因为每次对半切。6.2 基数排序不比较也能排但限制条件要记牢基数排序属于分配式排序不靠元素间比较。它按位从低位到高位每一位做一次稳定的桶分配和收集。因为每一位的分配是稳定的低位排好的顺序在高位相同时得以保留最终整体有序。void radixSort(int a[], int n) { int maxVal a[0]; for (int i 1; i n; i) if (a[i] maxVal) maxVal a[i]; int exp 1; int* tmp (int*)malloc(sizeof(int) * n); int count[10]; while (maxVal / exp 0) { memset(count, 0, sizeof(count)); for (int i 0; i n; i) count[(a[i] / exp) % 10]; for (int i 1; i 10; i) count[i] count[i - 1]; // 前缀和定位置 for (int i n - 1; i 0; i--) { // 倒序保证稳定 int d (a[i] / exp) % 10; tmp[--count[d]] a[i]; } for (int i 0; i n; i) a[i] tmp[i]; exp * 10; } free(tmp); }这里有两个关键点。第一收集时必须从后往前遍历原数组配合前缀和递减才能保证同一桶内元素的相对顺序不变这是稳定性的来源。第二基数排序的时间复杂度是 O(d(nr))d 是最大位数r 是基数十进制就是 10。它适合位数不多、数据量大的整数排序但对浮点数和负数需要额外处理通用性不如比较类排序。7. 常见问题与排查技巧实录7.1 手写代码时最容易翻车的五个边界我在帮人看代码和自测时发现错误高度集中在几个固定位置。下面这张表是我整理的“高频翻车点速查”建议默写前扫一眼。算法高频错误正确做法直接插入内层条件写成a[j] key用保稳定相等即停折半插入二分后插入位置写成high应为low它是第一个大于 key 的位置快速排序内层 while 漏写low high必须双条件防越界死循环堆排序建堆起点写成n/2应为n/2 - 1最后一个非叶结点归并排序合并时临时数组下标从 0 开始应与原数组区间对齐从 left 开始这些错误有个共同特点单看代码逻辑都对但边界差一格跑小数据可能碰巧对跑大数据立刻暴露。我的建议是每次写完用长度为 0、1、2 的极端数组各测一遍再用手工构造的逆序、全等、含重复元素的数组测一遍基本能覆盖大部分边界问题。7.2 复杂度分析里那些容易记混的结论很多人背复杂度表时把几个特殊结论记串了。我整理了一份“反直觉结论清单”这些都是考试爱考、日常容易想当然的点。快速排序最坏空间是 O(n) 不是 O(log n)建堆的总时间是 O(n) 不是 O(n log n)希尔排序的时间复杂度没有统一答案取决于增量序列简单选择排序的比较次数与初始序列无关恒为 n(n-1)/2冒泡排序的交换次数等于逆序对数。把这些单独拎出来记比混在大表里背效果好得多。7.3 稳定性判断的通用方法与其背“谁稳定谁不稳定”不如掌握一个判断套路看算法有没有远距离交换或跨组移动。插入、冒泡、归并都是相邻或顺序移动相等元素不会被越过所以稳定简单选择、快排、堆排都存在把远处元素换到前面的动作相等元素可能被越过所以不稳定希尔排序因为分组相等元素可能被分到不同组也不稳定。基数排序因为每一位收集时保持顺序所以稳定。用这个套路去推即使考场上忘了结论也能现场判断。8. 我在实际刷题和调试中的几点体会最后分享几个纯个人经验。第一不要一上来就追求默写完整代码先把每个算法的核心循环单独拎出来写比如只写快排的 partition、只写堆的 siftDown写熟这些“零件”再组装比整段硬背效率高得多。第二用打印中间状态的方式调试比如在每趟排序后把数组打出来对照教材上的过程图看哪一趟开始不对问题就出在哪一趟的逻辑里比盯着代码空想快十倍。第三同一类算法对比着写比如把直接插入和希尔放一起写你会发现只差一个 gap 变量这种对比记忆特别牢固。还有个小技巧准备一张 A4 纸把八个算法的“核心动作一句话”和“一个最简代码骨架”手写一遍贴在桌前每天扫一眼。坚持一周手写代码的流畅度会有明显变化。这个方法我自己用过也推荐给过几个一起备考的朋友反馈都不错。排序这块内容说到底就是“理解子问题 盯紧边界 反复手写”没有捷径但路径清晰。