对随机长度为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()方法见“排序算法模板”
}
算法改进:
在所有主键都相同时,插入排序比选择排序更快;对于逆序数组,选择排序比插入排序更快。