插入排序

算法思想：

每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

算法实例：

package com.lanhuigu.algotithm.sort;

import java.util.Arrays;

/**
 * 插入排序算法
 * @author yihonglei
 * @date 2018/11/18 10:42
 */
public class InsertSortTest {

    public static void main(String[] args) {
        // 定义数组
        int[] arr = {3, 1, 4, 5, 2, 8};
        System.out.println("排序前数组：" + Arrays.toString(arr));

        // 调用插入排序算法
        insertSort(arr);

        System.out.println("排序后数组：" + Arrays.toString(arr));

    }

    /**
     * 插入排序算法
     * @author yihonglei
     * @date 2018/11/18 11:17
     * @param arr
     * @void
     */
    public static void insertSort(int[] arr) {
        // 遍历所有的数字，下标从第二个数字下标位置开始
        for (int i = 1; i < arr.length; i++) {
            // 把当前元素取出来
            int tmp = arr[i];
            // 如果当前数字小于前一个数字
            if (tmp < arr[i-1]) {
                int j;
                /*
                 遍历比当前元素小的前面所有数字，如果前面的数字比当前元素大，则需要往后移动。
                 */
                for (j = i - 1; j >= 0 && tmp < arr[j]; j--) {
                    // 大数字往后移动一个位置
                    arr[j+1] = arr[j];
                }
                /*
                当前一个元素比tmp小时，上面大数字移动的for循环结束，这个时候需要将tmp赋值给
                循环结束位置的后一个元素，即小数字的后一个元素。
                */
                arr[j+1] = tmp;
            }
        }
    }

}

运行结果：

算法分析：