插入排序适合于部分有序序列和小规模的数据。其平均时间复杂度为 O(N^2)，空间复杂度为 O(1)，并且为稳定排序。

插入排序将待排序序列分为有序区 (记为 S 区)和无序区(记为 R 区)。以从小到大的顺序为例，每次从 R 区弹出一个元素 O，要将元素 O 插入到 S 区中恰当位置。从 S 区最右端开始，依次比较 S 区元素与元素 O 的大小。如果元素O 比 S 区元素小，就将 S 区元素后移一位。如果元素 O 大于 S 区元素，就在该元素右边一位插入元素 O。

public static void insertionSort(int[] x) {
        int N = x.length;
        for (int i = 1; i < N; ++i) {
            int value = x[i];
            int j = i - 1;
            for (; j >= 0; --j) {
                if (x[j] > value) {
                    x[j + 1] = x[j];
                } else {
                    break;
                }
            }
            x[j + 1] = value;
        }
    }

演示：

    public static void main(String[] args) {

        int[] b = {3, 12, 17, 2, 19, 34, 91};
        insertionSort(b);
        for (int value: b)
            System.out.printf("%d ", value);
    }

输出：2 3 12 17 19 34 91