排序之插入排序

????????插入排序每次排一个数组项，以此方式构建最后的排序数组。假定第一项已经排序了，接着，它和第二项进行比较，第二项是应该待在原位还是插到第一项之前呢？这样，头两项就已正确排序，接着和第三项比较（它是该插入到第一、第二还是第三的位置呢？），以此类推。
????????下面这段代码表示插入排序算法：

var insertionSort = function (array){
    var length = array.length,  //{1}
    j,temp     
    for(var i =1;i<length;i++){   //{2}
        j=i                       //{3}          
        temp = array[i]            //{4}
        while(j>0 && array[j-1]>temp){  //{5}
            array[j]=array[j-1]     //{6}
            j--
        }
        array[j]=temp       //{7}
    }
    return array
}

????????照例，算法的第一行用来声明代码中使用的变量（行{1}）。接着，迭代数组来给第i项找到
正确的位置（行{2}）。注意，算法是从第二个位置（索引1）而不是0位置开始的（我们认为第
一项已排序了）。然后，用i的值来初始化一个辅助变量（行{3}）并将其值亦存储于一临时变量
中（行{4}），便于之后将其插入到正确的位置上。下一步是要找到正确的位置来插入项目。只
要变量j比0大（因为数组的第一个索引是0——没有负值的索引）并且数组中前面的值比待比较
的值大（行{5}），我们就把这个值移到当前位置上（行{6}）并减小j。最终，该项目能插入到正确的位置上。
????????下面的示意图展示了一个插入排序的实例：

(1) 3已被排序，所以我们从数组第二个值5开始。3比5小，所以5待在原位（数组的第二位）。3和5排序完毕。
(2) 下一个待排序和插到正确位置上去的值是1（目前在数组的第三位）。5比1大，所以5被移至第三位去了。我们得分析1是否应该被插入到第二位——1比3大吗？不，所以3被移到第二位去了。接着，我们得证明1应该插入到数组的第一位上。因为0是第一个位置且没有负数位，所以1必须被插入到第一位。1、3、5三个数字已经排序。
(3) 4应该在当前位置（索引3）还是要移动到索引较低的位置上呢？4比5小，所以5移动到索引3位置上去。那么应该把4插到索引2的位置上去吗？4要比3大，所以4插入到数组的位置3上。
(4) 下一个待插入的数字是2（数组的位置4）。5比2大，所以5移动至索引4。4比2大，所以4也得移动（位置3）。3也比2大，所以3还得移动。1比2小，所以2插入到数组的第二位置上。至此，数组已排序完成。
????????排序小型数组时，此算法比选择排序和冒泡排序性能要好。