插入排序分析：1.后数插入前面的数组中，前面的数组是已经排好序的 2.后数下标为i，前数组最后一个数下标为i-1，用j记录i-1；
假设数组array有array.length个元素
说明：int i,j,temp=0; 其中i用来记录每趟插入数的下标，从1开始到array.length-1结束，共计array.length-1趟，j记录i下标所有前面元素组成数组中的元素下标，i下标从1开始到array.length-1变化，j下标从i-1到可能是负数的情况变化。
假设问题规模为n，即需要排序的数组元素为n个。
第1趟：i下标此时为1，前面数组元素个数为1个，最坏情况需要比较1次，while循环体中移动操作1次，加循环体结束再移动一次，共计移动2次，最好情况while循环体移动操作条件判定一次，不移动
....
第i趟：i下标此时为i，前面数组元素个数为i个，最坏情况需要比较i次，while循环体中移动操作i次，加循环体结束再移动一次， 共计移动i+1次，最好情况while循环体移动操作条件判定1次，不移动
....
第n-1趟（最后一趟）：i下标此时为array.length-1，前面数组元素个数为n-1个，最坏情况需要比较n-1次，while循环体中移动操作n-1次，加循环体结束再移动一次， 共计移动n次，最好情况while循环体移动操作条件判定一次，不移动
总计：时间复杂度 while循环体中移动操作最坏情况:1+2+...+n-1=(n-1)(1+n-1)/2, O(n^2);最好情况只有while循环体移动操作条件判定 一次，while循环体中移动操作不执行：1*(n-1)=n-1,O(n)。只需要一个额外空间O(1)。
我个人代码实现：
public class InsertSort {
public static void insertSort(int[] array) {
int i,j,temp=0;
for(i=1;i<array.length;i++) {
temp=array[i];
j=i-1;
while(j>=0&&array[j]>temp) {
array[j+1]=array[j];
j--;
}
array[j+1]=temp;
}
}
public static void main(String[] args) {
int[] array= {6,5,3,2,4,8,9,1};// TODO Auto-generated method stub
System.out.println("排序前：");
for(int i=0;i<array.length;i++)
System.out.print(array[i]+" ");
System.out.println();
insertSort(array);
System.out.println("排序后:");
for(int i=0;i<array.length;i++)
System.out.print(array[i]+" ");
}
}
输出结果：
排序前：
6 5 3 2 4 8 9 1
排序后:
1 2 3 4 5 6 8 9
网友评论