两种Java插入排序实现对比：Sedgewick版本与移位版本哪个更优？

二者存在实质性的性能差异，使用临时变量的第二个版本实际运行效率更高，你并没有过度思考。

两种实现代码回顾 #

版本1：Sedgewick教学版插入排序 #

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

版本2：移位优化版插入排序 #

for(int i = 1 ; i < arr.length ; i++){
      int j = i;
      int temp = arr[j];
      while(j >= 1 && temp < arr[j-1]){
           arr[j] = arr[j-1];
           j--;
      }
      arr[j] = temp;
}

核心差异在于赋值操作的开销 #

• 版本1每次内层循环都会执行一次元素交换，一次交换隐含了3次赋值操作：临时变量存a[j]、a[j]赋值为a[j-1]、a[j-1]赋值为临时变量。如果当前元素需要往前移动k位，就要执行3k次数组赋值。
• 版本2把待插入元素提前存到临时变量里，每次内层循环只执行1次赋值arr[j] = arr[j-1]，循环结束后再把临时变量放到最终位置，移动k位总共只需要k+2次赋值，操作量比版本1少了近三分之二。

其他性能优势 #

版本2的内层比较逻辑直接用存在寄存器的临时变量和数组元素比较，不需要每次读取两次数组元素做对比，进一步降低了内存访问的开销。

要注意的是，Sedgewick的版本只是为了教学时更直观展示插入排序「逐个向前交换到正确位置」的核心逻辑，实际生产环境中用到的插入排序基本都是第二种移位优化的实现。在Java环境下对基本类型数组排序，即使JIT做了编译优化，版本2的性能通常也比版本1高出15%~35%，数组无序程度越高，性能差异越明显。

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