插入排序将数组分成已排序和未排序两个部分，每次都抽一个未排序的数出来，跟已排序的部分进行比较，找到合适的位置插入，然后那个数就变成了已排序的，之后继续抽一个未排序的数出来，再跟已排序的数一 一比较，一直循环到没有未排序的数为止。
插入排序的平均时间复杂度为O(n^2) ，最好时间复杂度为O(n)，最差时间复杂度为O(n^2)。
/**
* Created by lkmc2 on 2018/1/8.
*/
public class InsertSort {
public static void insertSort(int[] array) {
//因为第0个元素默认是已排序元素，抽取第一个未排序元素，其i下标从1开始
for (int i = 1; i < array.length; i++) {
//存储当前位置的值
int value = array[i];
int j;
//将第一个未排序元素分别与已排序元素进行对比（逆序），选择合适的位置插入
for (j = i; j > 0 && array[j - 1] > value; j--) {
//j位置的元素向后移动
array[j] = array[j - 1];
}
//将当前位置的值插入到j位置
array[j] = value;
}
}
public static void main(String[] args) {
int[] array = {7,4,3,9,2};
insertSort(array); //插入排序
for (int num : array) {
System.out.print(num + " ");
}
}
}
运行结果
