插入排序多种实现

插入排序多种实现：arr,i=1,len=arr.length,flag=arr[i];第一趟，比较flag与arr[0]的大小，若flag > arr[0]，另arr[i++] = flag;否则， arr[0]右移（arr[i] = arr[0]）后另arr[0] = flag; i++进行下一趟排序。
第二趟，flag与前两个元素进行比较，在合适位置插入。
…
依次进行上述插入，直至排序完成。

这里一个需要注意的问题是，插入的时候，如果前i个元素都大于flag，直接在第一位插入。也就说需要在j = 0 处加一个岗哨。

这里不难分析，两层循环的时间复杂度为n^2，（平均为n^2/4），但我们用到的交换空间为O（1）。

贴代码：

  function insertFlag(arr, pos, flag) {
        for (var j = pos; j > 0; j--) {
            if(flag < arr[j-1]){
              arr[j] = arr[j-1];
            }else{
              arr[j] = flag;
              break;
            }
        }
        //岗哨
        if(j == 0){
          arr[0] = flag;
        }
    }

    function insertSort(arr) {
        var flag,
            len = arr.length;
        for (var i = 1; i < len; i++) {
            flag = arr[i];
            console.log(flag);
            insertFlag(arr, i, flag);
        }
    }

我们这里把插入函数独立出来，是为了之后更好的对插入方法进行改进。
上述的方法在待排序的数组比较小的时候，效率比较高，但大的时候就有点力不从心。
我们这里的插入，其实是在寻找一个arr[j] <= flag <=arr[j+1]的位置，并进行插入。那么如何进行改进呢，当然就是“折半查找”咯！（虽然时间和空间没有质的改变，但也是一种改进嘛）

 function binary(arr, pos, flag) {
        var mid, low = 0,
            hign = pos - 1;
        while (low <= hign) {
            mid = Math.ceil((low + hign) / 2);
            arr[mid] < flag ? low = mid + 1 : hign = mid - 1;
        }
        return hign + 1;
    }

    function binaryInsert(arr) {
        var flag,index,
            len = arr.length;
        if (arr[1] < arr[0]) {
            flag = arr[1];
            arr[1] = arr[0];
            arr[0] = flag;
        }
        for (var i = 2; i < len; i++) {
            flag = arr[i];
            console.log(flag);
            index = binary(arr, i, flag);
            for(var j = i; j > index; j--){
              arr[j] = arr[j-1];
            }
            arr[index] = flag;
        }
    }

这里我们为了折半查找的方便，先对arr的前两个元素进行排序，然后再进行折半查找并插入。不然看出，我们减少了关键字的比较，但是移动的次数并没有改变，所以时间复杂度依然为n^2.空间O（1）。

2-路插入排序主要是为了减少移动的次数。而要想真正达到减少移动次数，最方便的是使用表插入排序，与直接插入排序的差别在于改变了2n次指针值代替移动记录，比较次数并没有发生变化。时间复杂度依旧是n^2。

希尔排序也是插入排序的一种。因为我们知道在数组基本有序，而且数组长度较小的时候，直接插入排序的效率很高（n），希尔排序正是利用了这一点，先将整个待排记录序列分割成若干个子序列，分别进行直接插入排序，待整个记录基本有序时，再对整体序列进行一个直接插入排序。

希尔排序的特点是，分段不是简单的逐段分割，而是将相隔一定增量的的记录组成一个子序列。简单理解的话，就当是先按增量数组进行两两交换，最后用一次直接插入排序。