设有一个长度为N的数组a，下标为0...i...N-1，其中a[0~i]为数组的左半部分，a[i+1~N-1]为数组的右半部分，开始时i=0，要进行递增排序(a[0]<a[1]<....)：
1、此时数组的左半部分只有一个元素(a[0])，必为有序，将i+1
2、对数组的左半部分(a[0~1])排序，然后将i+1
3、对数组的左半部分(a[0~2])排序，此时a[0~1]部分已经有序，因此a[2]只要逐步与自己之前的元素比较，直到遇到比自己小的则停止。即：若a[2]
<a[1]则交换a[1]、a[2]的值，交换后再比较此时a[1]的值与a[0]的值，若a[1]<a[0]，则再交换二者的值；反之若a[2]>a[1]，则直接退出排序。
4、之后的步骤如此类推，当索引到达数组最右端时，数组排序就完成了。
从上的原理来看，插入排序就像逐步把一个个数据插入到一个有序的数组中，就像整理扑克牌一样。
1、java实现（Comparable接口）：
public class Insertion { private static boolean less(Comparable v, Comparable w) { //检测v是否小于w,为真返回负，为假返回正，相等返回零 return v.compareTo(w) < 0; } private static void exch(Comparable[] a, int i, int j) { //交换元素位置 Comparable t = a[i]; a[i] = a[j]; a[j] = t; } public static void sort(Comparable[] a) { //将a[]升序排列 int N = a.length; for (int i = 1; i < N; i++) for (int j = i; j > 0 && less(a[j], a[j-1]); j--) //a[j]比它的前一个元素小，则交换元素 exch(a, a[j], a[j-1]); } }
2、python实现：
1 def Insertion(a): 2 for i in range(1, len(a)): 3 key = a[i] 4 j = i - 1 5 while j >= 0 and key < a[j]: 6 a[j+1] = a[j] 7 j = j - 1 8 a[j+1] = key 9 10 #或 11 12 def InsertionSort(a): 13 for i in range(1, len(a)): 14 j = i 15 while j > 0 and a[j] < a[j-1]: 16 a[j],a[j-1] = a[j-1], a[j] 17 j = j - 1
1、对于随机排列的长度为N且主键不重复的数组，平均情况下插入排序需要~N2/4次比较以及~N2/4次交换。最坏情况下需要~N2/2次比较和~N2/2次交换，最好情况下需要N-1次比较和0次交换。
2、插入排序很适合小规模数组
原文：http://www.cnblogs.com/SlientGuest/p/4895513.html