本文说明了如何实现和使用插入排序算法。最简单但同时是功能强大的之一。代码示例将在Java中，但可以轻松地转换为任何其他编程语言。如果您想摘要，只需滚动到摘要部分。

在主题期间，我们将对以下数组进行排序。所有示例都与此数组有关。

插入排序

算法本身非常简单。这是实现的伪代码。

function InsertionSort(input)
    for i = 1 to length(input) - 1 do //2
        element = input[i]
        j = i - 1
        while j > 0 and input[j] > element do
            input[j + 1] = input[j]
            j = j - 1
        input[j + 1] = element

    return input

主要思想是在左侧有一个排序的子阵列，然后将下一个元素从右侧的未分组的其余部分插入到排序的部分中的适当位置。

排序以1 ^st 索引元素开头，而不是以0 ^th 索引，因为单元素阵列始终被整理。未分类部分的每个元素都会向左移动以找到其位置，即插入正确的位置。当索引i-1较小或等于元素被移动/插入的元素时，该位置是正确的。

从1 ^th 索引元素（5。
）
该元素不小于以前的元素，因此无需移动它。它就位。现在，1和5已分类。

下一个元素是带有索引2的3。

它比索引1的前一个小，有必要通过一个单元将5向右移动。现在，将3与索引0进行比较。它不小于1，因此将3放在索引1的单元格上。将采用相同的方法。用索引3取以下元素1。

这次1小于两个元素，必须移动两个元素。由于比较操作严格较小，因此该算法不会从Cell 0移动1，这不是必需的。最后一个元素是4

仅需要一个元素向右移动以在必要位置加速4。就是这样，数组已被排序。

Java实现非常简单。

    int[] insertionSort(int[] input) {
        for (var i = 1; i < input.length; i++) {
            var element = input[i];
            var j = i - 1;
            for (; j > 0 && input[j] > element; j--) {
                input[j + 1] = input[j];
            }
            input[j + 1] = element;
        }
        return input;
    }

以索引1开头的主循环和一个向后遍历尽可能多的元素的子环向放置当前的元素。

Wiki的整个过程的动画。

复杂性和特征

从空间复杂性角度来看，算法使用恒定空间，因为始终有三个变量，两个用于索引，一个元素可以插入：O(1)。

由于嵌套环的时间复杂性，时间复杂性更加糟糕，导致O(N*N)的二次时间。确实，在更糟糕的情况下，当数组被排序以将其上升为上升时，每个元素都必须转移到镜像位置，即第一个元素将成为最后一个，最后一个将成为第一个。需要每个元素的~ N移动，因此~ N * N移动。

该算法是稳定，因为在排序过程中保持相对顺序，即，如果有两个相同的元素A和B它们的顺序在排序之后将相同。