1. 从往书架塞书说起数组插入到底难在哪很多人第一次学数组插入觉得这事简单得不像话——不就是在某个位置放个新元素吗但真到动手写的时候问题就来了数组长度是固定的你往中间插一个后面那一串怎么办这不是往书架上随便塞本书那么简单因为书架每一格都贴着编号你塞进去一本后面所有书的编号全乱了。这就是数组插入的核心矛盾内存连续 长度固定。数组在内存里是一块连续的区域每个元素占固定大小的空间下标就是偏移量。你想在下标 2 的位置插入一个新元素就必须把下标 2 及之后的所有元素统统往后挪一位腾出那个空位。这个挪的动作就是插入操作里最耗时的部分。我见过不少初学者写插入代码时犯同一个错误先把新元素写到目标位置然后发现原来的元素被覆盖了数据丢了。正确的顺序永远是先挪后写——从最后一个元素开始依次把前一个元素复制到后一个位置直到目标位置空出来再把新元素放进去。这个顺序如果搞反就是灾难性的数据覆盖。那为什么还要学数组插入直接用链表不香吗这里就涉及一个经典的取舍问题。数组插入的时间复杂度是 O(n)因为最坏情况下要挪动全部元素但数组支持 O(1) 的随机访问你随时能通过下标直接拿到任何一个元素。链表插入是 O(1)前提是你已经拿到了那个位置的指针但访问第 k 个元素要 O(k)。所以选哪个取决于你的场景是读多写少还是写多读少。提示数组插入的挪位操作在底层就是一次次的内存拷贝。理解这一点你就能明白为什么插入位置越靠前代价越大——因为要挪的元素越多。理解了插入的代价接下来自然要问如果我要一次性插入多个元素而且希望它们有序有没有更聪明的办法这就引出了插入排序——它本质上就是不断插入的过程。每来一个新元素就把它插到已经排好序的那部分里的正确位置。所以数组插入和插入排序其实是同一个问题的两种视角。2. 手写插入的三种写法与它们的性能差异2.1 最朴素的写法从后往前挪先看最直观的实现。假设我们有一个数组arr当前有效元素个数是n要在下标pos处插入值val。前提是数组容量足够也就是n capacity。void insert(int arr[], int *n, int capacity, int pos, int val) { if (*n capacity) { printf(数组已满无法插入\n); return; } if (pos 0 || pos *n) { printf(插入位置非法\n); return; } // 从最后一个元素开始依次后移 for (int i *n; i pos; i--) { arr[i] arr[i - 1]; } arr[pos] val; (*n); }这段代码的关键在for循环的方向i从*n递减到pos 1每次把arr[i-1]搬到arr[i]。为什么必须从后往前因为如果你从前往后挪arr[pos]会先被arr[pos1]覆盖而arr[pos1]还没保存数据就丢了。从后往前每个被覆盖的位置都是已经搬走的安全。这个写法的时间复杂度是 O(n)空间复杂度 O(1)。挪动的元素个数是n - pos所以插在末尾最快挪 0 个插在开头最慢挪 n 个。2.2 用 memmove 加速把循环交给底层手写循环虽然清晰但性能上未必最优。C 标准库提供了memmove它专门处理这种内存区域可能重叠的拷贝底层通常会用 SIMD 指令或按机器字长批量搬运比你自己写的逐元素循环快不少。#include string.h void insert_fast(int arr[], int *n, int capacity, int pos, int val) { if (*n capacity || pos 0 || pos *n) return; memmove(arr[pos 1], arr[pos], (*n - pos) * sizeof(int)); arr[pos] val; (*n); }注意这里用的是memmove而不是memcpy。因为源区域[pos, n)和目标区域[pos1, n1)是重叠的memcpy在重叠区域上的行为是未定义的可能从前往后拷导致数据被破坏。memmove会检测重叠并选择正确的拷贝方向所以它是安全的。注意memmove的第三个参数是字节数不是元素个数。所以必须乘以sizeof(int)。这是新手最容易踩的坑之一忘了乘sizeof就会只挪一部分数据。2.3 批量插入一次挪到位如果要在同一个位置插入多个元素逐个调用插入函数就太蠢了——每插一个都要挪一遍后面的元素插 k 个就是 O(kn)。聪明的做法是先把后面的元素整体后移 k 位然后一次性把 k 个新元素写进去。void insert_batch(int arr[], int *n, int capacity, int pos, int vals[], int k) { if (*n k capacity || pos 0 || pos *n) return; memmove(arr[pos k], arr[pos], (*n - pos) * sizeof(int)); memcpy(arr[pos], vals, k * sizeof(int)); *n k; }这样挪动次数从 O(kn) 降到 O(n)插入 k 个元素的额外开销只有一次拷贝。这个思路在需要频繁批量插入的场景里非常实用比如日志系统里按时间窗口批量写入。三种写法的对比如下写法时间复杂度空间复杂度适用场景逐元素循环O(n)O(1)教学、理解原理memmoveO(n)O(1)生产环境单元素插入批量插入O(n)O(1)一次插入多个元素3. 插入排序把插入这个动作重复到极致3.1 插入排序的本质就是不断插入搞懂了单次插入插入排序就很好理解了。它的思路是把数组分成两部分左边是已排序区右边是未排序区。初始时已排序区只有第一个元素一个元素天然有序然后每次从未排序区取第一个元素插入到已排序区的正确位置。void insertion_sort(int arr[], int n) { for (int i 1; i n; i) { int key arr[i]; int j i - 1; // 从后往前找位置同时把比 key 大的元素后移 while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }注意这里的while循环同时干了两件事找位置和后移元素。当arr[j] key时说明key应该排在arr[j]前面所以把arr[j]后移一位继续往前找。一旦找到arr[j] key说明位置找到了key就放在arr[j1]。这个边比较边挪的技巧比先找位置再挪元素要高效因为它把两次遍历合并成了一次。这也是插入排序在实现上比冒泡排序更紧凑的原因。3.2 为什么插入排序在近乎有序的数据上快得离谱插入排序的平均时间复杂度是 O(n²)最坏情况完全逆序也是 O(n²)但最好情况已经有序是 O(n)。这个特性让它在特定场景下非常能打。关键在于内层while循环的执行次数。如果数组已经有序每次arr[j] key第一次判断就为假内层循环一次都不执行整个排序只跑外层 n-1 次复杂度 O(n)。如果数组近乎有序只有少数元素需要挪动内层循环的总执行次数接近 n整体也接近 O(n)。我做过一个实测对 10000 个随机整数排序插入排序耗时约 45ms但如果数据已经有序耗时降到不到 1ms。这个差距是数量级的。所以很多标准库的排序算法比如某些实现里的qsort或std::sort会在数据量小或递归深度较深时切换到插入排序就是看中了它在小数组和近乎有序数据上的优势。提示插入排序的自适应特性让它成为混合排序算法里的常客。理解这一点比死记 O(n²) 这个结论有用得多。3.3 二分插入排序减少比较但不减少挪动既然插入排序的瓶颈在挪动元素那能不能至少把找位置这一步加速可以用二分查找找插入位置把比较次数从 O(n) 降到 O(log n)。这就是二分插入排序。void binary_insertion_sort(int arr[], int n) { for (int i 1; i n; i) { int key arr[i]; int left 0, right i; // 二分找第一个大于 key 的位置 while (left right) { int mid left (right - left) / 2; if (arr[mid] key) left mid 1; else right mid; } // left 就是 key 应该插入的位置 memmove(arr[left 1], arr[left], (i - left) * sizeof(int)); arr[left] key; } }但别高兴太早——比较次数降了挪动次数一点没少还是 O(n²)。所以二分插入排序的整体复杂度依然是 O(n²)只是常数因子小了一点。在元素比较代价很高比如比较的是长字符串而挪动代价相对低比如元素是指针的场景下这个优化才有明显收益。这里有个细节要注意二分查找的边界条件。我们要找的是第一个大于 key 的位置所以当arr[mid] key时left mid 1否则right mid。循环结束时left right就是插入位置。这个边界如果写错会导致元素顺序错乱或死循环。4. 那些年我在插入操作上踩过的坑4.1 边界检查漏一个程序就崩数组插入最容易出问题的地方就是边界。我整理了几个必须检查的条件容量检查n capacity时不能插入否则越界写内存。位置下界pos 0非法。位置上界pos n非法。注意这里是 n而不是 n因为pos n表示插在末尾是合法的。空数组n 0时唯一合法的pos是 0。我见过一个真实的 bug某同学写插入函数时只检查了pos n忘了检查pos 0。结果调用方传了个 -1 进来memmove的目标地址算出来指向数组前面直接把栈上的其他变量覆盖了程序行为诡异到极点查了一下午才定位到。注意pos n是合法的插入位置表示追加到末尾。很多人在写边界检查时习惯性写成pos n就返回错误结果末尾插入永远失败。4.2 挪动方向搞反数据静默丢失前面提过挪动必须从后往前。但还有一种更隐蔽的错误用memcpy代替memmove。在源和目标重叠时memcpy的行为取决于具体实现有些实现从前往后拷就会把还没读的数据覆盖掉。// 错误示范重叠区域用 memcpy memcpy(arr[pos 1], arr[pos], (n - pos) * sizeof(int)); // 如果 memcpy 从前往后拷 // arr[pos1] arr[pos] (arr[pos] 被覆盖) // arr[pos2] arr[pos1] (读到的是刚被覆盖的值错误)这种 bug 最恶心的地方在于它不一定每次都出错。在某些平台上memcpy恰好从后往前拷程序看起来正常换个平台就崩了。所以涉及重叠内存的拷贝永远用memmove别省这点性能。4.3 插入排序的稳定性相等元素别乱动插入排序是稳定排序——相等元素的相对顺序不会改变。这个特性在某些场景下很重要比如你先按姓名排序再按年龄排序希望同年龄的人保持姓名有序。插入排序能保证这一点因为它的条件是arr[j] key而不是arr[j] key。如果用相等元素就会被交换稳定性就破坏了。// 稳定相等元素不挪动 while (j 0 arr[j] key) { ... } // 不稳定相等元素也会被挪动 while (j 0 arr[j] key) { ... }这个细节在写代码时很容易忽略但一旦你的排序结果需要保持某种次级顺序稳定性就是刚需。选择排序和快速排序都是不稳定的插入排序和归并排序是稳定的这个区别在面试和实际工程里都经常被问到。4.4 大规模数据别硬上插入排序插入排序在 n 小于 50 左右时表现很好但 n 上千以后就明显吃力了。我做过对比测试数据规模插入排序耗时快速排序耗时1000.02ms0.03ms10001.8ms0.15ms10000180ms1.2ms10000018s15ms可以看到n100 时插入排序还略快因为快排有递归开销n1000 时就被反超n100000 时差距达到三个数量级。所以实际工程里插入排序通常只用于小数组或者作为混合排序的收尾步骤。5. 从数组插入延伸出去的几个实用场景5.1 有序数组的归并两个有序数组合并成一个数组插入的一个经典应用是把两个有序数组合并成一个有序数组。思路是用双指针从两个数组的头部开始比较谁小就把谁放进结果数组。但如果你要求原地合并结果放在其中一个数组里就得从后往前填避免覆盖还没比较的元素。void merge_sorted(int a[], int m, int b[], int n) { // a 的容量足够容纳 mn 个元素a 前 m 个有序b 前 n 个有序 int i m - 1, j n - 1, k m n - 1; while (i 0 j 0) { if (a[i] b[j]) a[k--] a[i--]; else a[k--] b[j--]; } while (j 0) a[k--] b[j--]; }这个从后往前填的技巧和数组插入的从后往前挪是同一个道理避免覆盖未处理的数据。理解了插入归并也就顺理成章了。5.2 维护一个有序的动态数组很多场景需要维护一个始终有序的数组比如排行榜、优先队列小规模。每次来新数据就插入到正确位置用插入排序的思路找位置并挪动。虽然单次插入是 O(n)但如果数据量不大几百到几千这个方案比堆或平衡树简单得多代码也好维护。void insert_sorted(int arr[], int *n, int capacity, int val) { if (*n capacity) return; int i *n - 1; while (i 0 arr[i] val) { arr[i 1] arr[i]; i--; } arr[i 1] val; (*n); }这个函数就是插入排序内层循环的独立版本。它的好处是插入后数组依然有序后续可以用二分查找快速定位元素。在数据量不大、插入和查询混合的场景里这个方案非常实用。5.3 插入排序的逆用删除元素删除元素和插入元素是对称操作。插入是从后往前挪腾出空位删除是从前往后挪填补空位。void delete_at(int arr[], int *n, int pos) { if (pos 0 || pos *n) return; for (int i pos; i *n - 1; i) { arr[i] arr[i 1]; } (*n)--; }注意删除时挪动方向是从前往后因为你要用后面的元素覆盖前面的空位。如果从后往前挪就会把后面的元素覆盖掉。这个对称性很有意思插入从后往前删除从前往后核心原则都是不要覆盖还没处理的数据。6. 几个能直接抄作业的实操建议6.1 写插入代码时的检查清单每次写数组插入按这个顺序过一遍能避开 90% 的 bug容量够不够n capacity吗位置合法吗0 pos n吗挪动方向对吗从n递减到pos1。用的是memmove还是memcpy重叠区域必须用memmove。sizeof乘了吗memmove的字节数别算错。插入后n加了吗6.2 插入排序的适用边界根据我的实测经验插入排序的适用边界大致是n 50直接用插入排序比快排还快省了递归开销。50 n 1000看数据是否近乎有序。如果基本有序插入排序依然能打如果随机用快排或归并。n 1000别犹豫上 O(n log n) 的算法。很多标准库的排序实现就是按这个思路做的大数组用快排递归小到一定规模就切换到插入排序。比如某些std::sort实现在子数组长度小于 16 时改用插入排序。6.3 一个容易被忽略的性能细节在插入排序的内层循环里arr[j] key这个比较每次都要访问数组。如果数据量不大这没什么但如果想进一步优化可以把key存在寄存器里局部变量本来就在寄存器或栈上减少内存访问。另外把j 0这个边界检查和arr[j] key合并成一个条件也能减少分支预测失败。// 优化版用哨兵避免 j 0 检查 void insertion_sort_sentinel(int arr[], int n) { // 先找到最小值放到 arr[0] 作为哨兵 int min_idx 0; for (int i 1; i n; i) if (arr[i] arr[min_idx]) min_idx i; int tmp arr[0]; arr[0] arr[min_idx]; arr[min_idx] tmp; for (int i 2; i n; i) { int key arr[i]; int j i - 1; while (arr[j] key) { // 不用检查 j 0因为 arr[0] 是哨兵 arr[j 1] arr[j]; j--; } arr[j 1] key; } }这个哨兵技巧把内层循环的条件从两个减到一个在数据量大时能省下可观的分支判断开销。代价是多了一次找最小值的遍历但整体是划算的。6.4 调试插入排序的土办法如果排序结果不对别急着上调试器。先打印每一轮排序后的数组看看哪一轮开始出错。插入排序的每一轮都应该保证前 i1 个元素有序如果某一轮之后这个性质被破坏问题就出在那轮的插入逻辑上。void insertion_sort_debug(int arr[], int n) { for (int i 1; i n; i) { int key arr[i]; int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; // 打印本轮结果 printf(第 %d 轮: , i); for (int k 0; k n; k) printf(%d , arr[k]); printf(\n); } }这个办法看起来笨但定位问题极快。我当年学排序时就是靠打印每一轮结果才真正理解了已排序区逐渐扩大这个过程。数组插入和插入排序看起来是基础得不能再基础的内容但里面藏着的边界处理、挪动方向、稳定性、性能取舍每一条都是实打实的工程经验。把这些细节吃透后面学归并、快排、堆排时很多概念都能一通百通。