Skip to content

折半插入排序

· 4 min

核心思想#

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

image-20250214130706386

在上面的队列中，前面的 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]
}

复杂度#

稳定性#

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

-EOF-