插入排序 - javascript

插入排序的空间复杂度为O(1) ，则不需要额外的空间而是位移；
最佳的情况下T(n) = O(n)
最坏情况下T(n) = O(n2)

插入排序与扑克牌整理无异：
综图所述：
假设现在有数组let arr = [3,1,2,4];

1. 拿出一个元素，例如1,往前比；
2. 元素1与前面的元素进行比较，如果元素1小于前面的元素,元素1值=上一个对比元素；[3,3,2,4];达到了结束条件(对比元素index<0并且前一个对比元素小于当前元素)这时候值为[1,3,2,4];
3. 然后到元素2与前一个元素对比，达到交换条件[1,3,3,4],然后元素2与前一个元素index-1对比(前前个元素)达到结束条件(元素2大于对比元素)；停止，[1,2,3,4];
   如果用代码表示，则是：

在这里插入代码片
let arr = [3,5,1,4]
function InsertionSort(arr) {
        let len = arr.length;
        for (let i = 0; i < len; i++) {
            let item = arr[i];
            let preIndex = i - 1;
            while (preIndex >= 0 && arr[preIndex] > item) {
                arr[preIndex + 1] = arr[preIndex]
                preIndex--
            }
            // preIndex大于0并且前一个大于对比当前元素
            // while (preIndex > 0 && arr[preIndex] > item) {
            //     // 当前=前一个
            //     console.log(arr[preIndex],'---',item);
            //     arr[preIndex + 1] = arr[preIndex]
            //     preIndex--
            // }
            // // 如果当前没有前一个匹配的元素大,则赋值当前查找元素
            arr[preIndex + 1] = item;
        }

        return arr;
    }
    console.time()
    InsertionSort(arr)
    console.timeEnd()