408内部排序全解析：从算法原理到C代码实现与避坑指南

内部排序这块内容，我在带新人和自己做项目复盘的时候反复讲过很多轮。很多人学完数据结构课程，考试能默写快排和堆排的伪代码，但真让他手写一份能跑、边界不出错、还能说清楚每个参数为什么这么定的实现，就开始卡壳。这篇东西就是冲着这个痛点来的：把408考纲里那几类内部排序——插入、希尔、冒泡、快速、选择、堆、归并、基数——从算法思路、代码实现、复杂度推导到实际踩坑，完整捋一遍。适合正在准备408的考生，也适合工作几年后想回头把基础夯实的朋友。代码我全部用C风格写，贴近教材和考场习惯，每一段都能直接编译运行，注释里标清楚关键变量的含义和边界条件，你可以直接抄去当模板。

1. 内部排序的整体设计思路与选型逻辑

1.1 为什么内部排序值得单独拎出来啃

内部排序指的是待排序记录全部放在内存里完成的排序过程，和外部排序相对。408考纲里明确列出的内部排序算法有插入类（直接插入、折半插入、希尔）、交换类（冒泡、快速）、选择类（简单选择、堆）、归并排序和基数排序。这些算法不是孤立的知识点，它们背后是同一套分析框架：时间复杂度、空间复杂度、稳定性、适用场景。考试喜欢考对比，工程里也确实是按这套框架选型的。

我见过不少人背复杂度表背得很熟，但一问“为什么希尔排序不稳定”就答不上来。原因在于希尔排序做的是跳跃式插入，相同元素可能被分到不同子序列里，相对次序在跨组移动时被打乱。这种“为什么”才是真正拉开差距的地方。所以这篇不打算只给结论，每个算法的关键设计我都会拆开讲清楚它解决了什么问题、代价是什么。

从工程视角看，内部排序是所有数据处理的地基。你写业务代码时调用的库函数排序，底层往往是多种算法的混合策略，比如小数组用插入排序、大数组用快排、递归深度超限切堆排。理解这些单算法的特性，才能明白混合策略为什么这么设计。这也是我坚持把每个算法手写一遍的原因——调库调多了，人会失去对边界和性能的敏感度。

1.2 一张表看清各算法的取舍

选型之前先把全局图景摆出来。下面这张表是我自己复习和讲课时用的核心对照表，参数都按408的标准定义来：

这张表要能自己推出来，而不是死记。比如堆排序空间为什么是O(1)？因为它原地建堆、原地调整，只用了常数个临时变量。归并为什么是O(n)？因为合并两个有序段需要一块和原数组等长的辅助空间。每个格子背后都有推导路径，后面章节我会逐个展开。

1.3 选型的三个判断维度

实际选算法时我一般看三件事。第一是数据规模，n小于几十的时候插入排序反而快，因为常数因子小、没有递归开销，这也是很多标准库在小数组上切插入排序的原因。第二是数据初始状态，如果数据基本有序，插入和冒泡能退化到O(n)，而快排在这种输入上如果基准选得不好反而容易退化。第三是稳定性要求，只要业务里有多关键字排序的需求，比如先按成绩排再按班级排，就必须用稳定算法，否则前一次排序的结果会被破坏。

提示：稳定性不是“锦上添花”，在多关键字排序场景里是硬需求。判断一个算法稳不稳定，看它有没有发生“跨距离交换”。直接插入是相邻挪位所以稳定，简单选择是把最小值直接换到前面，跨距离交换会破坏稳定性。

2. 插入类排序的细节拆解与代码实现

2.1 直接插入排序：把哨兵用起来

直接插入的思路就是打扑克摸牌，每次把新牌插到前面已经有序的手牌里合适的位置。教材版本通常用A[0]当哨兵，这个设计很值得说。哨兵的作用是省掉内层循环的边界判断——把待插入元素先放到A[0]，然后从后往前比较，只要A[j]大于哨兵就往后挪，一旦遇到不大于的就停，因为A[0]本身等于待插入值，循环必然在j=0处终止，不用额外写j>=1的判断。这是一个用一点空间换掉每次循环一次比较的经典技巧。

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[j+1] = A[j]; // 后移 A[j+1] = A[0]; // 落位 } } }

这段代码有几个细节容易写错。第一，数组下标从1开始用，A[0]专门留给哨兵，所以循环从i=2起。第二，外层那个if判断不是可有可无的优化，当A[i]已经大于等于前一个元素时直接跳过，这让最好情况（原本有序）退化成O(n)而不是O(n²)。第三，内层for循环结束后j指向的是第一个不大于哨兵的位置，所以落位是A[j+1]而不是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 >= high+1; j--) A[j+1] = A[j]; // 统一后移 A[high+1] = A[0]; } }

这里的关键在else分支：当A[mid]等于哨兵时，我们让low=mid+1，也就是继续往右半区找，这样最终插入位置会在所有相等元素的右边，保证稳定性。如果写成A[mid] >= A[0]时high=mid-1，就会插到相等元素左边，稳定性就破坏了。这个细节考试爱考，实际写代码也常错。

注意：折半插入的循环结束后，插入位置是high+1，后移的起点也是high+1。很多人写成low，虽然此时代码里low和high+1数值上相等，但语义上high+1才是“最后一个不大于哨兵的位置的右边”，理解清楚这个语义比记结论重要。

2.3 希尔排序：增量序列是灵魂

希尔排序是把序列按增量d分成若干子序列，对每个子序列做直接插入，然后缩小增量重复，直到d=1。它的巧妙之处在于，前期用大增量让元素大跨度移动，快速把小的元素送到前面、大的送到后面，让序列逐渐变得“基本有序”，最后一趟d=1的插入排序面对的已经是一个接近有序的序列，效率很高。

void ShellSort(int A[], int n) { int d, i, j; for (d = n/2; d >= 1; d = d/2) { // 增量每次折半 for (i = d+1; 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[j+d] = A[j]; A[j+d] = A[0]; } } } }

增量序列的选择直接影响性能。教材常用n/2折半，但严格说这个序列不是最优的，最坏仍可能到O(n²)。工程上更常用的是Hibbard序列（2^k-1）或Sedgewick序列，能把最坏复杂度压到O(n^1.5)甚至更好。408考试按教材的折半增量写就行，但你要知道这不是唯一选择。

希尔排序为什么不稳定？举个例子，序列[3, 3, 1]，增量d=2时，第一个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及之前已经是最小的i+1个元素。如果从前往后扫把大的往后冒，逻辑对称，但循环边界要相应调整。两种写法都对，关键是边界别写错。冒泡是稳定的，因为只有严格大于才交换，相等不换。

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]变成新坑，左边找到大的填进去，如此往复，最后low==high时把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 = i+1; 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[i+1]) 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、右孩子是2k+1，最后一个非叶结点是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 = mid+1, 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, mid+1, high); Merge(A, B, low, mid, high); } }

合并时那个B[i] <= B[j]的判断是稳定性的关键：相等时优先取左边的，保证左边段的元素排在前面。如果写成小于，相等时取右边，稳定性就没了。归并的递归深度是O(logn)，加上辅助数组O(n)，总空间O(n)。

5.2 基数排序：不比较的排序

基数排序走的是另一条路，它不比较元素大小，而是按关键字的每一位分配和收集。以十进制整数为例，先按个位分配到10个桶，按顺序收集，再按十位分配收集，直到最高位。每一趟分配收集是稳定的，所以整体稳定。时间复杂度O(d(n+r))，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(n+r)。基数排序适合关键字位数少、范围可控的整数排序，比如对一批学号或身份证号排序。如果关键字是字符串，也可以按字符位做基数排序。

6. 常见问题与排查技巧实录

6.1 手写排序时的高频错误速查

下面这张表是我这些年看别人代码和自己踩坑总结出来的，按出现频率排序：

6.2 几个必须亲手验证的边界场景

第一个是空数组和单元素数组。所有排序函数在n=0或n=1时都应该直接返回，不进入循环。我见过快排在单元素时因为low<high判断写反导致无限递归的。第二个是全部相等的数组，这时候稳定性问题会暴露，比如简单选择会把相等元素换乱。第三个是已经有序和完全逆序两种极端输入，前者考验最好情况优化（插入、冒泡的提前退出），后者考验最坏情况（快排的基准选择）。

注意：验证排序正确性不要只用随机数据。随机数据几乎不会触发边界bug，一定要专门构造有序、逆序、全相等、含重复这四类输入各跑一遍，再和标准库的排序结果做逐元素比对。

6.3 复杂度分析的推导心得

很多人背复杂度表但推不出来，我的建议是抓住“基本操作执行次数”这条主线。插入排序的基本操作是比较和移动，最坏情况下第i个元素要比较i次、移动i次，累加就是n²/2量级。快排的分析要看划分的均衡程度，平均情况下每次划分把序列分成两半，递归树高度logn，每层总工作量n，所以O(nlogn)。堆排序的建堆O(n)推导前面说过，排序阶段n次调整每次O(logn)，合计O(nlogn)。把这些推导自己动手写一遍，比背十遍表都管用。

我在实际复盘时发现，真正让人记住一个算法的不是它的代码，而是你亲手调试它、看着它在某个边界上出错、然后想明白为什么的那个过程。所以别光看，把上面每段代码敲进编辑器，故意改坏一个边界，看它怎么错，再改回来。这个来回的过程，才是把知识变成自己的过程。