插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法步骤：

1）将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

2）从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

算法图示：

算法基本性能

排序方法	平均时间复杂度情况	最好情况	最坏情况	空间复杂度	稳定性
插入排序	O(n2)	O(n)	O(n2)	O(1)	稳定

Java代码

package com.sort;import java.util.Random;public class Main {    // 从小到大    private static void sort(int[] array) {        if (array.length <= 1) {            return;        }        for (int i = 1; i < array.length; i++) {            /**             * 因为0~i-1为有序的，如果i位置的大于i-1位置的，说明0~i也是有序的，             * 反之需要在0~i-1直接找出i位置的元素的正确位置插入             */            if (array[i] < array[i - 1]) {                /**                 * 先保存i位置元素                 */                int temp = array[i];                int j = i - 1;                /**                 * 从i-1开始向前查找，一直到找到比i位置元素小的位置，然后插入                 */                for (; j >= 0 && array[j] > temp; j--) {                    /**                     * 没有找到，那么将此位置的元素后移一位，腾出位置                     */                    array[j + 1] = array[j];                }                /**                 * 将i位置元素放在腾出的位置上面                 */                array[j + 1] = temp;            }        }    }    /**     * 获取指定长度的随机数组     */    public static int[] getRandomArray(int n) {        int[] array = new int[n];        Random random = new Random();        for (int i = 0; i < array.length; i++) {            array[i] = random.nextInt(500);        }        return array;    }    /**     * 打印指定数组     */    public static void outputArray(int[] array) {        for (int i : array) {            System.out.print(i + " ");        }        System.out.println("");    }    public static void main(String[] args) {        int[] array = getRandomArray(10);        outputArray(array);        sort(array);        outputArray(array);    }}