insertion_sort.md

排序 - 插入排序

概念

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

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

算法

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

复杂度

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

应用

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

代码

JavaScript Code

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;
    }
}