JS实现直接插入排序

2016年10月23日Web前端0

插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。

JS的实现代码：

function insertionSort(arr) {
    var len = arr.length,
        preIndex, cur;
    for (var i = 1; i < len; ++i) {
        preIndex = i - 1;
        cur = arr[i];
        while (preIndex >= 0 && arr[preIndex] > cur) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = cur;
    }
    return arr;
}

比如，现在我们传入一个[2, 5, 8, 4, 1]的数组，

外层第一次循环，i为1，内层循环不满足条件，退出第一次循环，

外层第二次循环，i为2，内层循环不满足条件，退出第二次循环，

外层第三次循环，i为3，因为8 > 4，所以移动8，数组变成[2, 5, 8, 8, 1]，因为5 > 4，移动，数组变为[2, 5, 5, 8, 1]，因为2 < 4，所以数组变为[2, 4, 5 ,8, 1]，退出第三次循环，

外层第四次循环，i为4，因为8 > 1，所以移动8，数组变为[2, 4, 5, 8, 8]，又5 > 1，数组变为[2, 4, 5, 5, 8]，因为4 < 1，所以数组变为[2, 4, 4, 5, 8]，有因为2  > 1，所以数组变为[2, 2, 4, 5, 8]，退出循环，此时preIndex的值是-1，最后给arr[0]赋值，得到[1, 2, 4, 5, 8]。

JavaScript算法

目录