# 排序 - 插入排序

## 概念

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

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

## 算法

* 假设数组的第一个数字是“已排序”部分。
* 从第二个数字开始，首先用一个变量记录这个数字 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;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://suki.gitbook.io/notes/articles/sorting/insertion_sort.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.