插入排序的交换次数定义与代码优化相关疑问

先回顾背景：面试题要求用最少交换次数排序数组 [0, 9, 3, 7, 15]，实际验证后选择排序和插入排序都仅需2次交换，且插入排序在数组近乎有序时表现更优，但针对标准插入排序实现有以下两个疑问：

疑问1：为何不为arr[j+1] = curr添加条件判断（如if (j !== i - 1)），避免位置正确时执行无意义操作？ #

首先明确：当元素已经处于正确位置时，j会最终走到i-1，此时执行arr[j+1] = curr确实等价于arr[i] = arr[i]，属于无意义的赋值操作。但标准实现里不添加这个判断的原因主要有三点：

• 性能收益可忽略：这种无意义赋值的开销极小，反而添加条件判断会引入分支逻辑，现代CPU的分支预测如果频繁遇到不命中的情况，反而会带来更大的性能损耗。
• 代码简洁性优先：标准插入排序的核心逻辑是“遍历-移动-插入”，添加额外判断会让代码逻辑变得冗余，降低可读性，不符合算法实现追求简洁直观的原则。
• 实际场景占比低：在大多数排序场景中，元素需要调整位置的情况远多于已经在正确位置的情况，添加判断的收益远抵不上代码复杂度提升的成本。

疑问2：为何称该场景下插入排序仅需2次交换，实际看起来却像4次？如何区分arr[j+1] = arr[j]与arr[j+1] = curr是否属于“交换”？ #

这里的核心是区分“交换操作”和“移动操作”：

• 真正的交换操作是指两个元素互换位置，需要三次赋值（比如temp = a; a = b; b = temp），这才是统计“交换次数”时的标准。
• 插入排序中的arr[j+1] = arr[j]属于元素移动，是将前面的元素向后平移，为当前元素腾出位置；而arr[j+1] = curr是最终的插入操作。这一系列操作本质上是完成一次“逻辑上的元素位置调整”，而非多次交换。

回到题目中的数组[0,9,3,7,15]：

1. 处理元素3时，通过移动9腾出位置，最终将3插入到9的前面，这整个过程等价于一次“3和9的位置调整”，算1次交换。
2. 处理元素7时，通过移动9腾出位置，最终将7插入到9的前面，这等价于一次“7和9的位置调整”，算第2次交换。

所以统计“最少交换次数”时，是按这种逻辑上的元素位置置换次数来计算，而非单个赋值操作的次数。插入排序的移动是单向的批量平移，和选择排序中一次互换两个元素的“交换”虽然操作形式不同，但从“元素位置调整的本质次数”来看，都是2次。

内容的提问来源于stack exchange，提问作者Ty Cali