上次的选择排序，无论数组是如何排列的其算法的比较次数都是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:看下代码吧...