移动法插入排序的核心逻辑是通过逐个后移较大元素腾出空位，再将当前元素填入；关键在于用arr[j+1]=arr[j]移动元素，最后将key赋给arr[j+1]。
移动法插入排序的核心逻辑是什么
移动法插入排序不借助额外数组或 swap，而是通过逐个后移较大元素腾出空位，再把当前元素填入。关键在于理解「空位」如何产生和维护——每次外层循环取 arr[i] 为待插入元素，内层从 i-1 开始向前扫描，只要 arr[j] > key，就执行 arr[j+1] = arr[j]，最后把 key 赋给 arr[j+1]（注意不是 arr[j]）。
标准移动法插入排序代码怎么写
以下是最简可用版本，适用于 std::vector 或原生数组：
void insertionSort(std::vector& arr) { for (int i = 1; i < arr.size(); ++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 >= 0，导致数组越界访问 - 填入语句写成
arr[j] = key，会覆盖未比较的元素或越界 - 用
std::swap替代移动，那就不是「移动法」而是交换法了
移动法和交换法在性能上有什么实际差异
移动法单次插入最多移动 i 个元素，但只写入不读取（除比较外）；交换法每次 swap 都是两次读+两次写。实测在 int 数组上，移动法通常快 10%–20%，尤其在部分有序数据中优势更明显。但若元素类型很大（比如含深拷贝的 class），移动操作本身开销变高，此时应考虑改用指针/引用排序，或直接用 std::sort。
立即学习“C++免费学习笔记（深入）”；
注意：std::move 在这里不适用——插入排序要求稳定、原地、顺序访问，std::move 不改变赋值语义，反而可能引入不必要的移动构造开销。
边界场景怎么验证是否正确
测试时必须覆盖这几类输入：
- 空数组或单元素：
{}、{5}→ 不进外层循环 - 已排序：
{1,2,3,4}→ 内层循环全跳过，仅做比较 - 逆序：
{4,3,2,1}→ 每轮都移动全部前面元素 - 含重复值：
{3,1,3,2}→ 确保稳定性（相同值的相对位置不变）
最容易被忽略的是：当 key 是最小值时，j 会减到 -1，此时 arr[j+1] 即 arr[0]，必须确保这个下标合法——所以内层 while 条件里 j >= 0 不能省略，也不能写成 j > 0。
