为何不同实现的数组版插入排序运行时间差异巨大？

嘿，这个问题挺有意思的！插入排序的O(n²)复杂度在大数据量下会把细节无限放大，哪怕是实现上的微小差异，都会带来巨大的耗时差距。我猜你遇到的大概率是元素移动方式的不同，这是插入排序实现里影响性能最关键的点之一，咱们来拆解一下：

• 逐个交换 vs 批量移动
  很多新手写插入排序时，会用相邻元素交换的方式把当前元素“挪”到正确位置，代码大概是这样：

  for (int i = 1; i < arr.length; i++) {
      int j = i;
      while (j > 0 && arr[j] < arr[j-1]) {
          // 交换相邻元素，一次交换要做3次内存赋值
          int temp = arr[j];
          arr[j] = arr[j-1];
          arr[j-1] = temp;
          j--;
      }
  }
  

  而更高效的实现会先把当前元素存起来，然后把前面比它大的元素整体向后移动一位，最后再把当前元素插入到空位：

  for (int i = 1; i < arr.length; i++) {
      int current = arr[i];
      int j = i - 1;
      // 只做单步赋值，把大元素往后移
      while (j >= 0 && arr[j] > current) {
          arr[j+1] = arr[j];
          j--;
      }
      arr[j+1] = current;
  }
  

  你算笔账就懂了：每次交换是3次内存操作，而批量移动是1次。对于10万元素的逆序数组（插入排序的最坏情况），前者的总赋值次数是3*(n²/2)，后者是n²/2，光是这一点就差了3倍左右。再加上CPU缓存的影响，实际跑出6500ms的差距完全合理。

• CPU缓存局部性的加持
  批量移动的方式里，数组的访问是连续的，CPU的缓存预取机制能完美发挥作用——每次加载一块内存到高速缓存里，后续的移动操作都能在缓存里完成，速度快到飞起。而交换的方式虽然也是连续访问，但每次交换涉及两次数组读写，缓存命中率会稍低，在10万级别的数据量下，这种差异会被指数级放大。

• 循环冗余操作的叠加影响
  有些实现可能在循环条件里做了多余的判断，比如每次都重复计算数组长度，或者用了低效的循环结构。不过这种影响一般比前两者小，但如果刚好你的两种实现还存在这类差异，那耗时差距会进一步拉大。

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