插入排序
最后更新
插入排序每次处理一个元素，逐步建立有序数组。它取出下一个未排序的元素（称为“键”），把有序区中所有比它大的元素向右移一位，再把键放进空出来的位置。这和大多数人整理手中扑克牌的方式一模一样。点击上方的“播放”，观看每个键被插入的过程，也可以一步一步查看每次移动。
插入排序在数据量小或几乎有序时非常快：如果数据已经有序，它只需 O(n) 时间。正因如此，许多混合排序算法在处理小的子数组时都会改用插入排序。
时间复杂度与空间复杂度
| 情况 | 复杂度 | 说明 |
|---|---|---|
| 最好情况 | O(n) | 已经有序 |
| 平均情况 | O(n²) | 随机顺序 |
| 最坏情况 | O(n²) | 逆序排列 |
| 空间 | O(1) | 原地排序 |
| 稳定性 | 稳定 | 相等元素保持原有的相对顺序 |
分步说明
| 步骤 | 发生了什么 |
|---|---|
| 1 | 把第一个元素看作长度为一的有序区。 |
| 2 | 取下一个元素作为键。 |
| 3 | 把有序区中所有比键大的元素向右移一位。 |
| 4 | 把键插入空出来的位置。 |
| 5 | 重复以上步骤，直到所有元素都插入完毕。 |
实例演示
对 [5, 2, 4, 1] 排序：
| 轮次 | 数组 | 操作 |
|---|---|---|
| 开始 | [5, 2, 4, 1] | 5 是最初长度为一的有序区。 |
| 1 | [2, 5, 4, 1] | 键 2：把 5 右移，把 2 插到最前面。 |
| 2 | [2, 4, 5, 1] | 键 4：把 5 右移，2 更小所以停下，插入 4。 |
| 3 | [1, 2, 4, 5] | 键 1：把 5、4、2 依次右移，把 1 插到最前面。 |
| 完成 | [1, 2, 4, 5] | 所有元素都已插入，数组排序完成。 |
什么时候用插入排序
| 适合使用 | 不适合使用 |
|---|---|
数组很小（大约 n < 20）。 | 数组很大且顺序随机。 |
数据已经接近有序，可以达到 O(n) 的最好情况。 | 你需要有保证的 O(n log n) 最坏情况。 |
你需要稳定的原地排序，只用 O(1) 额外空间。 | 移动元素的代价很高，因为它要做大量移位。 |
| 数据陆续到达，需要随时保持有序（在线排序）。 | 输入是逆序的，这正是它 O(n²) 的最坏情况。 |
Insertion Sort 代码
简洁、可运行的 Insertion Sort 实现，提供 Python, JavaScript, Java, C++, C, Pseudocode 版本。选择一种语言，复制代码，或在 Coddy 在线编辑器中直接打开。
Insertion Sort 的 Python 代码
Python
1def insertion_sort(a):2 for i in range(1, len(a)):3 key = a[i]4 j = i - 15 # Shift larger elements one slot to the right6 while j >= 0 and a[j] > key:7 a[j + 1] = a[j]8 j -= 19 a[j + 1] = key10 return a11
12
13nums = [7, 3, 9, 1, 5, 8, 2]14print("Before:", nums)15insertion_sort(nums)16print("After: ", nums)Insertion Sort 的 JavaScript 代码
JavaScript
1function insertionSort(a) {2 for (let i = 1; i < a.length; i++) {3 const key = a[i];4 let j = i - 1;5 // Shift larger elements right to open a slot for key6 while (j >= 0 && a[j] > key) {7 a[j + 1] = a[j];8 j--;9 }10 a[j + 1] = key;11 }12 return a;13}14
15const data = [5, 2, 9, 1, 7, 3];16console.log("Before:", data);17console.log("Sorted:", insertionSort([...data]));Insertion Sort 的 Java 代码
Java
1import java.util.Arrays;2
3public class Main {4 static void insertionSort(int[] arr) {5 for (int i = 1; i < arr.length; i++) {6 int key = arr[i];7 int j = i - 1;8 // Shift larger elements one slot to the right9 while (j >= 0 && arr[j] > key) {10 arr[j + 1] = arr[j];11 j--;12 }13 arr[j + 1] = key;14 }15 }16
17 public static void main(String[] args) {18 int[] arr = {7, 3, 9, 1, 5, 8, 2};19 System.out.println("Before: " + Arrays.toString(arr));20 insertionSort(arr);21 System.out.println("After: " + Arrays.toString(arr));22 }23}Insertion Sort 的 C++ 代码
C++
1#include <iostream>2#include <vector>3
4void printVec(const std::vector<int>& a) {5 for (int x : a) std::cout << x << " ";6 std::cout << "\n";7}8
9void insertionSort(std::vector<int>& a) {10 for (size_t i = 1; i < a.size(); ++i) {11 int key = a[i];12 int j = static_cast<int>(i) - 1;13 // Shift larger elements one slot to the right14 while (j >= 0 && a[j] > key) {15 a[j + 1] = a[j];16 --j;17 }18 a[j + 1] = key;19 }20}21
22int main() {23 std::vector<int> data = {7, 3, 9, 1, 5, 8, 2};24 std::cout << "Before: ";25 printVec(data);26 insertionSort(data);27 std::cout << "After: ";28 printVec(data);29 return 0;30}Insertion Sort 的 C 代码
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void insertionSort(int a[], int n) {9 for (int i = 1; i < n; i++) {10 int key = a[i];11 int j = i - 1;12 // Shift larger elements one slot to the right13 while (j >= 0 && a[j] > key) {14 a[j + 1] = a[j];15 j--;16 }17 a[j + 1] = key;18 }19}20
21int main(void) {22 int data[] = {7, 3, 9, 1, 5, 8, 2};23 int n = sizeof(data) / sizeof(data[0]);24 printf("Before: ");25 printArr(data, n);26 insertionSort(data, n);27 printf("After: ");28 printArr(data, n);29 return 0;30}Insertion Sort 的 Pseudocode 代码
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74nums[1] ← 75nums[2] ← 36nums[3] ← 97nums[4] ← 18nums[5] ← 59nums[6] ← 810nums[7] ← 211DECLARE i : INTEGER12DECLARE j : INTEGER13DECLARE key : INTEGER14
15// Insert each value into the sorted part on its left16FOR i ← 2 TO n17 key ← nums[i]18 j ← i - 119 WHILE j > 0 AND nums[j] > key DO20 nums[j + 1] ← nums[j]21 j ← j - 122 ENDWHILE23 nums[j + 1] ← key24NEXT i25
26FOR i ← 1 TO n27 OUTPUT nums[i]28NEXT i插入排序常见问题
插入排序的时间复杂度是多少？
插入排序在平均和最坏情况下都是
O(n²)，但在已经有序或接近有序的数组上只需 O(n)。它只用 O(1) 的额外空间。插入排序是稳定的吗？
是的。插入排序只移动严格大于键的元素，所以相等的元素不会互相越过，它们的相对顺序得以保留。
什么时候应该用插入排序？
适合用于小数组，或者已经差不多有序的数据。由于开销低、最好情况又能自适应，像 Timsort 这样的混合算法会用它来处理短的有序段。
插入排序和冒泡排序有什么区别？
两者都是
O(n²) 的比较排序，但插入排序通过移动元素为键腾出位置，而冒泡排序反复交换相邻的逆序对。插入排序的写入次数通常更少，实际表现更好，尤其是在接近有序的数据上，能达到 O(n) 的最好情况。为什么在小数组上插入排序比归并排序快？
插入排序的常数开销很低，没有递归，也不需要额外分配内存，所以在小规模输入上，尽管渐近复杂度更差，它仍然能胜过
O(n log n) 的排序算法。这正是 Timsort 和内省排序（introsort）等混合排序在小的子数组上改用插入排序的原因。插入排序更适合链表还是数组？
插入排序通常针对数组编写，主要开销在于移动元素。在链表上，你可以把节点直接接到正确位置，省去移动，但也失去了快速随机访问，所以每个元素找插入位置仍要线性时间，总开销依然是
O(n²)。相关资源
更多可视化
