概述

插入排序是一种简单直观的排序算法.

插入排序的工作原理就是, 对于未排序数据, 在一排序序列中从后向前扫描, 找到对应的位置并插入.

插入排序算法描述如下:

1. 从第一个元素开始, 该元素可以认为已经被排序
2. 取出下一个元素, 在已经排序的元素序列中从后向前扫描
3. 若序列中的元素大于取出的元素, 则向后移一位
4. 重复步骤3, 知道找到已排序的元素小于或等于取出元素的位置
5. 将取出的元素插入到该位置
6. 重复步骤2~5

很形象了

其时间空间复杂度如下:

插入排序也很好理解.

Java代码实现如下:

/**
 * 插入排序实现数组排序, 从小到大顺序
 * @param array
 */
public static void insertSort(int[] array) {
    /*
     * 1. 从数组第二个元素开始(第一个被认为已经排序)向后遍历
     * 2. 将已排序数组中所有大于当前元素的向后移动一位
     * 3. 将当前元素插入到已排序数组中
     * 4. 拿到下一个元素, 重复步骤2
     */
    // 对数组从第二个元素开始逐个查找
    for (int i = 1; i < array.length; i++) {
        // 保存当前元素
        int key = array[i];
        int j;
        // 将当前元素左面所有大于当前元素的值向右移一位
        for(j = i - 1; j >= 0 && array[j] > key; j--) {
            array[j + 1] = array[j];
        }
        // 插入当前元素
        array[j + 1] = key;
    }
}