数据结构--直接插入排序

直接插入排序

概念

插入排序的基本思想是：在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序地插入到已排好序的记录子集中，直到将所有待排记录全部插入为止。

插入类排序的整个过程就如同打扑克的理牌过程类似，拿到一张牌然后在已排好序的序列中找到一个合适的位置将这张牌插入。

在这里插入图片描述

function insSort(arr){
    if(!arr && !arr.length){
    return -1;}
    for(let i=2,len=arr.length; i<len; i++){
        const curNum = arr[i];
        let j = i - 1 ;
        while(curNum < arr[j]){
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = curNum;
    }
    return arr;
}

把当前数（curNum）之前的所有数字看做有序数组，从后往前逐个比较，找到合适位置后插入。

注：上述写法由于变量j可能取值-1，所以在其他语言中可以采用将数组的第一个位置设置为当前值的方式（哨兵）来避免数组越界问题。

算法要点

从后往前查找应插入的位置
查找与移动在同一循环中完成

算法分析

从空间角度看，仅需要一个curName变量来存储当前需要插入的数值。

从时间角度看，时间主要耗费在数值的比较和数组的移动上。

对于一趟插入排序，算法中的while循环的次数主要取决于待插记录与前i-1个记录的关键字的关系上。
最好情况为(顺序)： r [ i ] . k e y > r [ i − 1 ] . k e y r[i].key> r[i-1].key r[i].key>r[i−1].key，while 循环只执行 1 次，且不移动记录；最坏情况为(逆序): r [ i ] . k e y < r [ 1 ] . k e y r[i].key< r[1].key r[i].key<r[1].key，则while循环中关键字比较次数和移动记录的次数为i-1。

对整个排序过程而言，最好情况是待排序记录本身已按关键字有序排列，此时总的比较次数为 n − 1 n-1 n−1次，移动记录的次数也达到最小值(n-1)(每一次只对待插记录移动一次)；最坏情况是待排序记录按关键字逆序排列，此时总的比较次数达到最大值为 ( n + 2 ) ( n − 1 ) / 2 (n+2)(n-1)/2 (n+2)(n−1)/2，记录移动的次数也达到最大值 ( n + 4 ) ( n − 1 ) / 2 (n+4)(n-1)/2 (n+4)(n−1)/2。

执行的时间耗费主要取决于数据的分布情况。若待排序记录是随机的，即待排序记录可能出现的各种排列的概率相同，则可以取上述最小值和最大值的平均值，约为 n2/4。因此，直接插入排序的时间复杂度为 T ( n ) = O ( n 2 ) T(n)=O(n^2) T(n)=O(n2)，空间复杂度为 S ( n ) = O ( 1 ) S(n)=O(1) S(n)=O(1)。

排序算法的稳定性必须从算法本身加以证明。直接插入排序方法是稳定的排序方法。在直接插入排序算法中，由于待插入元素的比较是从后向前进行的，循环while( x . k e y < r [ j ] . k e y x.key< r[j].key x.key<r[j].key)的判断条件就保证了后面出现的关键字不可能插入到与前面相同的关键字之前。