算法回顾之二：直接插入排序

算法回顾系列第二篇：直接插入排序算法

-------------------------------------------

直接插入排序

基本原理：

把n个待排序的元素看成为一个有序表和一个无序表。

开始时有序表中只包含一个元素，无序表中包含有n-1个元素。排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。

程序实现：

public void sort(int[] data) {
	int temp;
	for(int i=1;i<data.length;i++){//已排序(有序表)的元素个数(第一个元素默认看作已排序).
		//有序表的下一个元素(j)如果小于已排序的最大元素(j-1),则交换位置.
		//如此向前(j--)与每个元素比较直到找到小于它的元素(data[j]<data[j-1])或者到第一个元素(j>0).
		for(int j=i; (j>0)&&(data[j]<data[j-1]); j--){//for的初始化条件j=i只执行1次.
			temp = data[j];
			data[j] = data[j-1];
			data[j-1] = temp;
		}
		System.out.println("Sort"+i+":"+Arrays.toString(data));//每趟排序后的结果.
	}
}

上面程序中：

外层循环i代表已经排序的元素个数(即有序表的元素个数)。从1开始计数，表明第一个元素默认是有序的。

内层循环j代表无序表的第一个元素，j-1即有序表的最后一个元素。两个元素比较：

如果无序表的第一个元素大于有序表的最后一个元素，则结束本趟排序(因为有序表的最后一个元素一定是最大的，无序表的第一个元素如果比它还大，不需要交换位置)。

如果无序表的第一个元素小于有序表的最后一个元素，则交换位置，然后继续与有序表的倒数第二个元素进行比较，直到找到有序表中比它小的元素或者它排在了第一个时，结束本趟排序。

如此直到排序完N-1个元素(第一个元素无需排序)。

性能分析：

1、待排序元素已从小到大排好序(正序)或接近排好序时,所用的比较次数和移动次数较少;

2、当待排序元素已从大到小排好序(逆序)或接近排逆序时,所用的比较次数和移动次数较多。

最坏时间复杂度：O(n^2)

空间复杂度：1。

稳定性：稳定的排序。