插入排序算法假设数组是部分有序的，它从未排序的数组部分的最左边开始， 将这个元素值存到一个临时变量中，然后用这个变量的值和该元素左边(即假设已经有序的部分)的每一个元素相比较，如果临时变量的值比该元素小，则该元素要右移，直到发现有一个元素比临时变量的值要小，则将该值复制到这个元素后面的位置上。
算法从索引为1的元素开始，它假设左边的这一个元素是有序的，则在第一趟中，它需要比较1 次，每二次比较 2次， 类推下云， 比较了 1+2+3+...+ (N-1) = N*(N-1) / 2 次。而实际上由于它总是只和左边已经有序的部分进行比较，所以基本上比较次数可再除以 2， 为 N*(N-1) / 4 次。
而复制次数则差不多一样， 可见它的时间复杂度仍为 O(N^2)。
在基本有序的数组中，插入排序的效率很高，因为很多情况下元素都比它前面的要大，时间可以接近 O(N)。 而且移动和交换相比花费的时间也少得多，所以即使在最坏的情况下，它也比冒泡排序要快一些。实际在通常的情况下， 它比冒泡排序可能快上一倍。
代码片断
/*
start from the second elem, copy the left most elem
of the unsorted part to a temp variable, then compare
it with all the elem within the sorted part of array, move
all the elem larger than the temp variable right, then
insert the value in the vacant position.
n-1 times of iterations required
*/
public void sort () {
for (int i = 1; i<size; i++) { //从第二个开始共N-1次，假设第一个有序
int tmp = array[i]; //将这个数复制到一个临时变量中
int j = i; //从当前这个元素开始
while (j>0 && array[j-1]>=tmp) { //看前面一个是否比自己大
array[j] = array[j-1]; //只要前面一个比自己大，就让它右移
j--;
}
if ( j != i ) { //如果还在这个位置上，就不必要复制了
array[j] = tmp; //复制到正确的位置
}
}
}