一、插入排序的原理
将一个记录插入到一个已经排好序的有序表中，从而得到一个新的，记录数增1的新的有序表。从第一个元素开始，先将第一个元素看做一个排好序的子序列，然后从第二个元素开始起，对第二个元素进行插入，之后得到一个两个元素的有序表，然后再对第三个元素进行插入，得到一个三个元素的有序表...，依次类推，直到最后一个元素插入正确，整个序列有序为止。
二、插入排序的伪代码实现
INSERTION-SORT(A)
for j ← 2 to length[A]
do key ← A[j]
▹ Insert A[j] into the sorted sequence A[1 .. j - 1] to generate a new sorted sequence A[1 .. j]
i ← j - 1
while i > 0 and A[i] > key
do A[i + 1] ← A[i]
i ← i - 1
A[i + 1] ← key
三、插入排序的Java源码实现
import java.util.Comparator;
public class InsertSort {
/**
* 泛型方法实现插入排序算法，
* 泛型的类型不能是基础类型的，必须得是引用类型的
*/
public static <T> void insertSort(T[] t, Comparator<? super T> comparator){
T key = t[0];
for(int j = 1; j < t.length; j ++)
{
key = t[j];
//Insert the t[j] into the sorted sequence t[0, j-1], to generate a new sorted sequence t[0, j]
int i = j-1;
while(i > -1 && comparator.compare(t[i], key) > 0)
{
t[i+1] = t[i];
i--;
}
t[i+1] = key;
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Integer[] ints = {2, 0, 5, 23, 1, 4, 8, 56, 19};
insertSort(ints, new Comparator<Integer>(){
public int compare(Integer o1, Integer o2){
return o1.intValue() - o2.intValue();
}
});
for (int i = 0; i < ints.length; i++)
{
System.out.print(ints[i] + " ");
}
System.out.println();
}
}
运行结果：
0 1 2 4 5 8 19 23 56
四、复杂度分析
O(N^2)