TypeScript 算法手册【插入排序】
文章目录
- TypeScript 算法手册 - 插入排序
- 1. 插入排序简介
- 1.1 插入排序定义
- 1.2 插入排序特点
- 2. 插入排序步骤过程拆解
- 2.1 选择当前元素
- 2.2 寻找插入位置
- 2.3 插入元素
- 3. 插入排序的优化
- 3.1 二分查找插入排序
- 案例代码和动态图
- 4. 插入排序的优点
- 5. 插入排序的缺点
- 总结
【 已更新完 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 插入排序特点
- 简单直观: 插入排序的思想非常贴近生活，容易理解和实现
- 稳定性: 插入排序是稳定的排序算法
- 原地排序: 插入排序是原地排序算法，不需要额外的存储空间
- 适应性: 对于部分有序的数组，插入排序的效率很高
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. 插入排序的优点
- 实现简单，容易理解
- 对于小规模或基本有序的数据，效率很高
- 是稳定的排序算法
- 适合频繁操作的数据结构(如链表)，不需要额外的空间
5. 插入排序的缺点
- 对于大规模乱序数据，时间复杂度较高为O(n^2)
- 每次只能将数据移动一位，效率不如快速排序等高级排序算法
总结
插入排序虽然在大规模数据排序中不如一些高级算法高效，它在某些特定场景下仍然有其独特的优势。当数据规模较小或者数据已经基本有序时，插入排序可能会比一些复杂的排序算法更快。
插入排序的思想也被广泛应用在其他算法中。在快速排序中，当子数组的大小小于某个阈值时，会使用插入排序来完成最后的排序工作，在小规模数据上插入排序更有效。
理解每种算法的特点和适用场景，才能在实际应用中做出最佳选择。插入排序教会我们，有时候看似简单的方法，在特定情况下可能会有出人意料的好表现。
喜欢的话就点个赞 ❤️,关注一下吧,有问题也欢迎讨论指教。感谢大家!!!
下期预告: TypeScript 算法手册 - 归并排序