最坏的情况下（比如输入序列是个逆序），每个元素都需要跟左边已经排好序的所有元素比较，总的比较次数为：1+2+...+(n-2)=(n-1)(n-2)/2 ~ O(n^2); 插入操作需要将插入位置右边的元素平移一个位置，总得移动操作次数也为O(n^2)。
插入排序是稳定的(stable),这与选择排序不同（选择排序用的是交换非相邻元素位置，所以不稳定），并且如果原序列基本上排好序的情况下，比较和移
动操作的次数可以大大降低，因为它只需比较一部分元素，在这种情况下，它与冒泡排序和选择排序不同在于：
冒泡排序需要依次比较元素直到最右端，即使左边的元素已经全部排好序也要依次比较；选择排序也需要查找右边最小的元素，即使有右边的元素已经排好序也要逐
个比较。插入排序的这个特性可以用被别的排序算法（比如quicksort）利用。
选择排序优于插入排序的地方可能就是前者的交换操作（即写操作）平均复杂度是O(n)，而后者是O(n^2)，所以在n很大时，想比较而言，选择排序写操作次数非常少。但是选择排序的缺点是不稳定(unstable)。
冒泡排序的写操作是O(n^2)，比较操作在任何情况下（除非左边已经排好序，提前退出）都是O(n^2)，效率极低。
总而言之，插入排序是三个复杂度为O(n^2)的排序算法（插入排序，选择排序和冒泡排序）中比较优的。
以下是该算法的一个实现。在代码中变量j之所以放在外面，是因为语句A[j+1] = tmp;不能放在语句break；之前位置，因为像输入序列为逆序时，比如(2,1)，整个内层循环执行完，而没有执行到break语句。
/**
*
* @author ljs
* 2011-05-31
*
* Insertion Sort: O(n^2)
*
*/
public class InsertionSort {
public static void solve(int[] A){
int n = A.length;
for(int i=1;i<n;i++){
int tmp = A[i];
int j = i-1;
for(;j>=0;j--){
//compare the i-th element with each of the sorted elements
if(tmp>A[j]){
break;
}else{
A[j+1] = A[j];
}
}
//stop at j-th element: insert i-th element
//between j-th and (j+1)-th element.
A[j+1] = tmp;
}
}
public static void main(String[] args) {
int[] A= {2,1};
InsertionSort.solve(A);
for(int i=0;i<A.length;i++){
System.out.format(" %d", A[i]);
}
System.out.format("%n");
A=new int[] {1,3,10,9,2,7,19,5,20,4,8,11};
InsertionSort.solve(A);
for(int i=0;i<A.length;i++){
System.out.format(" %d", A[i]);
}
}
}
测试：
1 2
1 2 3 4 5 7 8 9 10 11 19 20
转播
