插入排序示范-从小到大 关键操作“从左至右后数插入前面数组”

插入排序分析：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