function insertSort(arr) {
// 循环遍历整个数组,从第二个元素开始(因为要把第一个元素看做已排序的子数组)
for (let i = 1; i < arr.length; i++) {
// 当前元素
let current = arr[i];
// 已排序子数组的最后一个元素的索引
let j = i-1;
// 在已排序子数组中,从后往前依次比较,找到合适的位置插入当前元素
while ((j > -1) && (current < arr[j])) {
// 如果当前元素比已排好序的元素小,则将该元素往后移动一个位置
arr[j+1] = arr[j];
j--;
}
// 插入当前元素到对应的位置
arr[j+1] = current;
}
return arr; // 返回排序后的数组
}
代码剖析
let j = i -1
原因:
let j = i-1是定义一个变量 j 并赋初值为 i-1。在插入排序算法中,我们需要将当前元素与已排序的子数组进行比较,并找到插入的位置。通常的做法是从当前元素的前一个位置开始扫描已排序的子数组,直到找到应该插入的位置。因此,我们将 j 初始化为当前元素的前一个位置,即 i-1,然后在 while 循环中逐步将 j 减小,扫描已排序的子数组,直到找到正确的位置。
例如,要将序列 [4, 1, 5, 3] 进行排序,先将第二个元素 1 作为当前元素进行比较。此时,已排序的子数组只有一个元素 4,因此将 j 的值初始化为 i-1,即 0,表示从第一个元素(也是最后一个元素,因为只有一个元素)比较起。随着 while 循环的进行,将 j 逐步减小,直到 j 的值为 -1 或找到了比 1 小的元素,然后将其交换位置,最终得到排序好的序列 [1, 4, 5, 3]。
重点:
- 为了找到插入排序要插入的位置
- 看列如的比喻