上次的选择排序，无论数组是如何排列的其算法的比较次数都是n(n-1)/2。
插入排序的方法是 从数组A[0]开始（先将数组中的首元素视为一个已经排序好的数组，因为是一个元素的数组，他自然是已经排序好的..）将A[1]插入到A[0]的前面或者后面，这取决于A[0]是否比A[1]大，接着继续这一过程 每次都是将A[i]插入到已经排序好的A[0....i-1]中合适的位置。
比较的过程为 依次扫描A[0....i-1]，每次都将A[i]于当前位置的元素比较，如果当前位置的元素比A[i]大，那么就将当前元素的位置移动到一个更高序号的位置，如果当A[i]大于当前位置的元素或者全部扫描完毕 比较过程结束，将A[i]插入到合适的位置。
:shock:看下代码吧...

[as]
/*
* 《算法设计技巧与分析》
* page 8-9
* 插入排序
*/
function insertionSort(ary:Array) :Array
{
var len:Number = ary.length;
for(var i=1; i {
var x:Number = ary[i];
var j:Number = i-1;
while(j>=0 && x {
ary[j+1] = ary[j];
j -= 1;
}
ary[j+1] = x
}

return ary;
}

//////////////////////main
//随机产生一个数组
var testAry:Array = new Array();
for(var i=1; i<=10; i++)
{
testAry.push( Math.round(Math.random()*100) );
}
trace("---before sort:\n" + testAry);
trace("\n---after sort:\n" + insertionSort(testAry));

/*
output:

---before sort:
72,79,95,28,70,0,66,6,15,86

---after sort:
0,6,15,28,66,70,72,79,86,95
*/
[/as]
与选择排序不同的是，插入排序的元素比较次数取决于原数组的顺序
观察结论: insertionSort 的元素比较次数在n-1到n(n-1)/2之间。
元素赋值次数等于元素比较次数加上n-1