基本思路

假设按照从小到大排列，总共有n个元素。

• 整个数组从逻辑上会被分成两个部分，左边部分是有序的序列，右边部分是待排序的元素。当然，刚开始左边的有序序列仅有一个元素，即第一个元素
• 将右边待排序元素的第一个元素，与左边有序序列进行比较。比较的时候，是从有序序列的末端（即有序序列最大的一个数）开始进行比较，如果比它大或者与之相等则直接插在其后面，否则一直往前面找，直到找到该插入的位置。插入的时候，需要把所插入位置右边的所有元素往右移。
• 重复上面的步骤，直到所有待排序的元素处理完毕

性能

平均需要n²/4次比较， n²/4次交换；最差情况n²次比较，n²次交换；最好情况n-1次比较，0次交换

时间复杂度：平均O(n²)，最坏O(n²)，最好O(n)

空间复杂度: O(1)

示例代码

更多详情可点击链接参考示例代码

private static int[] insertionSort(int[] unsortedArray) {
    int insertIndex;
    for (int splitter = 1; splitter < unsortedArray.length; splitter ++) {
        // Should have N - 1 rounds

        // Get the insert index
        insertIndex = splitter;
        for (int j = splitter -1; j >= 0; j --) {
            if (unsortedArray[j] > unsortedArray[splitter]) {
                insertIndex = j;
                continue;
            } else {
                break;
            }
        }

        // Move the item to right
        int temp = unsortedArray[splitter];
        for (int mov = splitter; mov > insertIndex; mov --) {
            unsortedArray[mov] = unsortedArray[mov - 1];
        }
        unsortedArray[insertIndex] = temp;
    }

    return unsortedArray;
}

用测试用例，有如下的输出。

Before sort: 3, 2, 9, 6, 0, 4, 8, 5, 7, 1
After round 1: 2, 3, 9, 6, 0, 4, 8, 5, 7, 1
After round 2: 2, 3, 9, 6, 0, 4, 8, 5, 7, 1
After round 3: 2, 3, 6, 9, 0, 4, 8, 5, 7, 1
After round 4: 0, 2, 3, 6, 9, 4, 8, 5, 7, 1
After round 5: 0, 2, 3, 4, 6, 9, 8, 5, 7, 1
After round 6: 0, 2, 3, 4, 6, 8, 9, 5, 7, 1
After round 7: 0, 2, 3, 4, 5, 6, 8, 9, 7, 1
After round 8: 0, 2, 3, 4, 5, 6, 7, 8, 9, 1
After round 9: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
After sort: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9