1. 排序算法是什么，为什么先学插入排序
在C语言算法学习里，插入排序是最适合零基础起步的排序算法之一。你不需要事先掌握复杂的数学公式，也不需要使用指针、递归、动态内存这些“劝退”内容，只要会用数组、for循环、while循环和函数，就能完整写出一个可运行的排序程序。正因为门槛低、逻辑直观，很多C语言教材和在线题库都把插入排序放在排序章节的开头位置。
那插入排序到底解决什么问题呢？简单来说，它让一个无序数组按照从小到大的顺序重新排列。比如你有一个数组{5, 2, 9, 1}，经过插入排序之后会变成{1, 2, 5, 9}。这种“让数据有序”的需求，在日常生活中经常出现，例如学生成绩排名、商品价格排序、排行榜生成、游戏分数排列等。即使你以后学习了更快的快速排序、归并排序，插入排序的“比较后移”思想仍然值得反复体会。
插入排序属于“插入类排序”，核心思路是维护一个已经有序的部分，然后把新元素逐个插入到正确位置。它和冒泡排序、选择排序一起，被并称为三大基础排序算法。很多同学先学冒泡排序，代码是两层for循环加交换；再学插入排序时，会发现循环结构和移动方式完全不同，容易混淆。本文直接用动画式的过程解析，配合完整C语言代码，把直接插入排序的所有细节拆开讲清楚。
2. 核心思想：从“整理扑克牌”到数组元素移动
2.1 日常生活类比
先别急着看代码，我们用打扑克牌来理解插入排序。
想象你左手拿着一摞已经排好顺序的牌，右手从桌上抽起一张新牌。要把这张新牌插入到左手的牌堆里，你会怎么做？你大概会从左往右或者从右往左看一眼，找到合适位置，然后把新牌放进去。插入排序就是这么工作的。
在数组场景中，我们把数组分成两个“虚拟区域”：左侧是已经排好序的部分，右侧是还没有处理的部分。每次从右侧取出第一个元素，暂存到变量key里，然后把这个key与左侧有序部分进行比较，找到合适的位置插入。这个过程重复进行，直到右侧区域没有元素为止。
2.2 手动模拟一轮插入过程
我们以数组[5, 2, 9, 1]为例，手动走一遍第一轮。
- 初始时，认为下标0的元素
5已经有序，所以已排序区间是[5]，未排序区间是[2, 9, 1]。 - 取出未排序区间的第一个元素
2，记为key = 2。 - 从已排序区间的最后一个元素开始比较：
5 > 2，所以5向右移动一位，数组变成[5, 5, 9, 1]。 - 此时已经到数组最左边，没有元素可比了，就把
key放到下标0位置，数组变成[2, 5, 9, 1]。
这个过程，就是把新牌插到合适位置的过程。每一轮之后，已排序区间都会增加一个新元素。
2.3 两个关键动作：比较和后移
很多初学者会问：插入排序为什么不直接把key和某个元素交换，而要执行“后移”？
它的关键就在这里。如果直接交换，结果可能会覆盖还没处理的数据，而且排序思路会退化成类似冒泡排序的逻辑。插入排序的特点是：先给新元素腾出位置。具体做法是，从右往左逐个比较，只要已排序区间的元素比key大，就把这个元素向右移动一格。等找到第一个比key小的元素时，它右边那个空位就是key的位置，最后执行arr[j + 1] = key。
所以插入排序的核心就六个字：比较、后移、插入。
3. C语言开发环境准备
3.1 编译器与IDE选择
本文代码是标准C语言代码，不依赖特定IDE。你可以在任何支持C语言的开发环境中运行。常见的组合有以下几种：
- Windows系统：使用 Dev-C++、Code::Blocks、Visual Studio，或者 VS Code 搭配 MinGW-w64。
- macOS系统：使用 Xcode Command Line Tools，或者 VS Code 搭配 clang。
- Linux系统：直接使用 gcc 编译，例如
gcc insert_sort.c -o insert_sort。 - 在线编译环境：如果你暂时不想安装软件，可以使用在线C语言编译器快速验证代码。
版本方面不需要过度纠结。本文示例代码用到的是基本语法，在 C99 及之后的版本都能正常编译。如果你的编译器版本比较旧，唯一要注意的是代码块中for (int i = 0; ...)这种在循环内声明变量的写法，旧标准可能不支持，可以改成在函数开头统一声明。
3.2 新建项目文件结构
建议你新建一个目录，文件名使用insert_sort.c，方便记忆和提交。对于这种单文件小项目，不需要额外配置工程，直接写代码，然后编译运行即可。
学习目录/ └── insert_sort.c下面进入最核心的代码部分。
4. 完整的插入排序C语言代码
4.1 源码示例
这是一个可以直接复制运行的完整程序。它定义了数组{5, 2, 9, 1, 5, 6}，调用插入排序函数进行排序，并输出排序前后的数组内容。
#include <stdio.h> // 插入排序函数 // arr: 待排序数组 // n: 数组元素个数 void insertionSort(int arr[], int n) { int i, j, key; // 从下标1开始，因为下标0默认是已排序区间 for (i = 1; i < n; i++) { key = arr[i]; // 取出当前要插入的元素 j = i - 1; // 从已排序区间的最后一个位置开始比较 // 从右往左找插入位置 // 条件 j >= 0 防止数组越界 // 条件 arr[j] > key 表示只有比key大的元素才后移 while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; // 元素后移一位 j--; // 继续向左比较 } arr[j + 1] = key; // 把key放入正确位置 } } // 打印数组 void printArray(int arr[], int n) { int i; for (i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {5, 2, 9, 1, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); printf("原始数组: "); printArray(arr, n); insertionSort(arr, n); printf("排序后数组: "); printArray(arr, n); return 0; }4.2 运行结果与观察
在编译并运行之后，你会看到这样的输出：
原始数组: 5 2 9 1 5 6 排序后数组: 1 2 5 5 6 9注意，数组中有两个5，排序后它们的相对顺序没有发生变化，这其实体现了插入排序的稳定性。关于稳定性的详细解释，我会在第7节展开。
5. 代码逐段拆解：零基础也能看懂每行
5.1 主函数的数组定义
int arr[] = {5, 2, 9, 1, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]);第一行初始化了一个整型数组。第二行是C语言中常用的“求数组长度”写法：sizeof(arr)得到整个数组占用的字节数，sizeof(arr[0])得到第一个元素占用的字节数，两者相除就是元素个数。
这种写法的好处是：你只需要修改花括号里的数据，程序会自动计算数组长度，不用手动数元素个数，减少了错误。
5.2 插入排序函数的参数设计
void insertionSort(int arr[], int n)函数接收两个参数：数组名arr和数组长度n。这里的arr[]在函数内部本质上是一个指向数组首元素的指针，所以函数内对数组元素的修改会直接作用到原数组上，排序结果可以带回main函数。
这一点对新手很重要：C语言函数传参不是“复制整个数组”，而是“让函数拿到数组的地址”。所以排序函数不需要返回值，排序效果已经体现在原数组里了。
5.3 while循环：从右往左找位置
很多人第一次看插入排序的代码，最难理解的就是这段：
while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }来拆开看。
j = i - 1，表示已排序区间的最后一个元素下标。key是当前要插入的元素，它在数组中的原始位置是i。- 进入循环后，我们看
arr[j]是否比key大。如果大，说明key应该排在它前面，所以这个元素要向右挪一个位置，也就是arr[j + 1] = arr[j]。 - 然后
j--，继续向左比较下一个元素。
循环结束有两种情况：
j < 0，说明已经比较到数组最左边，所有已排序元素都比key大，key应该放在下标0位置。arr[j] <= key，说明找到第一个不比key大的元素，key应该放在它右边。
这里有一个容易忽略的细节：为什么循环条件使用arr[j] > key而不是arr[j] >= key？这正是保证排序稳定性的关键。如果使用>=，遇到相同元素时，key会被插到相同元素前面，这会让两个相同元素的相对顺序发生改变。使用>，相同元素可以保持原有顺序，排序更稳定。
5.4 最后的插入赋值
arr[j + 1] = key;当while循环结束时，j已经指向“最后一个不需要移动的元素”。因为循环里我们执行了j--，所以正确插入位置是j + 1。
用一个例子验证。假设数组是[1, 3, 5]，现在要插入4。取key = 4，先比较5 > 4，所以5后移，数组变成[1, 3, 5, 5]，此时j = 1。接着比较3 > 4不成立，循环结束，j还是1，插入位置是j + 1 = 2，所以数组变成[1, 3, 4, 5]。结果正确。
6. 动画式过程模拟：用输入输出观察排序全过程
6.1 带每轮输出的改进版
如果你希望像看动画一样观察每一轮的变化，可以在排序函数里加入输出代码。下面的版本会在每一轮结束后打印当前数组状态，帮你把抽象过程变成可见结果。
#include <stdio.h> void insertionSortWithOutput(int arr[], int n) { int i, j, key; for (i = 1; i < n; i++) { key = arr[i]; 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"); } } int main() { int arr[] = {5, 2, 9, 1, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); printf("原始数组: 5 2 9 1 5 6 \n"); insertionSortWithOutput(arr, n); printf("最终结果: "); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }运行结果如下：
原始数组: 5 2 9 1 5 6 第 1 轮: 2 5 9 1 5 6 第 2 轮: 2 5 9 1 5 6 第 3 轮: 1 2 5 9 5 6 第 4 轮: 1 2 5 5 9 6 第 5 轮: 1 2 5 5 6 9 最终结果: 1 2 5 5 6 96.2 六元素数组全过程演示
我们再手动模拟一遍，把每一轮的比较与移动过程写清楚。
初始数组：
[5, 2, 9, 1, 5, 6]第1轮，处理下标1的元素key = 2：
5 > 2，5后移，数组变为 [5, 5, 9, 1, 5, 6] 到达数组开头，把2放到下标0，数组变为 [2, 5, 9, 1, 5, 6]第2轮，处理下标2的元素key = 9：
5 > 9不成立，不需要移动，9保持在原来位置 数组仍为 [2, 5, 9, 1, 5, 6]第3轮，处理下标3的元素key = 1：
9 > 1，9后移，数组变为 [2, 5, 9, 9, 5, 6] 5 > 1，5后移，数组变为 [2, 5, 5, 9, 5, 6] 2 > 1，2后移，数组变为 [2, 2, 5, 9, 5, 6] 到达数组开头，把1放到下标0，数组变为 [1, 2, 5, 9, 5, 6]第4轮，处理下标4的元素key = 5：
9 > 5，9后移，数组变为 [1, 2, 5, 9, 9, 6] 5 > 5不成立，停止移动 把5放到下标3，数组变为 [1, 2, 5, 5, 9, 6]第5轮，处理下标5的元素key = 6：
9 > 6，9后移，数组变为 [1, 2, 5, 5, 9, 9] 5 > 6不成立，停止移动 把6放到下标4，数组变为 [1, 2, 5, 5, 6, 9]通过这个过程可以看到，每一轮结束后，左侧的已排序区间长度都会加一。这就是直接插入排序的完整执行轨迹。
6.3 从过程推导算法规律
从上面的手动模拟可以总结出三个规律。
第一，第i轮开始时，下标0到i-1的元素已经有序，下标i到n-1的元素还没有处理。
第二，每一轮最多处理一个“新元素”，所以总共需要n-1轮。第一轮从下标1开始，因为下标0单独算一个有序区间。
第三，移动元素的次数等于“比key大的已排序元素个数”，这个数字直接决定了排序的时间开销。数据越接近有序，插入排序的效率越高；数据完全逆序时，效率最低。
7. 时间复杂度、空间复杂度与稳定性分析
7.1 最好、最坏、平均情况
插入排序的时间复杂度分三种情况。
最好情况是数组已经完全有序。此时每一轮只需要比较一次，发现arr[j] <= key就直接结束循环，不需要移动元素。总比较次数是n-1，时间复杂度为O(n)。
最坏情况是数组完全逆序。比如[9, 8, 7, 6, 5, 4, 3, 2, 1]，每一轮都要把新元素移动到最左边。总比较次数和移动次数都是1 + 2 + 3 + ... + (n-1)，也就是n(n-1)/2级别的量，时间复杂度为O(n^2)。
平均情况也是O(n^2)。虽然看起来不快，但插入排序在“近乎有序”的数据上表现非常好，这是它的重要优势。实际项目中，如果数据量不大或者数据基本有序，插入排序完全够用。
7.2 空间复杂度：原地排序
插入排序只额外使用了i、j、key这样的常量级变量，不需要额外的数组，所以空间复杂度是O(1)。它属于原地排序算法，这意味着即使数据量很大，也不会因为排序而占用过多内存。
7.3 稳定性：相同元素不会改变相对顺序
稳定性的定义是：如果两个元素的值相等，排序后它们的相对位置不发生变化。
插入排序为什么稳定？因为while循环的判断条件使用的是arr[j] > key，并不包含等于的情况。当遇到相同元素时，key会插入到相同元素的右边，而不是左边。因此相同元素的先后顺序保持不变。
这一点在基础排序题里可能看不出差别，但在实际业务中很重要。比如一个对象包含“成绩”和“学号”两个字段，我们先按学号排好序，再按成绩排序。如果排序算法稳定，成绩相同的情况下，学号仍然保持有序。如果排序不稳定，第二次排序可能打乱学号顺序。
8. 常用优化思路
8.1 减少交换次数
有人会把插入排序改写成“每一步都交换”的版本：
while (j >= 0 && arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; j--; }这种写法虽然也能排序，但每次交换都涉及三次赋值，效率比“后移+最后插入”差。推荐仍然是先把key保存下来，只做单方向后移，最后再插入，这样每轮只做一次“关键写入”。
8.2 二分插入排序
由于插入排序的左侧区间始终是有序的，所以在“找插入位置”这一步，可以使用二分查找来减少比较次数。这种优化称为“二分插入排序”。
二分插入可以把比较次数从O(n^2)降到O(n log n)，但是元素移动次数仍然是最坏O(n^2)。它适合元素比较代价较高、移动代价较低的场景。不过对于零基础学习阶段，先掌握普通版插入排序就可以。
8.3 与冒泡排序、选择排序的对比
很多在线题库的排序题，第一反应就是冒泡排序。这里简单对比三者：
- 冒泡排序：相邻元素两两比较并交换，每轮把最大值“冒”到末尾。
- 选择排序：每轮找到最小值，和当前前缀位置交换。
- 插入排序：每轮把新元素插入到已经有序的左侧区间中。
在数据基本有序的情况下，插入排序通常比冒泡和选择排序表现更好。这也是为什么有时在工程代码里能看到插入排序作为“小数组排序”的辅助手段，比如快速排序在数据量很小时，可能切换到插入排序来完成。
9. 零基础常见问题与排查思路
9.1 常见报错与原因
初学者运行插入排序代码时，可能遇到下面几种情况。
| 问题现象 | 常见原因 | 解决思路 |
|---|---|---|
| 程序运行后无输出 | 可能忘记调用printf，或编译没有成功 | 检查主函数中是否有一行printf("排序后数组: "); |
| 数组越界，程序崩溃 | while循环中缺少j >= 0条件 | 检查while条件是否同时写了j >= 0 && arr[j] > key |
| 排序结果只排了一部分 | 外层循环从0开始，把第一个元素也当作待插入元素 | 外层循环应该从i = 1开始；下标0已经是“已排序区间” |
编译报错，提示找不到printf | 缺少头文件#include <stdio.h> | 在文件开头补上#include <stdio.h> |
编译报错，提示for循环变量问题 | 编译器标准过旧，不支持循环内声明变量 | 把int i;提前到函数开头，或切换编译器标准为C99 |
9.2 排序结果不对怎么办
如果你运行之后发现数组没有完全变有序，建议按下面顺序排查。
先打印每一轮结果，看哪个位置最先错。如果第一轮就错了，多半是key保存的位置不对，或者while循环里的比较符号写反了。如果前面几轮正确、后面乱套，可能是数组长度算错了。
int n = sizeof(arr) / sizeof(arr[0]);这个写法要确保arr定义在同一个函数内。如果把数组传给函数后再在函数里用sizeof(arr) / sizeof(arr[0])，得到的是“指针大小除以元素大小”，结果不是数组长度，这是C语言新手最常见的坑之一。
9.3 在线题库提交失败的通用检查
如果是在在线OJ平台遇到“答案错误”或“运行超时”，除了检查排序逻辑，还要注意输入输出格式。题目要求输入多组数据时，需要用while循环读取整数，直到文件结束。例如：
int n; while (scanf("%d", &n) != EOF) { // 处理每一组数据 }另外要仔细阅读题目要求，是升序还是降序，是否允许重复元素。如果要求降序，只需要把while循环里的>改成<。
10. 最佳实践与下一步学习路线
10.1 写插入排序时的代码规范
建议把排序逻辑封装成独立函数，而不是把所有代码都堆在main里。函数命名可以使用insertionSort，参数列表统一写成“数组 + 长度”的形式。这样以后刷题或做项目时，可以快速复用。
边界条件一定要写完整。特别是while循环里的j >= 0，千万不要省略。我见过很多初学者因为少写这个条件，程序在数组最左边越界，造成难以排查的内存问题。
关键变量命名也要有含义。用key表示当前待插入的元素，比用temp更清晰，因为key能表达它在排序中的角色。
10.2 什么场景适合使用插入排序
插入排序的时间复杂度最坏是O(n^2)，所以它不适合处理超大规模数据。但是在下面几种场景中，它仍然是不错的选择：
- 数据量很小，比如少于几十个元素。
- 数组本身已经接近有序。
- 作为其他高效排序算法的小规模子任务。
- 教学演示，用来理解“有序区间 + 插入”的核心思想。
在正式项目中，如果需要对大量无序数据排序，建议使用qsort或者手写快速排序、归并排序。不过先掌握插入排序，对理解这些更高级的排序非常有帮助。
10.3 建议的练习顺序
学习算法最忌讳“只看不练”。建议按下面顺序动手实践。
第一，把本文的完整代码自己敲一遍，不要复制粘贴，确保能够编译运行。
第二，修改数组内容，测试空数组、单个元素、完全逆序、完全有序、含有重复元素这几种情况，观察运行结果。
第三，去掉函数封装，把排序逻辑直接写进main函数里，感受两者的区别，然后尝试把输入改成由键盘输入。
第四，做几道在线编程平台的入门排序题。很多C语言题库都有“排序”相关的基础题，它们通常会要求你处理多组输入，正好能检验你对循环和输入输出的掌握程度。
第五，把冒泡排序、选择排序、直接插入排序三种代码放在同一个程序里，用同一组数据对比排序过程和结果，这样能加深理解，避免以后混淆。
最后说一个我比较推荐的学习方法：给排序函数加上打印语句，亲眼看到每一轮的变化之后，再把打印语句删掉，让代码恢复成标准库函数的样子。这个“先看过程、再回到结果”的训练方式，对理解任何排序算法都很有用。等你把插入排序彻底吃透，再去看希尔排序、归并排序，会发现很多思路其实是一脉相承的。
