折半插入排序

核心思想

折半插入排序作为插入排序的改进版，不同的地方在于 寻找插入位置时的操作。我们知道，插入排序分为两大区间，一个是前面排好序的有序队列，另一个是未排好序的乱序队列。例如：

在上面的队列中，前面的 6 到 45 已经是排好序了的有序队列，右边的 17 到 9 是还未排好序的乱序队列。现在需要对 17 进行插入操作，那么标准的插入排序是怎么样的？

标准插入排序是 挨着挨着进行比较，然后找到正确的插入位置，插入进去。

既然前面是有序的数列，因此我们在查找插入位置的时候，实际上可以使用 二分查找 来找，这样能 提升查找插入位置效率。

另外，在移动元素上，折半插入排序和标准插入排序也有区别：

标准插入排序：一边查找插入的位置，一边移动元素
折半插入排序：先通过二分查找找到插入的位置，再将插入位置之后的元素统一做移动操作

代码实现

function binaryInsertionSort(arr){
  // 从第二个元素开始遍历，因为第一个元素会被视为已排序元素
  for(let i = 1; i < arr.length; i++){
    let current = arr[i]; // 当前要插入的元素
    let left = 0;
    let right = i - 1;
    
    // 这里就是使用二分查找，查找正确的插入位置
    while(left <= right){
      let mid = Math.floor((left + right) / 2);
     	if(arr[mid] < current){
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    // 跳出上面的 while 循环，说明 left > right
    // 说明找到了插入位置，插入位置就是 left 这个位置
    
    // 移动
    for(let j = i-1; j >= left; j--){
      arr[j+1] = arr[j];
    }
    
    // 插入
   	arr[left] = current;
  }
}

const arr = [7, 20, 27, 36, 55, 60, 28, 36, 67, 44, 16];
binaryInsertionSort(arr);
console.log(arr);

总结：整个折半插入相比标准插入，区别就在于查找插入位置的代码。

标准插入：

// 一边移动一边查找插入位置
while (j >= 0 && arr[j] > current) {
  arr[j + 1] = arr[j];
  j--;
}

折半插入：

// 先使用二分查找来找到插入的位置
while(left <= right){
  let mid = Math.floor((left + right) / 2);
  if(arr[mid] < current){
    left = mid + 1;
  } else {
    right = mid - 1;
  }
}

// 跳出上面的 while 循环，说明 left > right
// 说明找到了插入位置，插入位置就是 left 这个位置

// 然后再统一的做移动操作
for(let j = i-1; j >= left; j--){
  arr[j+1] = arr[j];
}

复杂度

时间复杂度：O(n^2) 提升的是查找的效率，但是移动的次数是没有变化的。
空间复杂度：O(1)

稳定性

和标准插入排序是一样的，是一种稳定排序。

对二分查找的新理解

二分查找不一定是要找一个精确的target，也可以去寻找一个坐标，就像这里一样，可以找到target应该在顺序数组中的位置

-EOF-

#算法

折半插入排序

http://localhost:8090/archives/zhe-ban-cha-ru-pai-xu

作者

Administrator

发布于

2026年01月30日

许可协议

二分查找上一篇

希尔排序核心思想下一篇