插入排序算法（Java版）

插入排序将数组分成已排序和未排序两个部分，每次都抽一个未排序的数出来，跟已排序的部分进行比较，找到合适的位置插入，然后那个数就变成了已排序的，之后继续抽一个未排序的数出来，再跟已排序的数一 一比较，一直循环到没有未排序的数为止。

插入排序的平均时间复杂度为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 + " ");
        }
    }
}

运行结果