插入排序算法中key变量的必要性：两种实现的差异分析

问题描述 #

我正在学习插入排序（Insertion Sort）的运行机制。以下是多个网站中描述的原始插入排序算法代码：

for (int i = 0; i < a.length; i++) { 
    int key = a[i]; 
    int j = i; 
    while (j > 0 && a[j-1] > key) { 
        swap(a, j, j - 1); 
        j--; 
    } 
    a[j] = key; 
}

在学习过程中我发现，以下这段不使用key变量的代码实现了完全相同的功能：

for (int i = 0; i < a.length; i++) { 
    int j = i; 
    while (j > 0 && a[j-1] > a[j]) { 
        swap(a, j, j - 1); 
        j--; 
    } 
}

我的问题是：原始算法中为何需要key变量？它是否是为了处理第二种算法未考虑到的边缘情况？如果是，这些边缘情况具体是什么？经测试，两种算法的交换次数相同，我无法理解使用key变量的差异所在。

回答 #

嘿，这个问题问得特别到位！先给你吃个定心丸：这两种实现功能完全等价，不存在第二种算法没覆盖的边缘情况——不管是空数组、单元素数组、已排序数组还是逆序数组，两者的运行结果都完全一致。那原始算法里的key变量到底有啥用？核心原因是减少底层赋值操作，提升算法效率，同时更贴合插入排序的核心逻辑。

1. 底层操作的差异：赋值次数天差地别 #

先拆解两种算法的底层行为：

• 你贴的第二种算法，每次swap(a, j, j-1)本质上是三次赋值（假设swap的标准实现如下）：

  void swap(int[] a, int x, int y) {
      int temp = a[x];
      a[x] = a[y];
      a[y] = temp;
  }
  

  也就是说，每一次循环里的交换操作，都要做3次值的转移。

• 而原始算法里的key变量，是先把a[i]的值暂存起来，然后只做单向的赋值移动（把a[j-1]的值覆盖到a[j]），最后再把key放到最终的正确位置。比如当需要把元素向前移动k次时：

  • 第二种算法需要3*k次赋值；
  • 原始算法只需要k+1次赋值（k次单向移动，1次把key放入目标位置）。

举个直观的例子：假设数组是[5,4,3,2,1]，当i=4（对应元素1）时，需要向前移动4次：

• 第二种算法：4次swap → 12次赋值；
• 原始算法：4次单向移动 + 1次key赋值 → 5次赋值。

你说两种算法的交换次数相同，这是对的——两者的比较次数和“交换/移动”的逻辑次数确实一致，但底层的赋值操作次数差了好几倍，原始算法的性能明显更优。

2. 逻辑贴合度：更符合插入排序的“插入”本质 #

原始算法的写法更直观地体现了插入排序的核心思路：把当前待排序的元素“拿出来”（存在key里），然后将前面所有比它大的元素都往后挪一位，最后把这个元素“插入”到空出来的位置。

而第二种算法是通过相邻元素交换来实现挪位置的效果，本质上是用“冒泡”的思路模拟插入排序，虽然结果一样，但逻辑上和插入排序的核心概念贴合度更低。

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