> For the complete documentation index, see [llms.txt](https://suki.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://suki.gitbook.io/notes/articles/sorting/insertion_sort.md).

# 排序 - 插入排序

## 概念

假设我们手上有一副扑克牌，现在要把所有牌按顺序摆放在桌面上，我们可以抽出第一张牌，先放到桌上，然后抽出第二张牌，如果第二张牌比桌面上的牌大，就放到它右边，反之就放到左边。

插入排序也是相似的思路，把数组分成“已排序”和“未排序”两个部分，不断地从“未排序”中取出数字，插入“已排序”部分。

## 算法

* 假设数组的第一个数字是“已排序”部分。
* 从第二个数字开始，首先用一个变量记录这个数字 key：
  * 将 key 与其左边的数字进行比较，
  * 如果它比左边的数字小，那就把左边的数字右移一位，
  * 继续向左比较，直到找到比 key 更小的数字，把 key 插到它的后面。

## 复杂度

* 时间复杂度：$O(n^2)$，n 为数组长度。
* 空间复杂度：$O(1)$。

## 应用

* 数组规模小的情况下。
* 数组已经是部分排好序了，只剩一小部分需要排序。

## 代码

JavaScript Code

```javascript
function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        const key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
```