对于数组:

var arr = [3, 2, 5, 1, 9, 4];

把此数组分为两个部分,左边部分 [3] 和右边部分[2, 5, 1, 9, 4]。只是思维上把 arr 数组分为两部分,arr 还是一个整体,也并不会多创建两个临时数组。

这时,左边部分是排序好的数组(因为只有一个元素),右边部分是没有排序好的数组。

插入排序就是每次排序时,从右边部分取一个元素,插入到左边部分,因为左边已经是有序的了,所以把从右边取出的元素依次和左边的元素对比,就能找到新元素应该存放的位置。以此循环,就能排序好整个数组 arr 了。

下面来分析一个具体排序过程:

var arr = [3, 2, 5, 1, 9, 4];

第一次排序

取出右边部分的第一个元素是 arr[1] = 2。

var j = 1;        // 右边部分第一个元素的脚标
var i = j - 1;    // 左边部分(从右向左方向)第一个元素的脚标
var key = arr[j]; // 从右边部分取出的第一个元素

把取出的元素 key,依次和左边排序好的元素进行比较,如果左边元素比 key 大,就把此元素(左边拿出来与 key 对比的元素)向右移动一位。

为什么要向右移动一位呢?

因为右边部分的第一个元素被取出来了,整个数组 arr 中有一个空位(arr[j] 所在位置),arr[j](即 key) 在和左边部分对比时,比 arr[j] 大的元素就要向右靠,占据 arr[j] 被取出后的位置,这样左边部分就会有一个空位,最终这个空位用来放最开始 arr[j] 的值,也就是 key。

这里 key = 2, arr[i] = 3

if (arr[i] > key) {
    arr[i+1] = arr[i];
    i = i - 1; // i 自动减 1 , 以便比较下一个元素
}

所以,移动之后是这样的[3, 3, 5, 1, 9, 4]

元素 2 在哪儿去了?

在 key 里面缓存着呢。

然后再在左边部分取下一个元素来比较,即 arr[i], i = -1,这里会取到 arr[-1] = undefined,undefined 会被转化为 NaN,所以 arr[i-1] > key 返回 false。

此时,对于 key 来说,在左边排序好的部分中,在 arr[i+1], i = -1 这个位置左边的元素比 key 小,而右边的元素比 key 大(或者和 key 相等),所以 arr[i+1]这就是 key 应该插入的位置。

// i = -1
arr[i+1] = key

此时,得到第一次排序后的数组:[2, 3, 5, 1, 9, 4]。

第二次排序

// 此时 arr = [2, 3, 5, 1, 9, 4]
// 左边部分是 [2, 3]
// 右边部分是 [5, 1, 9, 4]
// 所以
var j = 2;
var i = j - 1; // i = 1
var key = arr[j];

// 第一次比较
// arr[i] = 3, key = 5
// 此时发现,左边部分最大的元素也比 key 小
// 所以,key 此时的位置已经是排序好的了
// 则不作改变,进入下一轮排序
if (arr[i] > key) {
    arr[i+1] = arr[i];
    i = i - 1;
}

第三次排序

// 此时 arr = [2, 3, 5, 1, 9, 4]
// 左边部分是 [2, 3, 5]
// 右边部分是 [1, 9, 4]
// 所以
var j = 3;
var i = j - 1; // i = 2
var key = arr[j];

第一次比较

// i = 2, arr[i] = 5, key = 1
// 此时 arr[i] 大于 key
// 所以把 arr[i] 向后移动一位
if (arr[i] > key) {
    arr[i+1] = arr[i];
    i = i - 1;
}

// 移动后
// i = 1, arr[i] = arr[1] = 3

第二次比较

// 此时 i = 1, arr[i] = 3, key = 1
// 所以把 arr[i] 再次向后移动一位
if (arr[i] > key) {
    arr[i+1] = arr[i];
    i = i -1;
}

// 移动后
// i = 0, arr[i] = arr[0] = 2

第三次比较

// 此时 i = 0, arr[i] = 2, key = 1
// 所以把 arr[i] 再次向后移动一位
if (arr[i] > key) {
    arr[i+1] = arr[i];
    i = i - 1;
}

// 移动后
// i = -1, arr[i] = arr[-1] = undefined

第四次比较

// 此时 i = -1, arr[i] = undefined, key = 1
// arr[i] < key 返回 false
// 说明 arr[i] 比 key 小(或相等)
// 所以 i+1 就是 key 应该存放的位置
// 即 arr[i+1] = arr[0] = 1
if (arr[i] > key) {
    arr[i+1] = arr[i];
    i = i -1;
}

第三次排序结束后,数组是这样的:[1, 2, 3, 5, 9, 4]。

后面的排序和前面的分析一样,就不在赘述。

排序的代码非常简单,如下所示:

function insertionSort(arr) {
    var arr = arr.slice(0); // 排序后原数组不变
    var i, j, key, len = arr.length;

    // 循环依次从右边部分取元素
    // 每一次循环就是一趟排序
    for (j = 1; j < len; j++) {
        key = arr[j];
        i = j - 1;

        // 把每次的 key 和左边部分的元素依次比较
        while (arr[i] > key) {
            arr[i + 1] = arr[i];
            i = i - 1;
        }

        // 当 arr[i] <= key 时
        // i + 1 就是 key 应该存放的位置了
        arr[i + 1] = key;
    }

    return arr;
}