排序----插入排序

上一篇：选择排序

对随机长度为N且主键不重复的数组，平均情况下插入排序需要~N^2/4次比较和~N^2/4次交换；最坏情况需要~N^2/2次比较和~N^2/2次交换；最好情况需要N-1次比较和0次交换。插入排序平均时间复杂度：O(N^2)。

插入排序的特点：

• 与选择排序一样，当前索引左边的所有元素都是有序的。但插入排序中它们的最终位置还未确定。
• 插入排序所需要的时间取决与输入中元素的初始顺序。
• 插入排序不会访问索引右侧的元素，而选择排序不会访问数组左侧的元素。

public class Insertion {
	public static void sort(Comparable[] 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--)
				exch(a,j,j-1);
	}
	//less()、exch()、isSorted()、main()方法见“排序算法模板”
}

算法改进：

• 插入排序的哨兵。在插入排序的实现中先找到最小元素将其置于数组的最左边，这样就能去掉内循环中的判断条件j > 0；注意，这是一种常见的规避边界测试的方法，能够省略判断条件的元素通常被称为哨兵。
• 不需要交换的插入排序。在插入排序中使较大元素右移一位而不是每次都交换。

在所有主键都相同时，插入排序比选择排序更快；对于逆序数组，选择排序比插入排序更快。

下一篇：希尔排序