内部排序这块内容我在带新人和自己做项目复盘的时候反复讲过很多轮。很多人学完数据结构课程考试能默写快排和堆排的伪代码但真让他手写一份能跑、边界不出错、还能说清楚每个参数为什么这么定的实现就开始卡壳。这篇东西就是冲着这个痛点来的把408考纲里那几类内部排序——插入、希尔、冒泡、快速、选择、堆、归并、基数——从算法思路、代码实现、复杂度推导到实际踩坑完整捋一遍。适合正在准备408的考生也适合工作几年后想回头把基础夯实的朋友。代码我全部用C风格写贴近教材和考场习惯每一段都能直接编译运行注释里标清楚关键变量的含义和边界条件你可以直接抄去当模板。1. 内部排序的整体设计思路与选型逻辑1.1 为什么内部排序值得单独拎出来啃内部排序指的是待排序记录全部放在内存里完成的排序过程和外部排序相对。408考纲里明确列出的内部排序算法有插入类直接插入、折半插入、希尔、交换类冒泡、快速、选择类简单选择、堆、归并排序和基数排序。这些算法不是孤立的知识点它们背后是同一套分析框架时间复杂度、空间复杂度、稳定性、适用场景。考试喜欢考对比工程里也确实是按这套框架选型的。我见过不少人背复杂度表背得很熟但一问“为什么希尔排序不稳定”就答不上来。原因在于希尔排序做的是跳跃式插入相同元素可能被分到不同子序列里相对次序在跨组移动时被打乱。这种“为什么”才是真正拉开差距的地方。所以这篇不打算只给结论每个算法的关键设计我都会拆开讲清楚它解决了什么问题、代价是什么。从工程视角看内部排序是所有数据处理的地基。你写业务代码时调用的库函数排序底层往往是多种算法的混合策略比如小数组用插入排序、大数组用快排、递归深度超限切堆排。理解这些单算法的特性才能明白混合策略为什么这么设计。这也是我坚持把每个算法手写一遍的原因——调库调多了人会失去对边界和性能的敏感度。1.2 一张表看清各算法的取舍选型之前先把全局图景摆出来。下面这张表是我自己复习和讲课时用的核心对照表参数都按408的标准定义来算法平均时间最坏时间最好时间空间稳定性适用场景直接插入O(n²)O(n²)O(n)O(1)稳定基本有序、小规模折半插入O(n²)O(n²)O(n)O(1)稳定减少比较次数希尔排序O(n^1.3)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(1)不稳定交换代价大时堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定最坏也要稳归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定要求稳定、外排基数排序O(d(nr))O(d(nr))O(d(nr))O(nr)稳定整数、定长关键字这张表要能自己推出来而不是死记。比如堆排序空间为什么是O(1)因为它原地建堆、原地调整只用了常数个临时变量。归并为什么是O(n)因为合并两个有序段需要一块和原数组等长的辅助空间。每个格子背后都有推导路径后面章节我会逐个展开。1.3 选型的三个判断维度实际选算法时我一般看三件事。第一是数据规模n小于几十的时候插入排序反而快因为常数因子小、没有递归开销这也是很多标准库在小数组上切插入排序的原因。第二是数据初始状态如果数据基本有序插入和冒泡能退化到O(n)而快排在这种输入上如果基准选得不好反而容易退化。第三是稳定性要求只要业务里有多关键字排序的需求比如先按成绩排再按班级排就必须用稳定算法否则前一次排序的结果会被破坏。提示稳定性不是“锦上添花”在多关键字排序场景里是硬需求。判断一个算法稳不稳定看它有没有发生“跨距离交换”。直接插入是相邻挪位所以稳定简单选择是把最小值直接换到前面跨距离交换会破坏稳定性。2. 插入类排序的细节拆解与代码实现2.1 直接插入排序把哨兵用起来直接插入的思路就是打扑克摸牌每次把新牌插到前面已经有序的手牌里合适的位置。教材版本通常用A[0]当哨兵这个设计很值得说。哨兵的作用是省掉内层循环的边界判断——把待插入元素先放到A[0]然后从后往前比较只要A[j]大于哨兵就往后挪一旦遇到不大于的就停因为A[0]本身等于待插入值循环必然在j0处终止不用额外写j1的判断。这是一个用一点空间换掉每次循环一次比较的经典技巧。void InsertSort(int A[], int n) { int i, j; for (i 2; i n; i) { // A[1]视为已排好从第2个开始 if (A[i] A[i-1]) { // 只有逆序才需要插入 A[0] A[i]; // 哨兵暂存 for (j i-1; A[j] A[0]; j--) A[j1] A[j]; // 后移 A[j1] A[0]; // 落位 } } }这段代码有几个细节容易写错。第一数组下标从1开始用A[0]专门留给哨兵所以循环从i2起。第二外层那个if判断不是可有可无的优化当A[i]已经大于等于前一个元素时直接跳过这让最好情况原本有序退化成O(n)而不是O(n²)。第三内层for循环结束后j指向的是第一个不大于哨兵的位置所以落位是A[j1]而不是A[j]这个off-by-one是手写时最高频的错误。复杂度推导比较次数最好n-1次最坏约n²/2次移动次数最坏约n²/2次。平均下来O(n²)。空间只用了哨兵一个位置O(1)。稳定性方面内层条件是A[j] A[0]才后移等于时停下所以相等元素不会越过彼此稳定。2.2 折半插入比较次数降了移动次数没降折半插入的动机很直接前面那段已经有序了找插入位置何必一个个比直接二分。这样比较次数从O(n²)降到O(nlog₂n)但注意移动次数还是O(n²)因为找到位置后还是要把后面的元素整体后移。所以总时间复杂度仍然是O(n²)它优化的是比较这个动作不是移动。void BinaryInsertSort(int A[], int n) { int i, j, low, high, mid; for (i 2; i n; i) { A[0] A[i]; low 1; high i - 1; while (low high) { // 找插入位置 mid (low high) / 2; if (A[mid] A[0]) high mid - 1; else low mid 1; // 相等时往右半区找保证稳定 } for (j i-1; j high1; j--) A[j1] A[j]; // 统一后移 A[high1] A[0]; } }这里的关键在else分支当A[mid]等于哨兵时我们让lowmid1也就是继续往右半区找这样最终插入位置会在所有相等元素的右边保证稳定性。如果写成A[mid] A[0]时highmid-1就会插到相等元素左边稳定性就破坏了。这个细节考试爱考实际写代码也常错。注意折半插入的循环结束后插入位置是high1后移的起点也是high1。很多人写成low虽然此时代码里low和high1数值上相等但语义上high1才是“最后一个不大于哨兵的位置的右边”理解清楚这个语义比记结论重要。2.3 希尔排序增量序列是灵魂希尔排序是把序列按增量d分成若干子序列对每个子序列做直接插入然后缩小增量重复直到d1。它的巧妙之处在于前期用大增量让元素大跨度移动快速把小的元素送到前面、大的送到后面让序列逐渐变得“基本有序”最后一趟d1的插入排序面对的已经是一个接近有序的序列效率很高。void ShellSort(int A[], int n) { int d, i, j; for (d n/2; d 1; d d/2) { // 增量每次折半 for (i d1; i n; i) { if (A[i] A[i-d]) { A[0] A[i]; for (j i-d; j 0 A[j] A[0]; j - d) A[jd] A[j]; A[jd] A[0]; } } } }增量序列的选择直接影响性能。教材常用n/2折半但严格说这个序列不是最优的最坏仍可能到O(n²)。工程上更常用的是Hibbard序列2^k-1或Sedgewick序列能把最坏复杂度压到O(n^1.5)甚至更好。408考试按教材的折半增量写就行但你要知道这不是唯一选择。希尔排序为什么不稳定举个例子序列[3, 3, 1]增量d2时第一个3和1比较1换到前面两个3的相对位置就可能被打乱。本质原因是相等元素可能被分到不同的子序列跨组移动时次序无法保证。空间上只用了哨兵O(1)。3. 交换类排序从冒泡到快排的分治跃迁3.1 冒泡排序提前终止标志是加分项冒泡每一趟把最大的元素“冒”到末尾。基础版两层循环固定跑n-1趟但加一个flag记录本趟有没有发生交换如果一趟下来没交换说明已经有序直接退出。这个优化让最好情况原本有序从O(n²)降到O(n)。void BubbleSort(int A[], int n) { int i, j, flag; for (i 0; i n-1; i) { flag 0; for (j n-1; j i; j--) { // 从后往前冒小的往前 if (A[j-1] A[j]) { int t A[j-1]; A[j-1] A[j]; A[j] t; flag 1; } } if (flag 0) return; // 本趟无交换已有序 } }注意这里内层是从后往前扫把小的往前冒这样每趟结束后位置i及之前已经是最小的i1个元素。如果从前往后扫把大的往后冒逻辑对称但循环边界要相应调整。两种写法都对关键是边界别写错。冒泡是稳定的因为只有严格大于才交换相等不换。3.2 快速排序划分是核心基准选择是命门快排是分治的典型选一个基准把序列划分成左边都不大于基准、右边都不小于基准然后递归处理两边。它的平均性能是所有内部排序里最好的常数因子小、缓存友好所以是通用场景的首选。但最坏情况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 pivotpos Partition(A, low, high); QuickSort(A, low, pivotpos - 1); QuickSort(A, pivotpos 1, high); } }这段划分代码用的是“挖坑填数”法比交换法少一些赋值操作。理解它的关键是pivot暂存后A[low]就是一个坑右边找到小的填进来然后A[high]变成新坑左边找到大的填进去如此往复最后lowhigh时把pivot填回。整个过程原地完成空间只花在递归栈上。基准选择直接决定性能。固定选第一个元素在有序输入上会退化改进办法有三随机选基准、三数取中取首、中、尾三个数的中位数、或者当递归深度超过阈值时切换到堆排序。工程实现里三数取中最常见因为它几乎不增加开销却能有效避开有序输入的陷阱。递归深度最坏是O(n)平均O(logn)所以空间复杂度平均O(logn)、最坏O(n)。快排不稳定因为划分过程中相等元素可能被交换到基准的另一侧。这点在需要稳定性的场景要特别注意比如你按成绩排序后还想保持同分学生的原始顺序就不能用快排。3.3 快排的递归优化小区间切插入实际写快排时有个很实用的优化当子区间长度小于某个阈值常见取10到16时不再递归直接调用插入排序。原因是小数组上递归的函数调用开销和栈操作占比太高而插入排序在小数组上常数因子极小。这个混合策略是很多标准库的实际做法。我实测过在随机数据上这个优化能带来百分之十几的性能提升数据量越大越明显。4. 选择类排序简单选择与堆的对比4.1 简单选择排序交换次数最少的O(n²)算法简单选择每趟从未排序部分选出最小的和未排序部分的第一个位置交换。它的特点是交换次数最多n-1次是所有O(n²)算法里移动次数最少的。当元素本身很大、交换代价高比如结构体数组时这个特性有价值。void SelectSort(int A[], int n) { int i, j, min; for (i 0; i n-1; i) { min i; for (j i1; j n; j) if (A[j] A[min]) min j; if (min ! i) { int t A[i]; A[i] A[min]; A[min] t; } } }它不稳定因为把最小值换到前面是跨距离交换。比如[2, 2, 1]第一趟把1和第一个2交换两个2的相对次序就变了。时间复杂度恒为O(n²)因为不管数据什么状态找最小值都要扫完整个未排序部分。4.2 堆排序建堆与调整是两个动作堆排序分两步先自底向上建大根堆然后每次把堆顶最大值和末尾交换堆长度减一再对堆顶做向下调整。建堆的时间复杂度是O(n)而不是O(nlogn)这个结论很多人记不住推导其实很简单从最后一个非叶结点往前调整每个结点调整的代价和它的高度成正比所有结点高度之和是O(n)量级。void HeapAdjust(int A[], int k, int len) { int temp A[k]; for (int i 2*k; i len; i * 2) { // 沿较大孩子下坠 if (i len A[i] A[i1]) i; // 取较大孩子 if (temp A[i]) break; // 已满足堆性质 A[k] A[i]; k i; // 孩子上移 } A[k] temp; } void BuildHeap(int A[], int len) { for (int k len/2; k 1; k--) // 从最后一个非叶结点开始 HeapAdjust(A, k, len); } void HeapSort(int A[], int len) { BuildHeap(A, len); for (int i len; i 1; i--) { int t A[1]; A[1] A[i]; A[i] t; // 堆顶换到末尾 HeapAdjust(A, 1, i-1); // 调整剩余部分 } }这里下标从1开始所以结点k的左孩子是2k、右孩子是2k1最后一个非叶结点是len/2。HeapAdjust里那个i * 2是沿着孩子链往下走每次取较大的孩子和temp比较temp大就停否则孩子上移。这个“上移孩子、最后填temp”的写法比反复交换少一半赋值。堆排序的优点是无论数据什么状态都是O(nlogn)空间O(1)适合对最坏情况有要求的场景比如实时系统。缺点是不稳定而且常数因子比快排大缓存不友好跳跃访问所以通用排序里通常快排优先、堆排兜底。提示建堆从len/2开始不是从len开始。因为下标大于len/2的结点都是叶子叶子本身就是一个合法的堆不需要调整。这个起点写错是堆排序最常见的bug。5. 归并与基数排序稳定性的两条路线5.1 归并排序分治与合并归并排序把序列一分为二分别排好再合并。合并两个有序段是核心操作需要一块辅助数组。它的时间复杂度稳定在O(nlogn)且是稳定的代价是O(n)的额外空间。void Merge(int A[], int B[], int low, int mid, int high) { int i, j, k; for (k low; k high; k) B[k] A[k]; // 复制到辅助数组 for (i low, j mid1, k low; i mid j high; k) { if (B[i] B[j]) A[k] B[i]; // 相等取左边保证稳定 else A[k] B[j]; } while (i mid) A[k] B[i]; while (j high) A[k] B[j]; } void MergeSort(int A[], int B[], int low, int high) { if (low high) { int mid (low high) / 2; MergeSort(A, B, low, mid); MergeSort(A, B, mid1, high); Merge(A, B, low, mid, high); } }合并时那个B[i] B[j]的判断是稳定性的关键相等时优先取左边的保证左边段的元素排在前面。如果写成小于相等时取右边稳定性就没了。归并的递归深度是O(logn)加上辅助数组O(n)总空间O(n)。5.2 基数排序不比较的排序基数排序走的是另一条路它不比较元素大小而是按关键字的每一位分配和收集。以十进制整数为例先按个位分配到10个桶按顺序收集再按十位分配收集直到最高位。每一趟分配收集是稳定的所以整体稳定。时间复杂度O(d(nr))d是位数r是基数十进制就是10。void RadixSort(int A[], int n) { int bucket[10][100], count[10]; int max A[0], d 1, i, j, k, radix 1; for (i 1; i n; i) if (A[i] max) max A[i]; while (max / radix 10) { radix * 10; d; } // 求最大位数 for (int pass 0; pass d; pass) { for (i 0; i 10; i) count[i] 0; for (i 0; i n; i) { int digit (A[i] / radix) % 10; bucket[digit][count[digit]] A[i]; } k 0; for (i 0; i 10; i) for (j 0; j count[i]; j) A[k] bucket[i][j]; radix / 10; } }这段是教学版用二维数组当桶直观但空间浪费大。工程实现会用计数排序做每一趟的分配空间O(nr)。基数排序适合关键字位数少、范围可控的整数排序比如对一批学号或身份证号排序。如果关键字是字符串也可以按字符位做基数排序。6. 常见问题与排查技巧实录6.1 手写排序时的高频错误速查下面这张表是我这些年看别人代码和自己踩坑总结出来的按出现频率排序问题现象可能原因排查方法结果少一个元素或越界循环边界off-by-one用n1、n2的小数组单步快排栈溢出有序输入固定基准换三数取中或随机基准堆排结果错乱建堆起点写成len改为len/2归并后顺序不对合并时没处理剩余段检查两个while收尾稳定性被破坏相等时用了严格不等号检查比较条件方向希尔排序死循环增量没递减到1确认d最终为16.2 几个必须亲手验证的边界场景第一个是空数组和单元素数组。所有排序函数在n0或n1时都应该直接返回不进入循环。我见过快排在单元素时因为lowhigh判断写反导致无限递归的。第二个是全部相等的数组这时候稳定性问题会暴露比如简单选择会把相等元素换乱。第三个是已经有序和完全逆序两种极端输入前者考验最好情况优化插入、冒泡的提前退出后者考验最坏情况快排的基准选择。注意验证排序正确性不要只用随机数据。随机数据几乎不会触发边界bug一定要专门构造有序、逆序、全相等、含重复这四类输入各跑一遍再和标准库的排序结果做逐元素比对。6.3 复杂度分析的推导心得很多人背复杂度表但推不出来我的建议是抓住“基本操作执行次数”这条主线。插入排序的基本操作是比较和移动最坏情况下第i个元素要比较i次、移动i次累加就是n²/2量级。快排的分析要看划分的均衡程度平均情况下每次划分把序列分成两半递归树高度logn每层总工作量n所以O(nlogn)。堆排序的建堆O(n)推导前面说过排序阶段n次调整每次O(logn)合计O(nlogn)。把这些推导自己动手写一遍比背十遍表都管用。我在实际复盘时发现真正让人记住一个算法的不是它的代码而是你亲手调试它、看着它在某个边界上出错、然后想明白为什么的那个过程。所以别光看把上面每段代码敲进编辑器故意改坏一个边界看它怎么错再改回来。这个来回的过程才是把知识变成自己的过程。