算法排序篇——插入排序

发表于 | 分类于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function insertSort(arr){
    // 假设第一个数是已排序的，那么未排序就从第二个数开始，依次从未排序数组中取值，到已排序数组中比较
    for(let outer = 1; outer <= arr.length -1; outer++){
        // 将未排序的数遍历已排序的数组
        for(let inner = 0; inner <= outer -1; inner++){
            // 如果未排序的数比已排序的数小，这里有个技巧，直接从前往后遍历，就可以直接将要插入的值用splice插入
            if(arr[outer] < arr[inner]){
                // 插入到已排序的、比它大的数的前面
                arr.splice(inner, 0, arr[outer]);
                // 将其自身从未排序数组中删除，这里的outer + 1是因为，前面执行了添加，导致数组都整体往后移动一位，所以被插入的数组索引加一
                arr.splice(outer + 1, 1);
            }
        }
    }
}