插入排序

插入排序如何工作？

• 首元素视为已排序区间 [0, 0];
• 取出 nums[i] 作为 base, 在已排序区间内从右向左找插入位置;
• 比 base 大的元素整体右移一位, 空出的位置放入 base;
• i 从 1 到 n-1 重复, 已排序区间逐渐扩大;

插入排序如何实现？

function insertionSort(nums: number[]): void {
  for (let i = 1; i < nums.length; i++) {
    const base = nums[i];
    let j = i - 1;
    while (j >= 0 && nums[j] > base) {
      nums[j + 1] = nums[j];
      j--;
    }
    nums[j + 1] = base;
  }
}

插入排序的特性是什么？

• 时间复杂度: O(n^2);
• 空间复杂度: O(1);
• 稳定性: 稳定排序, 只有 nums[j] > base 才右移, 相等元素保持原序;

插入排序比冒泡和选择排序好在哪？

• 常数更小: 内层是元素搬移, 而不是反复交换;
• 近有序输入接近 O(n): 每个元素只需移动很少的位置;
• 对比: 冒泡排序每轮都涉及交换, 开销高; 选择排序不稳定;
• 适用: 小数据量排序;