插入排序

问题

实现插入排序算法。

解答

基本实现

function insertionSort(arr) {
  const len = arr.length;
  
  // 从第二个元素开始，第一个元素默认已排序
  for (let i = 1; i < len; i++) {
    // 当前要插入的元素
    const current = arr[i];
    // 已排序部分的最后一个索引
    let j = i - 1;
    
    // 在已排序部分从后往前找插入位置
    while (j >= 0 && arr[j] > current) {
      // 比 current 大的元素往后移
      arr[j + 1] = arr[j];
      j--;
    }
    
    // 插入到正确位置
    arr[j + 1] = current;
  }
  
  return arr;
}

// 测试
console.log(insertionSort([5, 2, 4, 6, 1, 3])); // [1, 2, 3, 4, 5, 6]
console.log(insertionSort([3, 1, 4, 1, 5, 9, 2, 6])); // [1, 1, 2, 3, 4, 5, 6, 9]

执行过程示意

// 原数组: [5, 2, 4, 6, 1, 3]

// i=1: current=2, 与5比较，5后移，插入2 → [2, 5, 4, 6, 1, 3]
// i=2: current=4, 与5比较，5后移，插入4 → [2, 4, 5, 6, 1, 3]
// i=3: current=6, 与5比较，6>5，位置不变 → [2, 4, 5, 6, 1, 3]
// i=4: current=1, 依次后移6,5,4,2，插入1 → [1, 2, 4, 5, 6, 3]
// i=5: current=3, 依次后移6,5,4，插入3 → [1, 2, 3, 4, 5, 6]

二分插入排序（优化版）

function binaryInsertionSort(arr) {
  const len = arr.length;
  
  for (let i = 1; i < len; i++) {
    const current = arr[i];
    
    // 二分查找插入位置
    let left = 0;
    let right = i - 1;
    
    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      if (arr[mid] > current) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    
    // 将 left 到 i-1 的元素后移
    for (let j = i - 1; j >= left; j--) {
      arr[j + 1] = arr[j];
    }
    
    arr[left] = current;
  }
  
  return arr;
}

// 测试
console.log(binaryInsertionSort([5, 2, 4, 6, 1, 3])); // [1, 2, 3, 4, 5, 6]

关键点

• 时间复杂度：平均和最坏 O(n²)，最好 O(n)（数组已有序时）
• 空间复杂度：O(1)，原地排序
• 稳定排序：相等元素的相对顺序不变
• 适用场景：小规模数据或基本有序的数据，效率较高
• 二分优化：减少比较次数，但移动次数不变，整体仍是 O(n²)