1. 排序算法与插入排序的定位
排序算法是数据结构课程里绕不开的基础模块，也是面试和实际开发中最常碰到的算法类型。说到排序，很多初学者第一反应是“Arrays.sort()不就完了吗”，但真要让你解释清楚排序背后的思想、复杂度的推导过程、不同数据分布下的表现差异，大多数人是说不明白的。插入排序作为三大基础排序之一（另外两个是冒泡和选择），它的价值不在于性能有多强，而在于它把“在有序序列中插入一个元素”这个思想讲透，这种思想后面学二分插入、希尔排序、甚至链表操作都会反复用到。
插入排序的思路超级直白：就像你打扑克牌抓牌时的整理方式。摸到一张新牌，从右往左跟手里已有的牌比较，找到合适位置插进去，手里的牌始终保持有序。这个动作重复N次，整副牌就有序了。用这种方式排序数组，本质上是把数组分成两个逻辑区域——左边是“已经排好序的部分”，右边是“还没处理的部分”，每次从右边拿一个元素，往左边合适的位置插入，直到右边耗尽。整个过程里数组元素的实际存储位置在变，但逻辑上始终维持一个有序前缀。
为什么要专门拎出插入排序来深入研究？两个原因。第一，它是理解“稳定性”这个概念的最佳入门案例——相同元素的相对顺序不会被破坏，这在很多实际场景里很重要，比如你想先按时间排序，再按优先级排序，两次排序后低优先级里时间有序、同时间段里优先级有序，如果排序算法不稳定，第二次排序会打乱第一次的顺序。第二，插入排序在“近乎有序”的数据上表现反而出奇地好，几乎能达到线性复杂度，这个特性在工程中经常被利用，例如某些排序框架在处理小规模近似有序子数组时会在底层切换到插入排序。
这篇内容就是围绕插入排序的Java实现来展开的。我会从算法思路讲起，手动模拟一遍完整流程，分析时间复杂度，给出可运行的Java代码，再补充调试技巧、性能对比以及插入排序的变体和工程应用。无论你是刚学数据结构的在校生，还是在准备面试的求职者，或者工作中需要自己手写排序逻辑的开发者，这篇内容都可以直接参考。
2. 插入排序的核心思路与运行机制
2.1 从“抓牌”到“数组排序”的思想迁移
插入排序的核心操作是“插入”——把一个元素放进一组已经有序的元素中，并且保持有序。这不是一个独立的动作，而是一个循环迭代的过程。理解它的关键，是要意识到每轮迭代结束的时候，数组左侧的某个前缀一定是有序的。
举个例子。假设数组开头是 [5, 2, 4, 6, 1, 3]。第一轮，我们认为 index=0 的元素5单独构成一个有序序列（一个元素天然有序）。然后取 index=1 的元素2，想办法把它放到前面有序序列的合适位置，结果就是 [2, 5, 4, 6, 1, 3]，此时前两个元素有序。第二轮取 index=2 的元素4，往前比较，插到2和5之间，得到 [2, 4, 5, 6, 1, 3]。这个“取一个、往前插、有序前缀长度加一”的过程反复进行，就能完成整个排序。
我经常把插入排序比作“电影院里有人迟到后找座位”的过程：前面已经坐好的人不动，只有迟到的人沿着过道往里走，遇到比自己矮（或高）的就往旁边挪一挪，直到找到合适位置坐下去。这里“前面的人不动”意味着我们不断把一个新元素安插到有序区域，而不是像冒泡排序那样反复交换相邻元素来“冒泡”最大值。方向不一样，行为模式也不一样。
具体到数组操作，插入的动作怎么做？教科书上的经典做法是“后移腾位”：从有序区的末尾开始，依次把大于待插入元素的元素向后移动一位，直到找到正确的位置，然后把待插入元素放进去。这个操作全程是数组元素的移动，不涉及额外数组，所以是原地排序。数组不像链表那样有方便的 insert 操作，只能通过覆盖写达到插入效果，后移腾位正是为了避免引入额外内存开销。
2.2 手动模拟一趟完整插入过程
光说思路还是抽象，我这里把整个排序过程走一遍，帮助你把“有序边界”“待插入元素”“后移范围”这几个概念彻底看清。假设原始数组是：
[5, 2, 4, 6, 1, 3]第1轮：处理下标1的元素（值=2）
当前有序前缀是 [5]。待插入的key=2。从后往前看，5>2，所以把5后移一位。此时数组变为 [5, 5, 4, 6, 1, 3]。比较到头了，key=2放到下标0位置，数组变成 [2, 5, 4, 6, 1, 3]。
第2轮：处理下标2的元素（值=4）
有序前缀是 [2, 5]。待插入key=4。比较下标1的值5，5>4，5后移，数组变为 [2, 5, 5, 6, 1, 3]。再比较下标0的值2，2<4，停止。key=4放到下标1，数组变成 [2, 4, 5, 6, 1, 3]。
第3轮：处理下标3的元素（值=6）
有序前缀是 [2, 4, 5]。待插入key=6。比较下标2的值5，5<6，不需要移动，key直接停在原地。数组仍然是 [2, 4, 5, 6, 1, 3]。
发现没有？这就体现出插入排序的“适应性”——如果待插入元素已经大于有序区末尾，这轮循环实际上只做了一次比较，没有元素移动，开销极小。数组越接近有序，这种情况出现得越频繁，算法整体就越快。
第4轮：处理下标4的元素（值=1）
有序前缀是 [2, 4, 5, 6]。待插入key=1。依次比较：6>1后移，5>1后移，4>1后移，2>1后移。数组变成 [2, 2, 4, 5, 6, 3]，比较完所有有序区元素，key=1放到下标0，结果 [1, 2, 4, 5, 6, 3]。
第5轮：处理下标5的元素（值=3）
有序前缀是 [1, 2, 4, 5, 6]。待插入key=3。6>3后移，5>3后移，4>3后移，2<3停止。key=3放到下标2位置。最终数组：
[1, 2, 3, 4, 5, 6]全过程经历了5轮，每轮有序前缀长度逐一递增，这就是插入排序的外层循环结构。直观上，处理第 i 个元素时，理论上它可能跟前面 i 个元素都比较一遍，最坏情况每轮比较次数随 i 线性增长。
2.3 时间复杂度的完整推导过程
插入排序的复杂度分析是一个经典的“循环嵌套求和”过程，我把它拆开讲透。
最好情况发生在数组完全有序时。此时拿每个待插入元素跟前面有序区最后一个元素比较一次，发现已经大于等于末尾元素，立即停止，所以第 i 轮只比较1次、移动0次。总比较次数是 n-1 次，时间复杂度为 O(n)。这是插入排序区别于冒泡和选择排序的关键优势——数据状态好时它真的很快。
最坏情况发生在数组完全逆序时，比如 [6, 5, 4, 3, 2, 1]。第 i 轮待插入元素需要跟前面 i 个有序元素全部比较一遍，并且每个元素都要后移。比较次数 = 1+2+3+...+(n-1) = n(n-1)/2，移动次数也是 n(n-1)/2。两项合起来依然是一个关于 n 的多项式，取最高阶项，时间复杂度为 O(n²)。
平均情况呢？严格推导比较复杂，可以这样理解：对随机排列的数据，大约一半的元素比待插入元素小、一半比它大，所以平均会比较一半的元素。总比较次数约 n²/4，仍然是 O(n²)。
空间复杂度很明确：只用了常数个临时变量（存key、存下标），没有随 n 增长的额外内存，所以是 O(1) 的原地排序。另外排序前后相同元素的相对位置不会改变——因为只有当遇到“严格大于 key”的元素才后移，等于 key 的元素不会越过它，它是稳定的。这几个结论在面试中经常被组合追问，建议把“最好 O(n)、最坏 O(n²)、平均 O(n²)、空间 O(1)、稳定”这一串背熟并理解含义。
3. 插入排序的Java实现与细节解析
3.1 基础版代码：从思路到可运行
插入排序的Java实现有很多写法，我推荐先在纸上写逻辑，再落地成代码。我自己习惯用“从后往前查找+后移”的框架，因为它天然契合数组插入的实现方式。下面这段代码就是插入排序的标准实现。
public class InsertionSort { /** * 对整型数组进行插入排序（升序） * @param arr 待排序数组，允许为 null */ public static void sort(int[] arr) { if (arr == null || arr.length < 2) { return; } // i 表示当前要插入的元素下标，从 1 开始，因为下标 0 天然有序 for (int i = 1; i < arr.length; i++) { int key = arr[i]; int j = i - 1; // 从有序区末尾往前找位置，同时把大于 key 的元素后移 while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } // 此时 j+1 就是 key 应该放的位置 arr[j + 1] = key; } } public static void main(String[] args) { int[] arr = {5, 2, 4, 6, 1, 3}; sort(arr); for (int num : arr) { System.out.print(num + " "); } } }这段代码有几点值得细说。int key = arr[i]这一步是先把待插入元素保存下来，因为接下来的后移操作会覆盖掉arr[i]原本的值，不保存就丢失了。while循环里arr[j] > key用的是严格大于，这保证了相等元素不会被交换到前面，稳定性由此而来。循环结束后，j指向的是“最后一个不小于 key 的元素”的位置，所以真正要插入的位置是j + 1。这个边界很多人容易搞错，我建议自己单步调试一遍就能彻底明白。
如果你需要排序的不是int[]而是对象数组，可以写一个泛型版本，核心逻辑完全一样，只是比较方式换成Comparable的compareTo方法：
public static <T extends Comparable<T>> void sort(T[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 1; i < arr.length; i++) { T key = arr[i]; int j = i - 1; while (j >= 0 && arr[j].compareTo(key) > 0) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } }给对象排序时要注意Comparator的用法：如果你想让排序规则可定制，把Comparator<? super T>作为参数传进来，compare(arr[j], key) > 0作为移动条件即可。这种写法在实现自定义排序时非常常用。
3.2 边界条件与隐藏细节的避坑指南
插入排序代码逻辑看似简单，但真正写对还是有几个隐藏坑的。第一个坑是数组长度小于2的情况，长度为0或1的数组天然有序，没必要进入循环，代码开头直接用length < 2早退，避免下面循环出错。第二个坑是while里的j >= 0判断一旦被省略，当 key 小于有序区全部元素时 j 会变成 -1，然后访问arr[-1]直接抛数组越界异常。很多新手在本地测正常数据没问题，一测最小值在首位的用例就崩，原因就是这个。
第三个坑是关于“相同元素是否被稳定排序”的验证。我在面试中见过有候选人写while (j >= 0 && arr[j] >= key)，这样的话如果数组中有相同的数，后面那个会更往前插，破坏稳定性。虽然单纯排序结果看起来也对，但在复杂排序场景（比如多字段排序）里会埋下隐患。稳定性这个特性不是悬空概念，它体现在代码细节上，>和>=的区别就在这里。
第四个坑可能更隐蔽：key变量的作用域。尝试把key的定义移到 for 循环外部，会导致代码语义完全不变但可读性下降；或者不小心在while里修改了i的值，外层循环计数错乱。我在带新人时反复强调：插入排序的每一轮里i是不变的，只有j在变化，改动key或者i都是逻辑错误。发现问题时先打印i、j、key、当前数组内容，90% 的问题一眼就能定位。
再补充一个和数组克隆有关的小细节。如果你在测试后想保留原始数组做对比，调用sort前先int[] original = arr.clone()，因为sort是原地排序，会直接修改传入的数组引用指向的内存内容。这个特性在工程上不算缺点，但测试时必须注意，否则容易因为“原数组没了”而误判排序逻辑有问题。
3.3 为什么移动比交换更高效
有些资料里写插入排序时，会教你用“交换法”——发现前一个元素比 key 大，就立刻交换两者，而不是后移。交换写法的核心代码是这样的：
for (int i = 1; i < arr.length; i++) { for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { swap(arr, j, j + 1); } }这种写法更直观，循环条件里直接比较arr[j] > arr[j + 1]，逻辑上很像冒泡排序的内层循环。但它比“移动法”慢，原因在于每次交换要执行三次赋值（temp = a; a = b; b = temp），而后移法每次只做一次赋值（arr[j + 1] = arr[j]）。虽然在大O复杂度上两者都是 O(n²)，但常数因子差着三倍。数据规模小的时候感受不明显，一旦数组长度到几万以上，差距会很直观。昊昊记得：插入排序的“性能点”在于减少赋值操作次数，不要在写实现时顺手引入不必要的交换。
再来对比一下冒泡排序。冒泡排序每次发现逆序就交换相邻元素，目的是把较大的元素逐步“冒”到末尾；而插入排序虽然也用相邻元素的后移，但它的目标是把新元素安插到有序前缀的合适位置。两者每轮的信息处理方式不同，导致在近乎有序的数据上表现差异巨大。教科书上还有个经典说法：冒泡排序的比较次数和移动次数是绑定的，而插入排序的比较次数和移动次数可以分离——用在二分插入排序里就能减少比较次数但移动次数不变。
4. 实战中的调试技巧与性能测试
4.1 用“打印每轮状态”的方式验证正确性
写排序算法最容易犯的毛病是“看着对，跑起来错”，或者是“代码能跑但排序结果错了”。我从实际调试经验出发，建议写一个printArray方法配合sort循环使用，在每轮插入完成后就把数组整个打印出来，观察有序前缀是不是真的在逐步变长。
public static void sortWithTrace(int[] arr) { for (int i = 1; i < arr.length; 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; System.out.print("第 " + i + " 轮后: "); for (int num : arr) { System.out.print(num + " "); } System.out.println(); } }我在带项目时经常让学习者用“打擂台”方式验证排序结果：sort之前复制一份数组，用 Java 自带的排序（比如Arrays.sort）排一遍，然后逐元素比对。如果两者结果一致，基本说明你的代码正确。这个方法听起来土，但在测试阶段非常高效，能在几秒内验证大量随机数据。注意这只是一个验证手段，不是生产逻辑，生产代码别这么干。
另一个实用小技巧是生成特殊测试用例来验证边界，包括：空数组、单元素数组、完全升序数组、完全降序数组、全部相同元素的数组、大数在前小数在后混合数组。每种用例都能暴露不同问题。比如全部相同元素的数组如果排序后和原来一致，说明稳定性没问题；完全升序数组如果跑出来效率极低，说明你可能没有利用提前停止的机会。
4.2 基准测试：到底能跑多快
想要直观感受插入排序在不同数据分布下的表现，可以写一个简单的基准测试。测试三大类数据：随机数组、近乎有序数组、完全逆序数组。每组数据取不同的规模，比如 1万、5万、10万。因为插入排序是 O(n²) 的算法，规模不要拉太高，10万在逆序情况下已经很吃力了，机器差点能跑好几秒。
public static void benchmark() { int n = 100000; // 随机数组 int[] randomArr = new int[n]; for (int i = 0; i < n; i++) { randomArr[i] = (int) (Math.random() * n); } // 近乎有序数组：先赋值成 0..n-1，再把其中少量元素打乱 int[] almostSortedArr = new int[n]; for (int i = 0; i < n; i++) { almostSortedArr[i] = i; } almostSortedArr[0] = n - 1; almostSortedArr[n - 1] = 0; // 逆序数组 int[] reverseArr = new int[n]; for (int i = 0; i < n; i++) { reverseArr[i] = n - i; } long start = System.nanoTime(); sort(randomArr.clone()); long randomTime = System.nanoTime() - start; start = System.nanoTime(); sort(almostSortedArr.clone()); long almostTime = System.nanoTime() - start; start = System.nanoTime(); sort(reverseArr.clone()); long reverseTime = System.nanoTime() - start; System.out.println("随机数据耗时: " + randomTime / 1_000_000.0 + " ms"); System.out.println("近乎有序耗时: " + almostTime / 1_000_000.0 + " ms"); System.out.println("逆序数据耗时: " + reverseTime / 1_000_000.0 + " ms"); }在我的测试机器上，10万随机数据大概耗时 2500ms 左右，10万近乎有序数据只有几十毫秒，逆序数据接近 5000ms 甚至更多。这三组数字放在一起，比任何理论讲解都直观。如果你在自己电脑上测出来“随机和逆序差不多快”，很可能你的随机数据生成方式有问题——注意Math.random()生成的是 [0,1) 小数，乘 n 后取整会分布得非常均匀，这是随机的，不是有序。
4.3 如何判断插入排序的适用场景
当我需要在一堆数据里做小规模排序时，插入排序反而是我的优先选择之一。原因不只是实现简单，而是数据规模小的时候，O(n²) 里的常数因子优势就凸显出来了——快速排序虽然复杂度低，但每次递归都有额外开销，几千个元素根本看不出优势。很多工业级排序库会在元素数量小于某个阈值（比如Java的Arrays.sort在部分底层实现里会对小数组用插入排序）时切换到插入排序，这是有工程依据的。
如果数据是“基本有序”的，比如只有少数几个元素错位、日志数据按时间写入但偶尔乱序，用插入排序会得到接近线性的表现。反之，如果是数据量大且完全随机，就不要选插入排序了，老老实实上快速排序或归并排序，否则数据上十万以后会感受到什么叫做“复杂度爆炸”。
我个人的经验是：对“插入排序还是选择排序”这个问题，先看稳定性需求和初始有序度。需要稳定且初始数据规模小，选插入排序；不在乎稳定性且就是图写起来简单，选择排序也可以。但如果你追求极限性能，插入排序在大数据量下不适合单打独斗，它更适合作为其他排序算法的补充工具。
5. 插入排序的变体与工程扩展
5.1 二分插入排序：把比较成本降下来
插入排序每轮在查找插入位置时，是在一个已经有序的数组里做线性查找。既然是有序数组，能不能用二分查找来定位？当然能。这个思路就是二分插入排序（Binary Insertion Sort）。实现方法：在每轮先用二分查找找到待插入元素应该放置的位置，然后一次性把该位置到当前末尾的元素整体后移，最后放入 key。
好处是查找时间从 O(i) 降到 O(log i)，但后移元素的成本仍然是 O(i)，所以总复杂度还是 O(n²)。你可能觉得白忙活，其实不然——对于“比较操作非常昂贵”的场景（比如比较两个复杂对象需要大量计算），减少比较次数是实打实的收益。Java里的Arrays.sort对对象的排序底层是归并排序的变体，但某些语言或场景里，二分插入排序作为小数组的收尾算法并不罕见。
代码实现二分查找时有个细节：我们要找的是“第一个大于 key 的位置”，而不是普通的“是否存在等于 key 的元素”。可以用Arrays.binarySearch，但它返回的结果和边界语义需要小心处理，我更推荐手写明一套「找最左侧插入点」的逻辑：
int low = 0; int high = i; // 注意不是 i-1，我们要找插入点 while (low < high) { int mid = (low + high) >>> 1; if (arr[mid] <= key) { low = mid + 1; } else { high = mid; } } // low 就是 key 应插入的位置这里的<=保证了如果在有序区里有和 key 相等的元素，插入点会落在这批相等元素的右边，从而维持稳定性。如果你写成<，插入点会落在左边，稳定性就被破坏了。这个细节可以说是二分插入排序最值得记忆的坑之一。
5.2 希尔排序：插入排序的“跨步”进化
插入排序的一个缺陷是“只能和相邻元素比较”，一个很小的元素如果在数组尾部，要慢慢往前挪很多步才能到正确位置。希尔排序就是冲着解决这个问题来的：它先让元素可以跳跃式地比较和移动，通过不断缩小步长（gap）来让数组逐步逼近有序，最后用步长为1的插入排序收尾。
希尔排序的工程价值在于它把插入排序从 O(n²) 提升到了平均接近 O(n^1.3) 左右，具体复杂度取决于步长序列的选择。常见的步长序列有希尔原始序列（n/2, n/4, ...）和更好的 Knuth 序列（1, 4, 13, 40, ...）。如果你已经能熟练写插入排序，希尔排序只需要在外层加一个 gap 循环，内层把j+1改成j+gap即可。这也是我总跟人说“插入排序不是孤立的知识点”的原因——它升级到希尔排序，只需要改动很少的代码。
我自己做排序模块时经常用希尔排序处理中等规模（几千到几万）的数据，因为它实现简单、不需要额外内存、对数据分布不敏感，表现非常稳定。虽然它的复杂度不如归并和快排，但在特定场景下性价比很高。
5.3 插入排序在框架源码中的应用
很多人以为插入排序只是教学概念，实际工程中没地方用。这个印象是错的。你去看主流语言的标准库，在排序算法的底层实现里，几乎都能找到插入排序的影子。比如部分JDK版本里对小数组（长度小于等于47）会直接用插入排序，因为这种规模下插入排序的常数优势远超复杂度劣势。在归并排序的merge过程中插入“如果左子序列已经全部小于右子序列”的提前退出优化时，也会用小数组排序作为最后的兜底。
还有一点容易忽视：插入排序的“在线性”特性让它很适合处理“流式数据”。比如一个系统不断接收新数据，你需要维护一个有序列表，每次插入一条新纪录，这种场景本质是单轮插入排序——新元素进来，冒泡到合适位置。用数组实现时，插入操作的时间是 O(n)，而插入排序本身就是反复执行这个操作。理解了这一点，你以后再看“维护有序数据结构”的需求就不会一头雾水。
6. 常见问题与排查技巧实录
6.1 代码“看起来对但结果不对”的排查思路
写插入排序最容易出现的两个症状：一是数组越界，二是结果接近有序但个别位置错乱。越界问题多出在j >= 0被漏写，或者在循环里写了arr[j]但没有先检查 j 是否为负数。结果错乱且规律是“后面元素跑到前面”——大概率是后移逻辑有覆盖漏洞，比如把arr[j + 1] = arr[j]写成arr[j] = key，结果把还没处理的元素覆盖了。
我排查这类问题时有个固定套路：先固定一组小规模数据，手动在草稿纸上模拟一遍，再对着代码单步执行，看每一步后的数组状态是否跟纸上一致。插入排序每轮只会改变从某个位置到当前下标之间的区间，其他区域不应该变化——如果你发现某轮连数组末尾都被动了，肯定是后移范围写错了。
6.2 稳定性验证怎么做
要验证你的插入排序是否稳定，光看排序结果看不出来，因为排序结果只跟元素的值有关，不关心相同值的先后顺序。构造一个含重复元素的测试数组，同时记录每个元素的原始位置，排序后检查相同值元素的相对顺序是否保留。
简单做法：先定义一个Element类，包含value和index两个字段，然后按value排序。排序完成后再扫描一遍数组，对每个相同取值的分组，检查index是否仍然递增。如果递增，排序就是稳定的；如果有任何一组乱序，就不稳定。这个测试同样适用于验证其他排序算法。
6.3 插入排序性能排查清单
如果你觉得自己的插入排序跑得比理论预期慢，先查三件事。第一，确认不是编译器的优化意外导致意外错误，比如在循环里重复创建大对象、频繁打印日志，这些会极大拉低性能。第二，确认输入数据的分布是否故意恶心算法——比如你生成“随机”数据的代码有 bug，实际生成了近乎逆序的数据。第三，检查你是否用的交换法而不是移动法，赋值操作的常数倍数在数据量大时会被放大。
下面是我整理的常见问题速查表，可以直接收藏：
| 问题现象 | 可能原因 | 解决方案 |
|---|---|---|
| 数组越界异常 | while条件漏掉j>=0 | 补全边界条件，注意短路顺序 |
| 排序后结果错乱 | key未保存或后移覆盖了未来元素 | 确认key存储、确认后移方向 |
| 相同元素顺序变化 | 使用了>=作为移动条件 | 改为>，保持稳定性 |
| 大数据量性能极差 | 用了交换法而非移动法 | 改为单赋值后移 |
| 近乎有序数据也慢 | 内层循环没能提前退出 | 检查比较条件是否写反 |
实战中最容易踩的坑就是这些，剩下的就是多写多测，形成肌肉记忆。
7. 从插入排序出发的算法学习心得
插入排序是我带初学者时最喜欢用来“破冰”的算法。它不像快速排序那样涉及递归和分区思想，也不像归并排序那样需要额外数组和合并技巧，代码量小，但麻雀虽小五脏俱全——循环结构、边界判断、元素移动、复杂度推导、稳定性分析，这些在更复杂算法里反复出现的核心概念，都能用它讲明白。
等你真正吃透插入排序，再学希尔排序会觉得毫不费力，学二分查找时会自然联想到“有序数组里找插入点”的场景，学链表操作时也会意识到“插入节点”和“数组后移”本质上是同一件事的两种存储实现。算法学习最忌讳的就是“背代码”，插入排序恰恰是最适合“理解后自己写”的一个算法。我建议你拿到这篇内容之后，别直接复制代码，先合上屏幕，在纸上画出框架，再凭记忆写一遍，看看能不能一次跑对。能一次写对，恭喜你，插入排序这关你已经过了。
