原理
口语描述：第二个和第一个比，从小到大排。第三个和第二个比，再和第一个比，从小到大排。第四个和第三个、第二个、第一个比，从小到大排。。。。。
数组a[n]，lenght=n
从a[1] 开始到a[n-1]结束和之前的值进行比较，按从小到大的顺序排。
a[1]和a[0]比较，若a[1] < a[0]，交换a[1] 和 a[0]。
a[0]-a[1]已经排好序，让a[2]和a[1]比较，
①若a[2] < a[1]，则交换a[2] 和 a[1]，再比较a[1]和a[0]，若a[1]< a[0]则交换。
②若a[2]不小于a[1]则不动。
这时a[0],a[1],a[2]已经排好序。
接着轮到a[3]和前面的a[0],a[1],a[2]作比较，发现比自己大的就交换。一直轮到a[n-1]
代码
//插入排序
public class Sort03 {
public static void main(String[] args) {
int[] array = { 2, 15, 7, 9, 30, 1, 5 };
insertSort(array);
for (int i : array) {
System.out.print(i+" ");
}
}
/**
* 数组a[n], lenght=n
* 按照最坏的情况计算
* i∈[1,n-1]
* i=1时j∈[1],循环1次
* i=2时j∈[2,1],循环2次
* i=n-1时j∈[n-1,1],循环n-1次
*
* 所以，当数组长度为n时，内层循环执行的次数=swap()方法执行的次数，为(n²-n)/2
* 时间复杂度为O(n²)
*/
public static void insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
for (int j = i; j > 0; j--) {
if (array[j] < array[j - 1]) {
swap(array, j, j - 1);
} else {
break;
}
}
}
}
public static void swap(int[] array, int x, int y) {
int temp = array[x];
array[x] = array[y];
array[y] = temp;
}
}
输出结果
1 2 5 7 9 15 30
