插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。

/**	 * 直接插入排序算法	 */	public static void insertSort(int[] base){		int len = base.length;		for (int i = 1; i < len; i++) {			if(base[i] < base[i-1]){//判断当前值小于前一个值时，当前位置不变。体现了算法的稳定性				int temp = base[i];//哨兵				int position = i;				//满足条件时向后移动	            while(position >0 && temp < base[position-1]){  	            	base[position] = base[position-1];  	                position--;  	            }  	            //将当前值插在空当的位置	            base[position]=temp;  							}					}	}

算法分析

1．算法的时间性能分析 

    　对于具有n个记录的文件，要进行n-1趟排序。

    各种状态下的时间复杂度：

注意：

    　初始文件按关键字递增有序，简称"正序"。

　    初始文件按关键字递减有序，简称"反序"。 

2．算法的空间复杂度分析

    　算法所需的辅助空间是一个监视哨，辅助空间复杂度S(n)=O(1)。是一个就地排序。

3．直接插入排序的稳定性

    　直接插入排序是稳定的排序方法。

 

参考地址：http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.2.1.2.htm