插入排序

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

        下面这段代码表示插入排序算法：

this.insertionSort = function(){

    var length = array.length,j, temp;  //{1}

    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}

    }

};

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

        下面的示意图展示了一个插入排序的实例：

        举个例子，假定待排序数组是 [3, 5, 1, 4, 2] 。这些值将被插入排序算法按照下面形容的步骤进行排序。

        (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插入到数组的第二位置上。至此，数组已排序完成。排序小型数组时，此算法比选择排序和冒泡排序性能要好。