二分插入排序

问题

实现二分插入排序（拆半插入排序），在插入排序的基础上，使用二分查找来确定插入位置。

解答

基本思路

插入排序在查找插入位置时需要逐个比较，时间复杂度为 O(n)。二分插入排序利用已排序部分的有序性，用二分查找将查找插入位置的复杂度降为 O(log n)。

实现代码

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 就是插入位置，将 left 到 i-1 的元素后移
    for (let j = i - 1; j >= left; j--) {
      arr[j + 1] = arr[j];
    }
    
    // 插入元素
    arr[left] = current;
  }
  
  return arr;
}

// 测试
const arr = [5, 2, 9, 1, 5, 6];
console.log(binaryInsertionSort(arr)); // [1, 2, 5, 5, 6, 9]

与普通插入排序对比

// 普通插入排序 - 边比较边移动
function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const current = arr[i];
    let j = i - 1;
    
    // 查找和移动同时进行
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current;
  }
  return arr;
}

// 二分插入排序 - 先查找再移动
function binaryInsertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const current = arr[i];
    
    // 1. 二分查找插入位置
    let left = 0, right = i - 1;
    while (left <= right) {
      const mid = (left + right) >> 1;
      if (arr[mid] > current) right = mid - 1;
      else left = mid + 1;
    }
    
    // 2. 统一移动元素
    for (let j = i - 1; j >= left; j--) {
      arr[j + 1] = arr[j];
    }
    arr[left] = current;
  }
  return arr;
}

关键点

• 比较次数减少：查找插入位置从 O(n) 降为 O(log n)
• 移动次数不变：元素移动仍是 O(n)，总体时间复杂度仍为 O(n²)
• 稳定排序：相等元素使用 arr[mid] > current 保证稳定性
• 适用场景：比较操作代价高时（如字符串比较）效果更明显
• 空间复杂度：O(1)，原地排序