TypeScript 算法手册【插入排序】

【 已更新完 TypeScript 设计模式 专栏，感兴趣可以关注一下，一起学习交流🔥🔥🔥 】

TypeScript 算法手册 - 插入排序

1. 插入排序简介

1.1 插入排序定义

插入排序是一种简单直观的排序算法，类似于我们整理图书馆的书架，当你面对一排杂乱无章的书籍时，该如何整理它们? 我们可能会这样做：从左到右一本一本来，拿起一本书，将它插入到已经按照特定顺序排列好的书籍中的正确位置，这就是插入排序的基本思想。

用TypeScript代码表示一个简单的插入排序:

function insertionSort(arr: number[]): number[] {
  const len = arr.length;
  for (let i = 1; i < len; i++) {
    let 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;
}

1.2 插入排序特点

1. 简单直观: 插入排序的思想非常贴近生活，容易理解和实现
2. 稳定性: 插入排序是稳定的排序算法
3. 原地排序: 插入排序是原地排序算法，不需要额外的存储空间
4. 适应性: 对于部分有序的数组，插入排序的效率很高

2. 插入排序步骤过程拆解

2.1 选择当前元素

for (let i = 1; i < len; i++) {
  let current = arr[i];
  // ...
}

这就像你在整理书架时，从第二本书开始，一本一本地拿起来准备插入到已经排好序的书籍中的正确位置。

2.2 寻找插入位置

let j = i - 1;
while (j >= 0 && arr[j] > current) {
  arr[j + 1] = arr[j];
  j--;
}

这个步骤就像你拿着一本书,从右向左比较已经排好序的书籍。如果遇到比你手上的书更大(或者按字母顺序更靠后)的,就将它们向右移动一格,给你手上的书腾出位置。

2.3 插入元素

arr[j + 1] = current;

找到正确的位置后,你就把手上的书插入到这个位置。

3. 插入排序的优化

3.1 二分查找插入排序

function binaryInsertionSort(arr: number[]): number[] {
  const len = arr.length;
  for (let i = 1; i < len; i++) {
    let left = 0;
    let right = i - 1;
    const current = arr[i];
    
    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      if (arr[mid] > current) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    
    for (let j = i - 1; j >= left; j--) {
      arr[j + 1] = arr[j];
    }
    arr[left] = current;
  }
  return arr;
}

这个优化版本就如你在整理书架时，不是从右向左一本一本比较，而是使用"二分法"快速找到插入位置。你手上拿着一本书，先看中间的书，如果你的书比它小就看左半边，比它大就看右半边，这样反复缩小范围直到找到正确的位置。这样可以减少比较的次数，提高整理书架的效率。

案例代码和动态图

const array = [49, 34, 25, 12, 22, 11];
const sortedArray = insertionSort(array);
console.log(sortedArray); // [11, 12, 22, 25, 34, 49]

4. 插入排序的优点

1. 实现简单，容易理解
2. 对于小规模或基本有序的数据，效率很高
3. 是稳定的排序算法
4. 适合频繁操作的数据结构(如链表)，不需要额外的空间

5. 插入排序的缺点

1. 对于大规模乱序数据，时间复杂度较高为O(n^2)
2. 每次只能将数据移动一位，效率不如快速排序等高级排序算法

总结

插入排序虽然在大规模数据排序中不如一些高级算法高效，它在某些特定场景下仍然有其独特的优势。当数据规模较小或者数据已经基本有序时，插入排序可能会比一些复杂的排序算法更快。

插入排序的思想也被广泛应用在其他算法中。在快速排序中，当子数组的大小小于某个阈值时，会使用插入排序来完成最后的排序工作，在小规模数据上插入排序更有效。

理解每种算法的特点和适用场景，才能在实际应用中做出最佳选择。插入排序教会我们，有时候看似简单的方法，在特定情况下可能会有出人意料的好表现。

喜欢的话就点个赞 ❤️,关注一下吧,有问题也欢迎讨论指教。感谢大家!!!

下期预告: TypeScript 算法手册 - 归并排序