【算法-插入排序】基础知识,代码示例和应用场景

ops/2024/11/9 0:50:09/

插入排序是一种相对简单、直观的排序算法,有点类似打扑克牌时将一张张牌“插入”到合适位置的过程。虽然插入排序的效率不如高级排序算法,但它有自己独特的优点,尤其在小数据集或已部分有序的数据中表现出色。


什么是插入排序

插入排序是一种逐步构建有序列表的算法。它将数组分成“已排序部分”和“未排序部分”,然后从未排序部分中挑选元素插入到已排序部分的合适位置。想象打扑克牌时,一张张将牌放在手中按照大小排好,就是插入排序的过程。

插入排序的操作过程

插入排序

假设有一个无序的数组 [8, 4, 3, 7, 6],我们用插入排序把它从小到大排序。

  1. 第一步

    • 假设第一个元素 [8] 已经有序。
    • 从第二个元素开始 [4],插入到 [8] 之前。
    • 结果为 [4, 8, 3, 7, 6]
  2. 第二步

    • 将第三个元素 [3] 插入到 [4, 8] 中。
    • [3][4] 小,放到最前面。
    • 结果为 [3, 4, 8, 7, 6]
  3. 第三步

    • 将第四个元素 [7] 插入到 [3, 4, 8] 中。
    • [7][4] 大,但比 [8] 小,因此插入到 [8] 之前。
    • 结果为 [3, 4, 7, 8, 6]
  4. 第四步

    • 将第五个元素 [6] 插入到 [3, 4, 7, 8] 中。
    • [6][7] 小,所以插入到 [7] 之前。
    • 最终结果为 [3, 4, 6, 7, 8]

通过这样一轮轮的插入,数组逐渐变得有序。


插入排序的代码实现

下面是插入排序的 Java 代码实现,每一步都附带注释,方便理解。

java">public class InsertionSort {public static void insertionSort(int[] arr) {// 从第二个元素开始逐个插入for (int i = 1; i < arr.length; i++) {int current = arr[i];int j = i - 1;// 向左扫描已排序部分,找到插入位置while (j >= 0 && arr[j] > current) {arr[j + 1] = arr[j]; // 向右移动元素j--;}// 把当前元素插入到合适位置arr[j + 1] = current;}}public static void main(String[] args) {int[] arr = {8, 4, 3, 7, 6};insertionSort(arr);System.out.println(Arrays.toString(arr));}
}

代码运行过程

对于数组 [8, 4, 3, 7, 6],代码运行时会执行以下操作:

  • 第一次循环,i = 1,将 4 插入到 8 前面。
  • 第二次循环,i = 2,将 3 插入到 4 前面。
  • 第三次循环,i = 3,将 7 插入到 8 前面。
  • 第四次循环,i = 4,将 6 插入到 8 前面。

这样一轮轮下来,最终输出的是 [3, 4, 6, 7, 8]


插入排序的时间复杂度

插入排序的时间复杂度取决于数据的有序程度:

  • 最佳情况:当数组已经有序时,插入排序只需逐一比较,无需移动元素,时间复杂度为 (O(n))。
  • 最差情况:当数组完全逆序时,每个元素都需要比较和移动,时间复杂度为 (O(n^2))。
  • 平均情况:在一般随机数据下,插入排序的时间复杂度为 (O(n^2))。

由于其时间复杂度,插入排序并不适合处理大规模数据,但在小数据集或近似有序的场景下表现不错。


插入排序的适用场景

  1. 小型数据集:对于数量较少的数据(如几十个元素),插入排序的性能较好,足以胜任排序任务。
  2. 部分有序的数组:如果数组大部分是有序的,插入排序会比其他复杂排序算法更有效率,因为它不需要做太多的移动。
  3. 实时数据插入:在不断插入数据并保持有序的场景下,插入排序的特性十分适合,比如插入排序在链表的排序上应用较多。

插入排序的优缺点

优点
  1. 简单易懂算法逻辑清晰、容易实现,适合初学者掌握。
  2. 稳定性:插入排序是稳定的排序算法,相等的元素不会交换位置。
  3. 在线排序:能够实现实时插入,即在排序过程中可以逐步添加新元素,并将其插入到合适的位置。
缺点
  1. 效率较低:当数据规模增大时,插入排序的时间复杂度为 (O(n^2)),处理大数据时性能较差。
  2. 不适合逆序排序:当数据逆序或接近逆序时,插入排序需要更多的移动操作,因此效率不佳。

插入排序的实际应用

插入排序在很多实际情况下有用,比如:

  1. 少量数据排序:对于小数据量的情况(例如少于 100 个元素),插入排序的效率可以和高级排序算法媲美。
  2. 排序链表:插入排序在链表中应用广泛,因为在链表中插入元素时效率较高。
  3. 基本有序的数据:当数据大致有序,或者需要不断插入新数据并保持有序时,插入排序的性能表现良好。

插入排序的总结

插入排序是一种操作简单、适合初学者学习的排序算法。它的特点是在小规模数据或基本有序的情况下性能较好,且插入时不需要额外空间。虽然插入排序的效率不如高级排序算法,但在某些应用场景中仍然具有实际价值。

希望通过本章的学习,能够帮助大家更好地理解插入排序的基本原理、适用场景和代码实现。在掌握插入排序后,可以继续学习其他更复杂的排序算法,提升数据处理效率。


http://www.ppmy.cn/ops/132075.html

相关文章

VBA02-初识宏——EXCEL录像机

一、录制宏 录制宏其实就是将一系列操作结果录制下来&#xff0c;并命名存储。这些操作可以是关于数据的处理、格式的设置、函数的运用等&#xff0c;相当于在编程语言&#xff08;如VB&#xff09;中定义的一个子程序。 在录制宏时&#xff0c;软件会记录用户执行的一系列操…

ubuntu 22.04 硬件配置 查看 显卡

ubuntu 22.04 硬件配置 查看 显卡 1. 参考文档 ubuntu 安装 nvidia 驱动 https://blog.51cto.com/u_13628828/7056095 input: HDA NVidia HDMI/DP,pcm3 as /devices/pci0000:00/0000:00:01.0/0000:01:00.1/sound/card1/input11 input: HDA NVidia HDMI/DP,pcm7 as /devices/…

QinQ VLAN技术

QinQ VLAN技术的主要作用包括扩展VLAN数量、实现私网VLAN透传、提供二层隔离和多租户环境等。以下是对这些作用的详细介绍&#xff1a; 扩展VLAN数量 解决VLAN ID不足问题&#xff1a;QinQ技术通过在原有的802.1Q标签基础上再增加一层802.1Q标签&#xff0c;从而将VLAN数量从40…

Spring Boot整合RabbitMQ

这里只会演示部分常用的工作模式 1.工作队列模式 1.1引入相关依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-amqp</artifactId></dependency><dependency><groupId>org.s…

2020年美国总统大选数据分析与模型预测

数据集取自&#xff1a;2020年&#x1f1fa;&#x1f1f8;&#x1f1fa;&#x1f1f8;美国大选数据集 - Heywhale.com 前言 对2020年美国总统大选数据的深入分析&#xff0c;提供各州和县层面的投票情况及选民行为的可视化展示。数据预处理阶段将涉及对异常值的处理&#xff0…

nuPlan最新SOTA,香港科技大学发布基于学习决策范围内的规划PlanScope

nuPlan最新SOTA&#xff0c;香港科技大学发布基于学习决策范围内的规划PlanScope Abstract 在自动驾驶的背景下&#xff0c;基于学习的方法在规划模块的开发中表现出了很大的潜力。在规划模块的训练过程中&#xff0c;直接最小化专家驾驶日志与规划输出之间的差异是一种广泛采…

关于Django 模型字段 `choices`自定义数据类型的枚举——补充

文章目录 1. 处理 datetime 类型的 choices2. 处理 time 类型的 choices3. 处理 Decimal 类型的 choices4. 处理 UUID 类型的 choices5. 处理 float 类型的 choices 在 Choices 类的基础上扩展&#xff0c;可以将 choices 与特定数据类型&#xff08;如 date 或 datetime&a…

【react】Redux基础用法

1. Redux基础用法 Redux 是一个用于 JavaScript 应用的状态管理库&#xff0c;它不依赖于任何 UI库&#xff0c;但常用于与 React 框架配合使用。它提供了一种集中式的状态管理方式&#xff0c;将应用的所有状态保存在一个单一的全局 Store&#xff08;存储&#xff09;中&…