排序算法之插入排序

[xuexueq]

插入排序（稳定）

插入排序的设计初衷是往有序的数组中快速插入一个新的元素。

插入排序由于操作不尽相同, 可分为 直接插入排序 , 折半插入排序(又称二分插入排序)。

主要思路：它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法分析:

最佳情况：输入数组按升序排列。T(n) = O(n)
最坏情况：输入数组按降序排列。T(n) = O(n2)
平均情况：T(n) = O(n2)

1. 直接插入排序

在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空。在每次比较操作发现待插入元素小于等于已排序的元素时，将已排序的元素移到下一位置，随后将待插入元素插入该位置，接着再与前面的已排序的元素进行比较。

function directInsertSort(arr) {
    function swap(arr, i, j) {
        let temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    for(let i = 1, len = arr.length; i < len; i++) {
        for(let j = i; j > 0; j--) {
            if(arr[j - 1] > arr[j]) {
                swap(arr, j - 1, j);
            } else {
                break;
            }
        }
    }
    return arr;
}

上面的做法交换操作代价比较大。还有一个做法是，将新元素取出，从后向前扫描，如果已排序的元素大于新元素，那么将该元素移动到下一个位置，接着再与前面的已排序的元素比较，直到找到已排序的元素小于等于新元素的位置，这时再将新元素插入进去。

function directInsertSort2(arr) {
    for(let i = 1,len = arr.length; i < len; i++) {
        let current = arr[i]; // 将待插入元素取出
        let index = i - 1;
        while(index >= 0 && arr[index] > current) {
            arr[index + 1] = arr[index];
            index--;
        }
        if(index + 1 != i) { // 避免同一个元素赋值给自身
            arr[index + 1] = current;
        }
    }
    return arr;
}

另一种写法：

function directInsertSort3(arr) {
    for(let i = 1,len = arr.length; i < len; i++) {
        let current = arr[i]; // 将待插入元素取出
        for(let j = i; j >= 0; j--) {
            if(arr[j - 1] > current) {
                arr[j] = arr[j - 1];
            } else {
                if(j != i) {
                    arr[j] = current;
                }
                break; // break
            }
        }
    }
    return arr;
}

2. 折半插入排序（二分插入排序/二分查找排序）

基本思路：折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。

步骤：

将一新的元素插入到有序数组中，寻找插入点时，将待插区域的首元素设置为a[low],末元素设置为a[high],比较时则将待插元素与参考元素a[m]（m=(low+high)/2）相比较；
如果待插元素比参考元素小，则选择a[low]到a[m-1]为新的插入区域（即high=m-1）,否则选择a[m+1]到a[high]为插入区域：
如此直到low<=high不成立，即将此位置(low)之后所有元素后移一位，并将新元素插入a[low]中。

function binaryInsertSort(arr) {
    let low;
    let high;
    let middle;
    let current;
    for(let i = 1, len = arr.length; i < len; i++) {
        low = 0;
        high = i - 1;
        current = arr[i];
        while(low <= high) { // 当两两相同时，切换到高半区，保证稳定性（移动的次数少）
            middle = Math.floor((low + high) / 2);
            if(current >= arr[middle]) { // arr[middle]
                low = middle + 1;
            } else {
                high = middle - 1;
            }
        }
        for(let j = i; j > low; j--) {
            arr[j] = arr[j - 1];
        }
        // 将插入点到待插入元素之间的所有元素依次往后移一位，此时low也即high+1，使用arr[high+1]也行
        if(low != i) {
            arr[low] = current;
        }
    }
    return arr;
}