当前位置: 首页 > news >正文

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 插入排序特点

  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 算法手册 - 归并排序


http://www.mrgr.cn/news/40697.html

相关文章:

  • C for Graphic:DNF手游残影效果
  • 宝塔的软件商店打不开怎么办?
  • 进程控制
  • Prompt 模版解析:诗人角色的创意引导与实践
  • 【科研日常】2024年计算图形学与多媒体CCF A、B类会议投稿截止日期汇总
  • springboot系列--web相关知识探索二
  • C++之String类(上)
  • 图解MySQL 1-22 章节相关总结
  • 大数据毕业设计选题推荐-个性化图书推荐系统-Python数据可视化-Hive-Hadoop-Spark
  • SHA-1 是一种不可逆的、固定长度的哈希函数,在 Git 等场景用于生成唯一的标识符来管理对象和数据完整性
  • CSP-J模拟赛(1)补题报告
  • OpenSCAP部署、使用与原理分析
  • 浏览器预解析机制
  • 螺狮壳里做道场:老破机搭建的私人数据中心---Centos下docker学习02(yum源切换及docker安装配置)
  • 叶绿素透射反射率与波长
  • 【AGC005D】~K Perm Counting(计数抽象成图)
  • 爵士编曲:爵士钢琴编写的规律和步骤 关于教程的个人想法 举一反三
  • Java面试必杀技为什么面试官都爱问源码?
  • MacOS配置python环境
  • 数据工程师岗位常见面试问题-3(附回答)