排序算法---插入排序

1. 基本思想

从待排序列的第二个元素开始，与前面已排序的每个元素进行比较，若大（或小）则交换两元素，直到待排元素到达正确位置为止

下面以摸扑克牌为例，我们希望摸到的牌最终在手中是有序的，假设我们将小牌排在左边，大的牌排在右边

（1）第一次我摸到的数字是5， 此时手里只有一张牌，不存在先后顺序问题

（2）之后又摸到了一张3，此时与前面的5比较一下，发现3比5小，于是将3和5交换一下位置，手里的牌变成了 [3, 5]

（3）之后又摸了一张4，手里的牌是 [3, 5, 4], 先让4与前面的5比较，发现比5小，于是交换，变成[3, 4, 5], 再让4与3比较，发现不比3大，不需要交换

（4）继续摸牌，摸到的是4， 手中的牌变成了[3, 4, 5, 4], 先让4与前面的5进行比较，5大于4需要交换，变成了[3, 4, 4, 5], 4再与前面的4进行比较，发现不比前面的4大，于是不需要交换

（5）最后摸到一张6，手中的牌变成了[3, 4, 4, 5, 6], 6先于前面的5进行比较，发现比5大，不需要交换。

最终手里的牌是 [3, 4, 4, 5, 6]

?

2. 代码实现

    <script>
        let arr = [5, 3, 4, 4, 6];
        let len = arr.length;
        function InsertSort() {
            for (let i=0; i<len; i++) {  
                for (let j=i; j>0; j--) {  // 向前遍历 比较
                    if (arr[j] < arr[j-1]) {
                        let temp = arr[j];
                        arr[j] = arr[j-1];
                        arr[j-1] = temp;
                    }
                    else {
                        break;  // 当前元素不比前一个元素小，直接跳出内层循环
                    }
                }
            }
            console.log(arr)
            
        }
        InsertSort();
    </script>

?

?

3. 复杂度分析

1. 时间复杂度：找出执行次数最多的语句即可

if (arr[j] < arr[j-1]) {
       let temp = arr[j];
       arr[j] = arr[j-1];
       arr[j-1] = temp;
}

=> 对于第一个元素：需要比较0次

? ? ?对于第二个元素：需要比较1次

? ? ......

? ? 对于第n个元素：需要比较n-1次

=>所以 0+1+2+...+(n-1) = (n^2)/2 - n/2

=> 去掉系数、低阶和常量 ?

=> 则时间复杂度为 ?O(n^2)

?2. 空间复杂度: 插入排序中并没有用到额外的空间，所以空间复杂度为 O(1)

3. 插入排序是稳定的排序算法：从上述的摸扑克牌案例中可以看出，有两个4，然而后摸的4仍就排在先摸的4的后面

?