思路

1. 把所有的元素视为两组：左边是已排序的a和右边未排序的b；
2. 找到b中的第一个元素k，k从右向左依次与a中的元素a[i]比较；
   2.1. 若k小，则k与a[i]交换位置，k继续向左与下一个元素比较；
   2.2. 否则k找到自己的位置，结束当前遍历；
3. 重复以上过程。

图示

绿色区间为已排序的，蓝色区间（包括黄色）为未排序的；每次遍历拿黄色元素与绿色区间比较。

代码

算法

    /**
     * 插入排序
     *
     * @param data
     */
    public static void insertOrder(int[] data) {
        for (int i = 1; i < data.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (data[j + 1] >= data[j]) {
                    break;
                } else {
                    exchange(data, j, j + 1);
                }
            }
        }
    }

    private static void exchange(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

测试

    public static void main(String[] args) {
        int[] data = {5, 3, 4, 1, 2};
        insertOrder(data);
        System.out.println(Arrays.toString(data));
    }

结果

[1, 2, 3, 4, 5]