定义

对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。

例如有个数组的长度为6，需要从小到大进行排序
第一遍：对比0~1位置的数，如果1位置的数比0位置小，则交换

第二遍：对比0~2位置的数，此时0~1位置的数已经是有序了，所以只需要先用2位置的数和1位置的对比，如果2位置的数不比1位置小，则结束这一遍对比，如果2位置的数比1位置小，则两者交换，然后再拿1位置的数和0位置的对比，如果1位置的数比0位置小，则交换。

第三遍：对比0~3位置的数，此时0~2位置的数已经是有序了，所以只需要先用3位置的数和2位置的对比，如果3位置的数不比2位置小，则结束这一遍对比，如果3位置的数比2位置小，则两者交换，然后再拿2位置的数和1位置的对比，如果2位置的数不比1位置小，则结束这一遍对比，如果2位置的数比1位置小，则两者交换，然后再拿1位置的数和0位置的对比，如果1位置的数比0位置小，则交换。

......

以此类推

代码示例

public class CodeInsertSort {

    /**
     * 从小到大排序
     * @param arr
     */
    public static void insertSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            // 考虑边界情况，数组为空或者长度小于2，则不用排序
            return;
        }
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--) {
                int temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }
        }
    }

    public static void printArr(int[] arr) {
        for (int j : arr) {
            System.out.print(j + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {5, 1, 6, 11, 10, 9, 45, 1, 6, 7, 9, 12};
        printArr(arr);
        insertSort(arr);
        printArr(arr);
    }

}

输出结果

5 1 6 11 10 9 45 1 6 7 9 12 
1 1 5 6 6 7 9 9 10 11 12 45