内排序1：插入排序

插入排序有几种，这里讨论的是简单插入排序法，也称为直接插入排序法。

基本思想：第i趟排序是将第i+1个元素ki+1(i=1,2,...,n-1)插入到一个已经按值有序的子序列（k1,k2,...,k`i）的合适位置，得到一个长度为i+1且仍然按值有序的子序列（k1,k2,...,ki,ki+1）。插入方法的核心动作是插入，而寻找被插入元素的合适位置是主要工作。
算法如下:

function insertSort(arr) {
    let n = arr.length
    let i, j, temp
    for ( i=1; i<n; i++) {
        temp = arr[i]
        j = i-1
        while ( j>=0 && temp<arr[j] ) {
            arr[j+1] = arr[j--]
        }
        arr[j+1] = temp
    }
    return arr
}

let arr = [5,3,8,1,9,2,7,4,6,10]
insertSort(arr)

性能：
时间复杂度：最坏时O(n2)，最好时O(n)。是稳定性排序方法。

基本思想：由于每一趟被插入的子序列为一个按值有序的序列，因而可以采用 折半查找方法 来确定被插入元素在该有序排序中的合适位置。
算法如下：

function bin_insertSort(arr) {
    let n = arr.length
    let low, high, mid, i, j, temp
    for( i=1; i<n; i++ ) {
        temp = arr[i]
        low = 0
        high = i-1
        while ( low<=high ) {
            mid = Math.floor((low+high)/2)
            if ( temp<arr[mid] ) {
                high = mid-1
            } else {
                low = mid+1
            }
        }
        for( j=i-1; j>=low; j-- ) {
            arr[j+1] = arr[j]
        }
        arr[low] = temp
    }
    return arr
}

let arr = [5,3,8,1,9,2,7,4,6,10]
bin_insertSort(arr) 

性能：
时间复杂度：最坏时O(n2)，最耗时O(nlog2n)。