插入排序中while循环的作用是什么？为何未用交换操作？

先看你提供的完整代码：

const arr = [8, 20, -2, 4, -6];
insertionSort(arr);
console.log(arr); // [-6, -2, 4, 8, 20]

function insertionSort(arr) {
  // Two loops, outer to look at each element, and inner to shift elements

  // Outer loop
  for (let i = 1; i < arr.length; i++) // i starts at 1 because we don't need to sort the first element
  {
    let key = arr[i];
    let j = i - 1;

    // Inner loop
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
}

核心逻辑拆解 #

插入排序的本质是把数组分成「已排序区间」和「未排序区间」：

• 初始时，已排序区间只有第一个元素（arr[0]）
• 外层循环从i=1开始，每次取未排序区间的第一个元素（arr[i]）作为key，目标是把它插入到已排序区间的正确位置

while循环的具体动作 #

这个while循环没有用交换，而是通过**「后移元素腾出位置」**来实现插入，我们用你的数组一步步走一遍就清楚了：

第1次外层循环（i=1，key=20）

• j = 0，arr[j] = 8，8不大于20，while循环不执行
• 直接执行arr[j+1] = key，数组保持[8,20,-2,4,-6]，已排序区间变为[8,20]

第2次外层循环（i=2，key=-2）

• j = 1，arr[j] = 20 > -2，进入循环：
  • arr[2] = 20，数组变成[8,20,20,4,-6]
  • j减1变为0
• 此时arr[j] = 8 > -2，继续循环：
  • arr[1] = 8，数组变成[8,8,20,4,-6]
  • j减1变为-1，退出循环
• 执行arr[j+1] = key，也就是arr[0] = -2，数组变为[-2,8,20,4,-6]，已排序区间变为[-2,8,20]

第3次外层循环（i=3，key=4）

• j=2，arr[j]=20>4，进入循环：
  • arr[3]=20，数组变为[-2,8,20,20,-6]
  • j减1变为1
• arr[j]=8>4，继续循环：
  • arr[2]=8，数组变为[-2,8,8,20,-6]
  • j减1变为0
• arr[j]=-2不大于4，退出循环
• 执行arr[j+1]=key，也就是arr[1]=4，数组变为[-2,4,8,20,-6]，已排序区间变为[-2,4,8,20]

第4次外层循环（i=4，key=-6）

• j=3，arr[j]=20>-6，进入循环：
  • arr[4]=20，数组变为[-2,4,8,20,20]
  • j减1变为2
• arr[j]=8>-6，继续循环：
  • arr[3]=8，数组变为[-2,4,8,8,20]
  • j减1变为1
• arr[j]=4>-6，继续循环：
  • arr[2]=4，数组变为[-2,4,4,8,20]
  • j减1变为0
• arr[j]=-2>-6，继续循环：
  • arr[1]=-2，数组变为[-2,-2,4,8,20]
  • j减1变为-1，退出循环
• 执行arr[j+1]=key，也就是arr[0]=-6，得到最终排序数组[-6,-2,4,8,20]

为什么不用交换？ #

交换操作需要三次赋值（比如temp=a; a=b; b=temp），而这种「后移+插入」的方式，每次只需要一次赋值来移动元素，最后再用一次赋值插入key。当有多个比key大的元素时，这种方式的赋值次数更少，效率更高。本质上和交换的效果一致，但实现更高效。

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