插入排序算法分为直接插入、折半插入和希尔排序
1.直接插入排序
直接插入排序是一种最简单的排序方法，其基本操作是将一条记录插入到已排好序的有序表中，从而得到一个新的、记录数量增1的有序表。
算法步骤
（1）设待排序的记录存放在数组list[1....n]中，
（2）循环n-1次，每次使用顺序查找法，查找list [ i ] (i=2,...,n)在已排好序的序列list[ 1...i-1 ]中的插入位置，
然后将list[ i ]插入表长为i-1的有序序列r[ 1...i-1 ],直到将list[ n ]插入表长为n-1的有序序列list[ 1...n-1 ],最后得到一个表长为n的有序序列。
如图：8.2
代码如下
void insertSort(int list[]){ for(int i=1;i<list.length;i++){ int j=i; int temp=list[j]; if(list[j]<list[j-1]){ while(j>0&&(temp<list[j-1])){ list[j]=list[j-1]; j--; } list[j]=temp; } System.out.println(Arrays.toString(list)); } }
原文：http://www.cnblogs.com/fxbbk/p/7323958.html