1. 插入排序一个你早就在用的排序算法排序算法是数据结构与算法学习中绕不开的基础内容。不管你是刚接触编程的初学者还是在准备面试的求职者插入排序通常都是最早接触的几个排序算法之一。但很多人在学习它时容易陷入一个误区死记硬背代码却没有真正理解排序的整个过程。等代码一背完过几天再问又忘了。其实插入排序并不难。甚至可以这样说你早在学编程之前就已经在生活中用过它了。想想打扑克牌的场景——你摸到一张新牌会把它插入到手中已经排好序的牌堆里的正确位置。这个动作的本质就是插入排序。这篇文章要做的就是把插入排序的整个执行过程拆开来看。我会用可想象的“动画帧”逐轮展示数据的变化配合完整可运行的 Java 代码以及复杂度分析、易错点、优化思路帮你彻底理解插入排序。不管你是零基础入门数据结构还是想复习排序算法的细节这篇文章都可以作为一份比较完整的学习笔记来阅读。2. 什么是插入排序先建立直观概念2.1 核心思想插入排序Insertion Sort是一种简单直观的排序算法。它的核心思想可以概括成一句话将未排序部分的元素逐个插入到已排序部分的正确位置中。这句话里有两个关键概念已排序部分通常指数组左侧的一段区域。初始时第一个元素可以视为已经排好序。未排序部分数组中剩余的元素。我们需要依次取出来插入到左侧正确的位置。这个过程会不断把“已排序部分”向右扩展直到整个数组都变成有序的。2.2 生活类比抓牌假设你正在打扑克牌左手拿着已经按从小到大排好的牌。现在你从桌面上新摸到一张牌你会从右往左比较手中的牌。一旦发现某张牌比新牌小或相等你就把新牌插到这张牌的右边。如果一直没找到比新牌小的牌那就插到最左边。这个过程就是一次“插入”。你摸了 N 张牌执行了 N 次插入手上的牌就全部有序了。插入排序模拟的正是这套逻辑。2.3 与选择排序、冒泡排序的区别很多初学者会把三种 O(n²) 的简单排序搞混这里简单做一个区分算法核心动作特点冒泡排序相邻元素两两比较大的往后冒每一轮确定一个最大值交换频繁选择排序从未排序部分选择最小值放到已排序末尾交换次数少一轮一次交换插入排序把新元素插入到已排序部分的正确位置对接近有序的数据表现极好从思想上来说插入排序和选择排序的“方向”是相反的。选择排序是从未排序区间挑一个最小的放到前面插入排序是从未排序区间拿一个元素往前面已经有序的区间里插。3. 从真实案例出发一个待排序数组的完整执行过程只看概念还不够。我们拿一个具体的数组来模拟插入排序的每一轮结果。这里我用“动画拆解”的方式把每一轮的状态展示出来。假设待排序数组为[5, 2, 4, 6, 1, 3]我们的目标是从小到大排序。3.1 初始状态[5, 2, 4, 6, 1, 3] ↑ currentIndex 0位置 0 的元素 5 可以视为“已排序部分”因为单独一个元素天然有序。3.2 第 1 轮插入元素 2取出未排序部分的第一个元素 2与已排序部分从右往左比较2 和 5 比较2 5所以 5 往后移一位。已排序部分已经到头2 放到位置 0。本轮结果[2, 5, 4, 6, 1, 3] ↑ ↑ 已排序部分可以看到2 成功插入到了 5 的前面。3.3 第 2 轮插入元素 4取出当前元素 4与已排序部分 [2, 5] 从右往左比较4 和 5 比较4 55 后移。4 和 2 比较4 2停止比较。4 放到 5 原来的位置。本轮结果[2, 4, 5, 6, 1, 3] ↑ ↑ ↑ 已排序部分3.4 第 3 轮插入元素 6取出当前元素 6与已排序部分 [2, 4, 5] 从右往左比较6 和 5 比较6 5不需要移动。本轮结果[2, 4, 5, 6, 1, 3] ↑ ↑ ↑ ↑ 已排序部分这是插入排序的一个特性如果当前元素已经比已排序部分最右侧的元素大那么它不用做任何移动。3.5 第 4 轮插入元素 1取出当前元素 1与已排序部分 [2, 4, 5, 6] 从右往左比较1 和 6 比较1 66 后移。1 和 5 比较1 55 后移。1 和 4 比较1 44 后移。1 和 2 比较1 22 后移。比较完所有元素1 放到位置 0。本轮结果[1, 2, 4, 5, 6, 3] ↑ ↑ ↑ ↑ ↑ 已排序部分3.6 第 5 轮插入元素 3取出当前元素 3与已排序部分 [1, 2, 4, 5, 6] 从右往左比较3 和 6 比较3 66 后移。3 和 5 比较3 55 后移。3 和 4 比较3 44 后移。3 和 2 比较3 2停止比较。3 放到 4 原来的位置。本轮结果[1, 2, 3, 4, 5, 6]排序完成。3.7 动画帧汇总表为了方便你理解每一轮的变化这里整理一张汇总表轮次取出元素比较过程摘要排序结果初始--[5, 2, 4, 6, 1, 3]第1轮25 后移2 插入位置0[2, 5, 4, 6, 1, 3]第2轮45 后移4 插入位置1[2, 4, 5, 6, 1, 3]第3轮6无需移动[2, 4, 5, 6, 1, 3]第4轮12、4、5、6 全部后移1 插入位置0[1, 2, 4, 5, 6, 3]第5轮34、5、6 后移3 插入位置2[1, 2, 3, 4, 5, 6]这张表就是你“脑补动画”的依据。每一轮从左到右扫描把未排序的第一个元素插入到左侧已排序区间的正确位置。4. 插入排序的代码实现从伪代码到 Java理解了执行过程写代码就顺理成章了。插入排序常见的实现有两种写法我们先看最容易记住的版本。4.1 伪代码描述for i 1 to n-1: key arr[i] j i - 1 while j 0 and arr[j] key: arr[j1] arr[j] j j - 1 arr[j1] key逻辑非常清晰外层循环从下标 1 开始因为下标 0 已经视为有序。key保存当前要插入的元素。内层循环从右向左扫描已排序区间一旦发现比key大的元素就后移。找到合适位置后把key放进去。4.2 Java 完整实现/** * 插入排序示例 * 文件路径src/main/java/sort/InsertionSort.java */ public class InsertionSort { public static void insertionSort(int[] arr) { if (arr null || arr.length 1) { return; } int n arr.length; 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--; } // 此时 j1 就是 key 要插入的位置 arr[j 1] key; } } public static void main(String[] args) { int[] arr {5, 2, 4, 6, 1, 3}; System.out.println(排序前); printArray(arr); insertionSort(arr); System.out.println(排序后); printArray(arr); } private static void printArray(int[] arr) { for (int num : arr) { System.out.print(num ); } System.out.println(); } }运行输出排序前 5 2 4 6 1 3 排序后 1 2 3 4 5 64.3 逐行解释关键代码int key arr[i];这一行保存当前待插入的元素。为什么要单独用一个变量保存因为后面的移动操作会覆盖arr[i]。如果不用key先保存元素就会被覆盖丢失。int j i - 1;j指向已排序部分的最后一个下标。我们从最后一个元素开始从右往左比较。while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; }这个循环有两个条件j 0防止数组下标越界。arr[j] key只有当前元素比key大才需要向右移动。注意用的是而不是这保证了排序的稳定性。如果两个元素值相等它们不会交换相对位置。arr[j 1] key;循环结束后j指向的是第一个比key小的元素位置。所以j1才是key的正确插入位置。4.4 Python 版本实现如果你主要使用 Python可以参考这个版本def insertion_sort(arr): for i in range(1, len(arr)): key arr[i] j i - 1 while j 0 and arr[j] key: arr[j 1] arr[j] j - 1 arr[j 1] key return arr if __name__ __main__: test_arr [5, 2, 4, 6, 1, 3] print(排序前, test_arr) sorted_arr insertion_sort(test_arr) print(排序后, sorted_arr)输出排序前 [5, 2, 4, 6, 1, 3] 排序后 [1, 2, 3, 4, 5, 6]两种语言的思路完全一致你掌握任一种都可以轻松翻译成另一种语言。5. 插入排序的时间复杂度与空间复杂度5.1 时间复杂度插入排序的时间复杂度取决于数据的初始顺序可以分为三种情况。最好情况数据已经完全有序每轮只需要比较一次发现key已经比已排序部分最后一个元素大直接结束。此时内层循环的执行次数是常数级别。总的比较次数为n - 1时间复杂度为 O(n)。最坏情况数据完全逆序比如[6, 5, 4, 3, 2, 1]。每轮插入一个元素时都需要把它和已排序部分的所有元素比较并移动。总的比较和移动次数约为1 2 3 ... (n-1) n(n-1)/2时间复杂度为 O(n²)。平均情况对于随机排列的数据平均比较次数接近最坏情况的一半但时间复杂度仍然为 O(n²)。5.2 空间复杂度插入排序是原地排序算法只需要一个额外的临时变量key来暂存元素。空间复杂度为 O(1)。5.3 稳定性插入排序是稳定排序。因为当遇到相等元素时我们的比较条件是arr[j] key而不是所以相等元素的相对顺序不会被改变。这一点在按多个字段排序的场景下很重要。比如先按姓名排序再按年龄排序稳定的排序算法可以让第二次排序时保留第一次排序的相对顺序。5.4 复杂度汇总表指标结果最好时间复杂度O(n)最坏时间复杂度O(n²)平均时间复杂度O(n²)空间复杂度O(1)稳定性稳定原地排序是6. 插入排序的常见优化折半插入排序基本的插入排序在查找插入位置时是从右往左逐个比较的。这个查找过程是线性的当数据量很大时会比较耗时。一个常见的优化思路是因为已排序部分是有序的所以可以用二分查找来快速定位插入位置。这就是折半插入排序。6.1 折半插入排序的思想折半插入排序的思路是在已排序区间[0, i-1]中使用二分查找找到key应该插入的位置。将插入位置之后的所有元素统一后移一位。将key放到插入位置。这样比较次数从 O(n) 降低到 O(log n)。但要注意移动元素的次数没有减少所以整体的时间复杂度仍然是 O(n²)。6.2 折半插入排序 Java 实现/** * 折半插入排序示例 * 文件路径src/main/java/sort/BinaryInsertionSort.java */ public class BinaryInsertionSort { public static void binaryInsertionSort(int[] arr) { if (arr null || arr.length 1) { return; } for (int i 1; i arr.length; i) { int key arr[i]; int left 0; int right i - 1; // 二分查找找到第一个大于 key 的位置 while (left right) { int mid (left right) / 2; if (arr[mid] key) { right mid - 1; } else { left mid 1; } } // left 的位置就是 key 要插入的位置 // 将 [left, i-1] 区间的元素统一后移一位 for (int j i - 1; j left; j--) { arr[j 1] arr[j]; } arr[left] key; } } public static void main(String[] args) { int[] arr {5, 2, 4, 6, 1, 3}; System.out.println(排序前); for (int num : arr) { System.out.print(num ); } System.out.println(); binaryInsertionSort(arr); System.out.println(排序后); for (int num : arr) { System.out.print(num ); } System.out.println(); } }6.3 折半插入排序的适用场景与局限折半插入排序相比普通插入排序减少了比较次数适合比较操作代价较高的场景。比如待排序元素是复杂对象比较函数开销很大。但由于移动次数不变在数据量较大时性能提升有限。折半插入排序仍然是一个 O(n²) 的排序算法它更适合作为一种教学优化思路来理解而不是实际大规模排序的首选。7. 插入排序和更高级排序算法的关系很多初学者会问既然插入排序是 O(n²)为什么我们还要学它为什么不直接学快排和归并这个问题很关键。插入排序虽然整体时间复杂度不如 O(n log n) 级别的排序算法但它在特定场景下有着不可替代的优势。7.1 希尔排序插入排序的升级版希尔排序的本质是分组插入排序。它先将整个数组按下标的一定增量分组对每组使用插入排序然后逐步缩小增量直到增量为 1此时整个数组基本有序再执行一次完整的插入排序。希尔排序之所以能突破 O(n²)核心思想是先通过大步长让数组快速接近有序再利用插入排序对接近有序数据的高效性完成最终排序。所以理解插入排序是理解希尔排序的必要前提。7.2 高级排序算法中的“插入排序影子”在一些高级排序算法中也能看到插入排序的身影。比如Java 的Arrays.sort()在对基本类型数组排序时使用的是双轴快速排序。当数组规模较小比如长度小于 47时会切换到插入排序因为此时插入排序的常数小、实际运行更快。Python 的sorted()底层使用 TimSort 算法它内部也融合了插入排序和归并排序的思想。在处理小规模子序列时插入排序被大量使用。可以说插入排序是很多工业级排序引擎的“原子操作”。这也是为什么不能因为它时间复杂度“不好看”就轻视它。7.3 插入排序与归并排序、快速排序对比排序算法最好复杂度平均复杂度最坏复杂度额外空间稳定性插入排序O(n)O(n²)O(n²)O(1)稳定希尔排序O(n log n)取决于增量序列O(n²)O(1)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n log n)O(n²)O(log n)不稳定8. 插入排序的常见问题与易错点在学习和写插入排序时有几个问题特别容易踩坑。我在这里集中整理一下。8.1 为什么内层循环是j 0而不是j 0这是一个非常经典的边界问题。如果你写成j 0那么当key比所有已排序元素都小、需要插入到下标 0 时你的循环可能在j 0处提前停止导致key被放到错误的位置。来看一个例子int[] arr {3, 1};i 1, key 1, j 0如果条件写成j 0while 循环直接不执行。执行arr[j 1] key得到arr[1] 1。数组变成[3, 1]排序失败。正确的写法必须让j可以走到-1再通过arr[j1] key把元素放到位置 0。8.2 为什么key要用临时变量保存看这个错误示例for (int i 1; i n; i) { int j i - 1; while (j 0 arr[j] arr[i]) { arr[j 1] arr[j]; j--; } arr[j 1] arr[i]; // 错误arr[i] 可能已经被覆盖了 }当 while 循环第一次执行arr[j1] arr[j]时如果j 1 i那么arr[i]的值就会被覆盖。后面再用arr[i]时得到的已经不是原来的待插入元素了。所以在进入内层循环之前必须用key保存arr[i]的值。8.3 数组为空或只有一个元素怎么办插入排序的代码应该对空数组和单元素数组做保护。你可以在方法开头加一个判断if (arr null || arr.length 1) { return; }这样既避免了空指针异常也避免了不必要的循环。8.4 插入排序的常见问题排查清单问题现象可能原因解决思路数组下标越界内层循环缺少j 0条件检查 while 条件是否完整排序结果不正确key未保存导致元素被覆盖确认key arr[i]是否在循环之前相等元素顺序被打乱比较条件使用了改成保持稳定性空数组报空指针没有做空值判断方法开头增加null和长度判断9. 插入排序的变体从后往前插入与从前往后插入你可能在网上看到过不同写法的插入排序。有的版本是从i 1开始往前扫描有的版本是在已排序区间中从前往后找位置。下面简单对比一下。9.1 从后往前比较本文的实现这是最常见的写法。优点是可以在移动元素的同时查找位置逻辑简洁。每移动一个元素就少一次比较。9.2 从前往后查找位置思路是先在已排序区间中找到第一个大于key的位置pos然后把[pos, i-1]的元素整体后移最后把key放到pos。public static void insertionSortFromLeft(int[] arr) { for (int i 1; i arr.length; i) { int key arr[i]; int pos i; // 从左往右找第一个大于 key 的位置 for (int j 0; j i; j) { if (arr[j] key) { pos j; break; } } // 将从 pos 到 i-1 的元素后移 for (int j i; j pos; j--) { arr[j] arr[j - 1]; } arr[pos] key; } }这种写法在理解上更直观但代码稍微长一点且需要两轮循环分别完成“查找”和“移动”。10. 插入排序实战用 Java 实现一个完整的排序工具类把前面学的整合起来我们写一个相对完整的工具类包含普通插入排序、折半插入排序和测试方法。/** * 插入排序工具类 * 文件路径src/main/java/sort/SortUtils.java */ public class SortUtils { /** * 普通插入排序 */ public static void insertionSort(int[] arr) { if (arr null || arr.length 1) { return; } 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; } } /** * 折半插入排序 */ public static void binaryInsertionSort(int[] arr) { if (arr null || arr.length 1) { return; } for (int i 1; i arr.length; i) { int key arr[i]; int left 0; int right i - 1; while (left right) { int mid (left right) / 2; if (arr[mid] key) { right mid - 1; } else { left mid 1; } } for (int j i - 1; j left; j--) { arr[j 1] arr[j]; } arr[left] key; } } /** * 检查数组是否升序有序 */ public static boolean isSorted(int[] arr) { for (int i 0; i arr.length - 1; i) { if (arr[i] arr[i 1]) { return false; } } return true; } /** * 打印数组 */ public static void printArray(int[] arr) { for (int num : arr) { System.out.print(num ); } System.out.println(); } public static void main(String[] args) { // 测试普通插入排序 int[] arr1 {5, 2, 4, 6, 1, 3}; insertionSort(arr1); System.out.print(普通插入排序结果); printArray(arr1); System.out.println(是否有序 isSorted(arr1)); // 测试折半插入排序 int[] arr2 {9, 7, 5, 3, 1, 2, 4, 6, 8}; binaryInsertionSort(arr2); System.out.print(折半插入排序结果); printArray(arr2); System.out.println(是否有序 isSorted(arr2)); // 测试极端情况 int[] arr3 {1}; insertionSort(arr3); System.out.print(单元素排序结果); printArray(arr3); } }运行输出普通插入排序结果1 2 3 4 5 6 是否有序true 折半插入排序结果1 2 3 4 5 6 7 8 9 是否有序true 单元素排序结果111. 插入排序中的稳定性为什么重要稳定性是排序算法的一个重要属性。所谓稳定是指如果两个元素的值相等排序后它们的相对顺序不变。举个例子。假设有一组学生记录先按学号排序再按成绩排序。如果第二次排序算法是稳定的那么在成绩相同的学生中学号仍然保持升序。如果算法不稳定第二次排序可能会打乱学号顺序。插入排序的稳定性来自比较条件while (j 0 arr[j] key)当arr[j] key时循环停止key会被放在相等元素的右侧。因此相等元素的相对顺序不会改变。如果你不小心把写成了排序结果在数值上依然正确但稳定性会被破坏。这在某些业务场景下会产生问题。所以在学习算法时不仅要关注“排序对不对”还要关注“排序稳不稳”。12. 插入排序的工程实践建议了解了原理和代码最后聊聊在真实工程中怎么用好插入排序。12.1 适合使用插入排序的场景数据规模小当数组长度小于 50 时插入排序的实际执行速度往往不输给快速排序因为它的常数因子小代码逻辑简单。数据基本有序如果大部分元素已经处于正确位置插入排序每轮几乎不需要移动元素时间复杂度可以接近 O(n)。内存受限的环境插入排序只需要 O(1) 的额外空间非常适合嵌入式系统或内存受限的场景。作为其他排序的底层优化在快速排序划分到小区间时改用插入排序可以提升整体性能。12.2 不适合使用插入排序的场景海量随机数据比如百万级以上的随机数组O(n²) 的复杂度会让排序时间急剧增长。对时间要求极高的实时系统插入排序的最坏情况不够稳定需要更可预期的 O(n log n) 算法。12.3 工程中的最佳实践在实现插入排序时始终保留key临时变量不要直接使用arr[i]作为比较基准。考虑数据特征。如果数据基本有序插入排序是很好的选择如果不确定优先使用Arrays.sort()等经过高度优化的内置排序。在算法面试中插入排序通常不会单独作为考点但它经常作为希尔排序、TimSort 等算法的基础。理解它的执行过程有助于后续学习更复杂的排序算法。13. 总结从“看懂动画”到“理解排序”回到文章开头的问题。学习插入排序时最难的不是记住代码而是真正理解“每一轮发生了什么”。建议你按下面的顺序再自查一遍我能不能口述插入排序的执行过程我能不能画出每一轮数组的状态我能不能解释为什么j 0是必要的我能不能说清楚插入排序为什么是稳定的我能不能手写完整的插入排序代码并在编译器里跑通如果以上五个问题都能回答上来说明你已经真正掌握了插入排序。接下来可以继续学习折半插入排序、希尔排序以及归并排序、快速排序等更高级的排序算法。插入排序是很多排序算法的基础打好这一关后面的路会顺畅很多。