概述
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序（即只需用到O(1)的额外空间），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
换句话说，就是：
假设在序号 i 之前的元素即 [0... i-1] 都已经排好序，本趟需要找到 i 对应的元素 x 的正确位置 k ，在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位，为元素 x “腾位置”，最后将 k 位置对应的元素值赋为 x ，插入排序的时间复杂度和空间复杂度分别为 O(n2) 和 O(1)。
步骤
从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置中
重复步骤2，直到排好序为止
实例
举个简单的例子，帮助理解。
原始数据：
3 5 2 6 2
第一轮，把 3 作为已经排好序的，取出 5 与 3 进行比较，5 大于 3 位置保持不变，新的有序组为 [3 5]
3 5 2 6 2
第二轮，取出第一个 2 ，从已排序的 [3 5] 数组从后往前比较，与 5 比较，小于 5，将 5 向后移动一个位置，再与 3 比较，小于 3，将 3 向后移动一个位置，前面没有了，将 2 放置在原来 3 的位置，新的有序组为 [2 3 5]
2 3 5 6 2
第三轮，取出 6 ，与 5 比较，5 保持不动，新的有序组 [2 3 5 6]
2 3 5 6 2
第四轮，取出 2 ，与 6 比较，6 向后移动一位，与 5 比较，5 向后移动一位，与 3 比较，3 向后移动一位，与 2 比较，不需移动，将取出的 2 放到原来 3 的位置即可，至此完成排序。
2 2 3 5 6
两个相同的 2 保持他们原来的前后顺序，所以直接插入排序是稳定的。
代码实现(Java)
package com.coder4j.main.arithmetic.sorting; public class StraightInsertion { /** * 直接插入排序 * * @param array * @return */ public static int[] sort(int[] array) { // 将第一个i=0作为已排序组 for (int i = 1; i < array.length; i++) { System.out.println("第" + i + "轮比较结果："); // 取出i索引待排序元素 int temp = array[i]; int j; // 从已排序数组后面往前逐个比较，确定i元素的位置，并将相应的元素后移一位 for (j = i - 1; j >= 0 && temp < array[j]; j--) { array[j + 1] = array[j]; } // 找到了位置 array[j + 1] = temp; // 输出此轮排序结果 for (int k : array) { System.out.print(k + " "); } System.out.println(); } return array; } public static void main(String[] args) { int[] array = { 3, 5, 2, 6, 2 }; int[] sorted = sort(array); System.out.println("最终结果"); for (int i : sorted) { System.out.print(i + " "); } }} 测试输出结果：
第1轮比较结果：3 5 2 6 2 第2轮比较结果：2 3 5 6 2 第3轮比较结果：2 3 5 6 2 第4轮比较结果：2 2 3 5 6 最终结果2 2 3 5 6
经测试，与实例中结果一致。