对于一个有n个元素的待排序列,将这个序列分成有序表和无序表,刚开始时,有序表只有一个元素,无序表有n-1个元素,排序过程就是将无序表的第一个元素插入到有序表的合适位置,依次循环n-1次。
public static void insertsort(int[] arr) {
int i, j, k;
for(i=1;i<arr.length;i++) {
for(j=i-1;j>=0;j--) {
if(arr[j]<arr[i])
break;
}
if(j!=i-1) {
int temp = arr[i];
for(k = i-1;k>j;k--) {
arr[k+1] = arr[k];
}
arr[j+1]=temp;
}
}
}
public static void main(String[] args) {
int[] arr = {62,23,51,46,85,42,15};
insertsort(arr);
System.out.println(Arrays.toString(arr));
}
最好情况:待排序列已按关键字有序,只需1次比较,0次移动。
总比较次数:n-1次
总移动次数:0次
最坏情况:待排序列按关键字逆序,即每趟都需要叫关键字插入到有序序列的第一位
总比较次数:(n+2)(n+1)/2
总移动次数:(n+4)(n-1)/2
平均情况:O(n2)
网友评论