插入排序的核心逻辑是将数组分为已排序与未排序两部分，每次取未排序区首元素，从右向左比较并右移大于它的已排序元素，腾出空位后插入——关键在移位而非交换。
插入排序的核心逻辑是什么
插入排序本质是「摸牌」：每次取一个新元素，往已排好序的左侧子数组里找合适位置插进去。关键不是交换，而是把比它大的元素统一右移，腾出空位——这决定了必须从右往左比较，否则会覆盖未处理的数据。
手写时最容易错的边界和循环条件
常见错误是 i 或 j 的起始/终止值设错，导致越界或漏排。标准写法中：
-
i从1开始（第 0 个元素默认已“排好”） -
j从i-1开始，向前遍历到0（含），条件用j >= 0而非j > 0 - 内层循环退出后，要把暂存的
key放到j+1位置（不是j），因为最后一次j--后停在了插入点前一位
示例片段：
for (int i = 1; i < n; ++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; // 注意是 j+1
}如何适配不同数据类型和自定义比较
原生写法只支持 int 等可直接比较的类型。要通用，得用模板 + 比较函数：
立即学习“C++免费学习笔记（深入）”；
- 模板参数
T替代int，支持std::string、自定义结构体等 - 传入可调用对象
comp，默认用std::less<t>()</t>，这样就能反向排序或按成员比较 - 避免直接调用
，改用 <code>comp(arr[j], key)，保持语义一致
简化版模板签名：template<typename t typename compare="std::less<T">> void insertion_sort(T* arr, int n, Compare comp = {})</typename>
性能和适用场景的真实限制
插入排序不是用来跑大数据的。它的实际价值在特定场景：
- 小数组（
n ）：常被 <code>std::sort内部用作递归到底层的“收尾算法” - 近乎有序的数据：最好情况 O(n)，比快排/归并更轻量
- 在线排序：边读数据边维护有序序列，每次插入 O(n) 但无需重排全部
- 稳定排序：相等元素不会交换位置，这点容易被忽略
别在 10 万元素上硬刚——它没有优化余地，O(n²) 就是 O(n²)，编译器也榨不出花来。
