C++学习笔记【算法】——插入排序算法

Ne0inhk

21 Mar 2026 — 7 min read

插入排序算法原理详解

算法原理

插入排序是一种基于比较的原地排序算法，它通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。类似于整理扑克牌的过程。

核心思想

分界思想：将数组分为已排序部分和未排序部分
逐个插入：从未排序部分取出元素，插入到已排序部分的正确位置
元素后移：在插入过程中，需要将已排序部分中比当前元素大的元素向后移动

算法步骤（升序为例）

text

初始：[5, 3, 8, 1, 2] 第1轮：第一个元素5视为已排序当前：[5 | 3, 8, 1, 2] 第2轮：取元素3 与已排序部分比较：3 < 5 将5后移，3插入到5的位置结果：[3, 5 | 8, 1, 2] 第3轮：取元素8 与已排序部分比较：8 > 5，位置正确结果：[3, 5, 8 | 1, 2] 第4轮：取元素1 与已排序部分从右向左比较： 1 < 8 → 8后移 1 < 5 → 5后移 1 < 3 → 3后移 1插入到最前面结果：[1, 3, 5, 8 | 2] 第5轮：取元素2 与已排序部分从右向左比较： 2 < 8 → 8后移 2 < 5 → 5后移 2 < 3 → 3后移 2 > 1 → 插入到1后面结果：[1, 2, 3, 5, 8]

时间复杂度分析

最坏情况：O(n²) - 数组完全逆序
最好情况：O(n) - 数组已有序
平均情况：O(n²)
空间复杂度：O(1) - 原地排序

C++实现代码

cpp

#include <iostream> #include <vector> using namespace std; // 基础插入排序 void insertionSort(vector<int>& arr) { int n = arr.size(); // 从第二个元素开始（第一个元素视为已排序） 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--; } // 插入key到正确位置 arr[j + 1] = key; } } // 带打印过程的插入排序（用于演示） void insertionSortWithSteps(vector<int>& arr) { int n = arr.size(); for (int i = 1; i < n; i++) { int key = arr[i]; int j = i - 1; cout << "第" << i << "轮，处理元素 arr[" << i << "] = " << key << endl; cout << "当前数组: "; for (int k = 0; k <= i; k++) { cout << arr[k] << " "; } cout << "| "; for (int k = i + 1; k < n; k++) { cout << arr[k] << " "; } cout << endl; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; cout << "插入后: "; for (int k = 0; k <= i; k++) { cout << arr[k] << " "; } if (i < n - 1) { cout << "| "; for (int k = i + 1; k < n; k++) { cout << arr[k] << " "; } } cout << endl << endl; } } // 使用二分查找优化的插入排序 void binaryInsertionSort(vector<int>& arr) { int n = arr.size(); for (int i = 1; i < n; i++) { int key = arr[i]; // 使用二分查找找到插入位置 int left = 0, right = i - 1; while (left <= right) { int mid = left + (right - left) / 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; } } // 递归版本的插入排序 void recursiveInsertionSort(vector<int>& arr, int n) { if (n <= 1) return; // 先对前n-1个元素排序 recursiveInsertionSort(arr, n - 1); // 将第n个元素插入到正确位置 int key = arr[n - 1]; int j = n - 2; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } // 打印数组 void printArray(const vector<int>& arr) { for (int num : arr) { cout << num << " "; } cout << endl; } // 测试函数 int main() { // 测试基础插入排序 vector<int> arr1 = {12, 11, 13, 5, 6}; cout << "=== 基础插入排序 ===" << endl; cout << "原始数组: "; printArray(arr1); insertionSort(arr1); cout << "排序后: "; printArray(arr1); // 测试带步骤的插入排序 vector<int> arr2 = {5, 3, 8, 1, 2}; cout << "\n=== 带步骤的插入排序（演示） ===" << endl; cout << "原始数组: "; printArray(arr2); cout << endl; insertionSortWithSteps(arr2); // 测试二分查找优化的插入排序 vector<int> arr3 = {20, 10, 30, 5, 15, 25}; cout << "\n=== 二分查找优化的插入排序 ===" << endl; cout << "原始数组: "; printArray(arr3); binaryInsertionSort(arr3); cout << "排序后: "; printArray(arr3); // 测试递归版本的插入排序 vector<int> arr4 = {7, 2, 9, 4, 1, 8}; cout << "\n=== 递归版本的插入排序 ===" << endl; cout << "原始数组: "; printArray(arr4); recursiveInsertionSort(arr4, arr4.size()); cout << "排序后: "; printArray(arr4); return 0; }

算法特点

优点：

实现简单：代码简洁，逻辑清晰
原地排序：只需要常数级别的额外空间
稳定排序：相等元素的相对位置不会改变
自适应：对部分有序数组效率高
在线算法：可以边接收数据边排序

缺点：

效率低：时间复杂度为O(n²)，不适合大数据集
移动操作多：需要频繁移动元素

实际应用场景

1. 小规模数据

cpp

// 小数组排序（通常n < 20） vector<int> smallArray = {5, 2, 8, 1}; insertionSort(smallArray);

2. 近乎有序的数组

cpp

// 已基本有序的数组 vector<int> nearlySorted = {1, 2, 4, 3, 5, 6, 8, 7}; insertionSort(nearlySorted); // 接近O(n)的时间复杂度

3. 作为高级算法的子程序

cpp

// 在快速排序等算法中，对小规模子数组使用插入排序 void quickSortWithInsertion(vector<int>& arr, int low, int high) { if (high - low + 1 <= 10) { // 子数组长度小于等于10时使用插入排序 insertionSortForSubarray(arr, low, high); return; } // ... 快速排序的其余部分 }

4. 链表排序

cpp

// 插入排序非常适合链表，因为不需要移动大量元素 struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* insertionSortList(ListNode* head) { if (!head || !head->next) return head; ListNode* dummy = new ListNode(0); ListNode* curr = head; while (curr) { ListNode* prev = dummy; ListNode* nextNode = curr->next; // 找到插入位置 while (prev->next && prev->next->val < curr->val) { prev = prev->next; } // 插入节点 curr->next = prev->next; prev->next = curr; curr = nextNode; } return dummy->next; }

性能对比

不同场景下的表现：

完全逆序数组：需要n(n-1)/2次比较和移动，最差性能
完全有序数组：只需n-1次比较，无需移动，最佳性能
随机数组：平均需要n²/4次比较和移动

与其他排序算法的比较：

比冒泡排序快：插入排序的平均移动次数更少
比选择排序稳定：选择排序是不稳定排序
适合小数据：当n≤20时，插入排序常比O(n log n)算法更快

优化技巧

1. 二分查找优化

cpp

// 使用二分查找减少比较次数，但移动次数不变 // 时间复杂度：比较次数O(n log n)，移动次数O(n²)

2. 哨兵技巧

cpp

// 将数组第一个元素作为哨兵，简化边界检查 void insertionSortWithSentinel(vector<int>& arr) { int n = arr.size(); // 先找到最小元素放到最前面作为哨兵 int minIndex = 0; for (int i = 1; i < n; i++) { if (arr[i] < arr[minIndex]) minIndex = i; } swap(arr[0], arr[minIndex]); // 排序时不需要检查j>=0 for (int i = 2; i < n; i++) { int key = arr[i]; int j = i - 1; while (arr[j] > key) { // 不用检查j>=0 arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } }

3. 希尔排序

cpp

// 插入排序的改进版，通过分组进行插入排序 void shellSort(vector<int>& arr) { int n = arr.size(); // 使用Knuth序列确定间隔 int gap = 1; while (gap < n / 3) { gap = 3 * gap + 1; } while (gap >= 1) { // 对每个间隔进行插入排序 for (int i = gap; i < n; i++) { int key = arr[i]; int j = i; while (j >= gap && arr[j - gap] > key) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = key; } gap /= 3; } }

插入排序是理解更复杂排序算法的基础，它在实际应用中虽然不适用于大数据集，但在特定场景下（小规模数据、近乎有序数据）仍有其优势，也是许多高级排序算法的重要组成部分。