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

Java 实现插入排序：[通俗易懂的排序算法系列之三]

news 来源：原创 2025/9/2 10:22:59

引言

大家好！欢迎继续关注我的排序算法系列。今天，我们要学习的是另一种非常基础且重要的排序算法——插入排序 (Insertion Sort)。

插入排序的思路非常贴近我们日常整理扑克牌的方式，理解起来相对自然。虽然它在最坏情况下的效率不高，但在某些特定场景下，它的表现甚至优于一些更高级的排序算法。

什么是插入排序？

想象一下你在玩扑克牌，手里已经握着几张排好序的牌（比如按点数从小到大）。现在你从牌堆里摸了一张新牌，你会怎么做？

通常，你会从右手边（或左手边）已排序的牌开始，逐张比较新牌和手里的牌，找到新牌应该插入的位置，然后将该位置及其后面的牌向后挪动一点，腾出空位，把新牌插进去。

插入排序就是基于这个思想：

将整个数组分为两部分： 左边是“已排序”区间，右边是“未排序”区间。
初始状态： 已排序区间只包含数组的第一个元素 arr[0]。
逐步扩展： 从未排序区间（从 arr[1] 开始）依次取出元素。
寻找位置并插入： 将取出的元素（我们称之为 current 或 now）与已排序区间的元素从右向左逐一比较。
移动元素： 如果已排序区间的元素大于 current，则将该元素向右移动一位。
重复比较和移动： 继续向左比较和移动，直到找到一个小于或等于 current 的元素，或者到达已排序区间的开头。
插入： 将 current 插入到最后移动元素的那个位置的后面（也就是空出来的位置）。
重复： 对未排序区间的所有元素重复步骤 3-7，直到所有元素都被插入到已排序区间中。

算法步骤详解 (以升序为例)

假设我们有数组 [5, 2, 4, 6, 1, 3]

初始： [5] | [2, 4, 6, 1, 3] ( | 分隔已排序和未排序)
处理 2 (now = 2)：
- 比较 2 和 5 -> 2 < 5 -> 移动 5 -> [_, 5] | [4, 6, 1, 3]
- j 变为 -1，循环结束。
- 插入 2 到 j+1 (即 0) -> [2, 5] | [4, 6, 1, 3]
处理 4 (now = 4)：
- 比较 4 和 5 -> 4 < 5 -> 移动 5 -> [2, _, 5] | [6, 1, 3]
- 比较 4 和 2 -> 4 >= 2 -> break 循环 (j 为 0)。
- 插入 4 到 j+1 (即 1) -> [2, 4, 5] | [6, 1, 3]
处理 6 (now = 6)：
- 比较 6 和 5 -> 6 >= 5 -> break 循环 (j 为 2)。
- 插入 6 到 j+1 (即 3) -> [2, 4, 5, 6] | [1, 3]
处理 1 (now = 1)：
- 比较 1 和 6 -> 1 < 6 -> 移动 6 -> [2, 4, 5, _, 6] | [3]
- 比较 1 和 5 -> 1 < 5 -> 移动 5 -> [2, 4, _, 5, 6] | [3]
- 比较 1 和 4 -> 1 < 4 -> 移动 4 -> [2, _, 4, 5, 6] | [3]
- 比较 1 和 2 -> 1 < 2 -> 移动 2 -> [_, 2, 4, 5, 6] | [3]
- j 变为 -1，循环结束。
- 插入 1 到 j+1 (即 0) -> [1, 2, 4, 5, 6] | [3]
处理 3 (now = 3)：
- 比较 3 和 6 -> 3 < 6 -> 移动 6 -> [1, 2, 4, 5, _, 6]
- 比较 3 和 5 -> 3 < 5 -> 移动 5 -> [1, 2, 4, _, 5, 6]
- 比较 3 和 4 -> 3 < 4 -> 移动 4 -> [1, 2, _, 4, 5, 6]
- 比较 3 和 2 -> 3 >= 2 -> break 循环 (j 为 1)。
- 插入 3 到 j+1 (即 2) -> [1, 2, 3, 4, 5, 6]
完成： 数组已排序。

Java 代码实现

下面是插入排序的 Java 代码实现，包含了我们之前讨论过的清晰注释：

import java.util.Arrays;public class InsertSort { // 类名建议大写开头public static void main(String[] args) {// 1. 初始化一个无序数组int[] arr = {2, 4, 5, 6, 1, 3};System.out.println("排列前的数据：" + Arrays.toString(arr));// 2. 调用插入排序函数insertSortFunc(arr);// 3. 打印排序后的结果System.out.println("排列后的数据：" + Arrays.toString(arr));// 测试其他例子int[] arr2 = {31, 25, 18, 16, 19, 82, 71, 35, 40, 45, 48, 49, 50};System.out.println("\n另一个例子，排序前：" + Arrays.toString(arr2));insertSortFunc(arr2);System.out.println("另一个例子，排序后：" + Arrays.toString(arr2));}/*** 插入排序函数* @param arr 待排序数组*/private static void insertSortFunc(int[] arr) {if (arr == null || arr.length < 2) {return; // 无需排序}// 外层循环：从第二个元素开始（索引1），遍历所有待插入的元素for (int i = 1; i < arr.length; i++) {// 1.1 记录需要插入的数据值（当前待排序元素）int now = arr[i];// 1.2 记录已排序区间的最后一个元素的索引（即待插入元素的前一个）int j = i - 1;// 1.3 内层循环：在已排序区间从右向左查找插入位置// 条件：j 没有越界 (>=0) 并且 当前考察的已排序元素 arr[j] 大于 待插入值 nowwhile (j >= 0 && now < arr[j]) {// 1.4 如果已排序元素大于待插入值，则将该已排序元素向右移动一位arr[j + 1] = arr[j];j--; // 继续向左比较}// 循环结束时，j 指向的是第一个小于或等于 now 的元素，或者 j 为 -1（表示 now 是最小的）// 因此，now 应该插入的位置是 j+1// 1.6 将需要插入的值（now）放入正确的位置 (j+1)// (优化：如果 now 没有移动过，即 j == i-1，可以省略这次赋值，但差别不大)arr[j + 1] = now;// (可选) 打印每一轮的结果// System.out.println("第 " + i + " 轮 (插入 " + now + "): " + Arrays.toString(arr));}}
}

代码解读

insertSortFunc(int[] arr): 接受数组并进行原地排序。
边界检查: 处理 null 或长度小于 2 的情况。
外层循环 for (int i = 1; ...):
- i 从 1 开始，因为第一个元素 arr[0] 自动构成初始的已排序区间。
- i 指向当前待插入的元素。
int now = arr[i];: 保存待插入元素的值，防止在后续移动操作中被覆盖。
int j = i - 1;: j 初始化为已排序区间的最右边元素的索引。
内层循环 while (j >= 0 && now < arr[j]):
- 这是核心的查找和移动过程。
- j >= 0: 确保比较不会越过数组的左边界。
- now < arr[j]: 如果待插入值 now 小于当前比较的已排序元素 arr[j]，则需要移动。
arr[j + 1] = arr[j];: 将较大的元素 arr[j] 向右移动到 arr[j+1] 的位置。注意，这不是交换，是覆盖/后移。
j--;: 将 j 向左移动，准备比较已排序区间中的下一个元素。
arr[j + 1] = now;: 当 while 循环结束时，意味着找到了 now 的正确插入位置，这个位置就是 j+1 (因为 j 是最后一个使得 arr[j] >= now 或 j=-1 的索引)。将之前保存的 now 放入此位置。

算法特性分析

时间复杂度：
- 最坏情况 (Worst Case): O(n²)。当输入数组完全逆序时，每个元素都需要与前面所有已排序元素进行比较和移动。内层 while 循环总共执行 1 + 2 + ... + (n-1) 次，即 O(n²)。
- 平均情况 (Average Case): O(n²)。平均来说，每个元素大约需要比较和移动其前面已排序元素的一半。
- 最好情况 (Best Case): O(n)。当输入数组已经基本有序或完全有序时，内层 while 循环的条件 now < arr[j] 很少（或从不）满足，每个元素只需要进行一次比较（与前一个元素比较）就能确定位置，无需移动。总时间复杂度接近线性。
空间复杂度：
- O(1)。插入排序是原地排序，只需要一个额外的 now 变量来存储待插入元素的值。
稳定性：
- 插入排序是稳定 (stable) 的排序算法。
- 当比较 now 和 arr[j] 时，只有 now < arr[j] 才移动 arr[j]。如果 now == arr[j]，while 循环会终止 (now < arr[j] 不成立)，now 会被插入到 arr[j] 的后面（arr[j+1] 的位置）。这保证了相等元素的原始相对顺序得以保留。

优缺点与适用场景

优点：
- 实现简单， 易于理解和编码。
- 原地排序， 空间复杂度低 (O(1))。
- 稳定。
- 对小规模数据或基本有序的数据非常高效。 这是插入排序最大的优势之一，其 O(n) 的最好情况时间复杂度很有用。
- 在线算法： 可以边接收数据边排序，因为它可以逐步构建排序好的序列。
缺点：
- 平均和最坏时间复杂度高 (O(n²))， 不适合处理大规模的无序数据。元素移动次数较多。
适用场景：
- 数据量小的数组排序。
- 数组基本有序的情况（此时效率很高，接近 O(n)）。
- 作为更复杂排序算法（如 Timsort、Introsort）的子过程，用于处理小规模子数组或在最后阶段优化基本有序的序列。
- 需要稳定排序且空间受限的场景。

总结

插入排序通过将元素逐个插入到已排序的子序列中来实现排序。它简单、稳定、空间效率高，并且在处理小数据量或近乎有序的数据时表现出色（最好情况 O(n)）。然而，其 O(n²) 的平均和最坏时间复杂度使其不适用于大规模乱序数据。理解插入排序的特性，有助于我们在合适的场景选择它，或者理解它在混合排序算法中的作用。

感谢阅读排序算法系列的第三篇！接下来，我们将开始探索更高级、平均效率更高的排序算法，比如归并排序或快速排序。敬请期待！

如果你觉得有收获，请不吝点赞、评论、收藏和关注！

Java 实现插入排序：[通俗易懂的排序算法系列之三]

引言大家好！欢迎继续关注我的排序算法系列。今天，我们要学习的是另一种非常基础且重要的排序算法——插入排序 (Insertion Sort)。插入排序的思路非常贴近我们日常整理扑克牌的方式，理解起来相对自然。虽然它在最坏情况下的效率不高&…...

编程日记 2025/9/2 10:22:59

HarmonyOS：WebView 控制及 H5 原生交互实现

一、效果展示二、技术栈技术栈： 编程语言：使用 TypeScript 进行开发，借助其类型系统提升代码的可读性与稳定性。框架与库：基于鸿蒙系统相关框架（如kit.ArkWeb、hadss/hmrouter&#xff09…...

编程日记 2025/8/26 14:55:56

250405-VSCode编辑launch.json实现Debug调试Open-WebUI

A. 最终效果根据__init__.py配置launch.json 根据中utils/chat.py中form_data的messages [{role: user, content: 唐老鸭}],可以找到用户输入，进而通过关键词或模型调用的方式，对敏感问题进行特殊处理。 B. 文件配置 launch.json // { // /…...

编程日记 2025/8/30 13:31:45

SQL Server 数据库实验报告

1.1 实验题目：索引和数据完整性的使用 1.2 实验目的： （1）掌握SQL Server的资源管理器界面应用； （2）掌握索引的使用； （3）掌握数据完整性的…...

编程日记 2025/8/28 4:13:13

【寻找Linux的奥秘】第三章：基础开发工具（上）

请君浏览前言1. 软件包管理器1.1 linux中安装软件1.2 yum的具体操作1.2.1 查找软件包1.2.2 安装软件1.2.3 卸载软件 1.3 小结 2. 编辑器vim2.1 vim的基本概念和操作2.2 命令模式的命令集光标定位其他命令模式切换（常用的） 2.3 末⾏模式的命令集2.4 小结…...

编程日记 2025/8/27 7:10:38

Photoshop 2025 Mac中文Ps图像编辑

Photoshop 2025 Mac中文Ps图像编辑文章目录 Photoshop 2025 Mac中文Ps图像编辑一、介绍二、效果三、下载一、介绍 Adobe Photoshop 2025 Mac版集成了多种强大的图像编辑、处理和创作功能。①强化了Adobe Sensei AI的应用，通过智能抠图、自动修复、图像生成等功能…...

编程日记 2025/8/28 13:53:06

#SVA语法滴水穿石# （004）关于 ended 和 triggered 用法

在 SystemVerilog 断言（SVA, SystemVerilog Assertions）中，ended 是一个用于序列（sequence）的关键字，它表示某个序列（sequence）在特定时间点已经成功匹配（即“结束”）。 ended 主要用于同步不同序列的时间关系，尤其是在多序列组合或属性（property）中需要对齐时…...

编程日记 2025/8/29 3:49:15

16.1Linux自带的LED灯驱动实验(知识)_csdn

前面我们都是自己编写 LED 灯驱动，其实像 LED 灯这样非常基础的设备驱动， Linux 内核已经集成了。 Linux 内核的 LED 灯驱动采用 platform 框架，因此我们只需要按照要求在设备树文件中添加相应的 LED 节点即可，本章我们就来学习如…...

编程日记 2025/8/31 13:13:28

普通类、抽象类和接口的区别

1. 普通类 (Concrete Class) 定义：完整的类，可以直接实例化特点： 可以包含属性、普通方法（有具体实现）和构造方法可以被直接实例化创建对象可以被继承（除非用final修饰） 示例&#xff1…...

编程日记 2025/8/29 7:54:56

使用 Elastic 实现端到端的大语言模型（LLM）可观测性：洞察生成式 AI 应用这个不透明的世界

作者：来自 Elastic Daniela Tzvetkova 及 Bahubali Shetti 在快速发展的人工智能领域，大语言模型（Large Language Models - LLMs）已成为创新的灯塔，为各行各业带来了前所未有的能力。从生成类人文本、翻译语言到提供个…...

编程日记 2025/8/30 0:58:36

15.2linux设备树下的platform驱动编写(程序)_csdn

我尽量讲的更详细，为了关注我的粉丝！！！ 修改设备树文件： 这个我们在上一章已经写过了，但是还是带着大家来重写一遍！ 1.打开pinctrl-stm32.c 这个文件： strict 成员变量默认为 true&…...

编程日记 2025/9/1 7:55:01

Java的Selenium的特殊元素操作与定位之window切换

当你要操作另外一个窗口页面的元素时，一定要注意先切换窗口切换方式:传入要操作窗口的name或者句柄handle driver.switchTo.window(nameOrHandle); 如何获取到窗口的句柄 driver.getWindowHandle();//获取当前操作窗口的句柄driver.getWindowHandles();//获取测…...

编程日记 2025/8/28 12:28:36

【Rust学习】Rust环境搭建和Rust基础语法

本文专栏：Rust学习目录一，Rust环境搭建 1，C环境安装 2，Rust下载 3，Rust安装 4，Rust环境检测二，创建Rust项目 1，rustc 2，cargo 三，输出到命令行 …...

编程日记 2025/8/30 20:35:45

在windows环境下通过docker-compose脚本自动创建mysql和redis

一、环境版本在windows环境下通过docker容器运行各种服务，使用的软件版本如下： docker desktop ：V4.39.0 【docker的安装环境设置略】 mysql：9.2 redis：7.4.2 二、各配置文件 1.已经解决了字符集和排序规则问题造成…...

编程日记 2025/8/29 7:30:05

【玩泰山派】2、制作buildroot镜像，并烧录

文章目录前言制作buildroot镜像过程搭建环境（docker版）下载泰山派开发的sdk利用制作的镜像和下载的sdk去启动开发docker容器编译buildroot镜像参考前言泰山派官方提供了不少现成的镜像但是都买了泰山派了，肯定是想自己编译折腾下&…...

编程日记 2025/8/26 23:00:09

实验二 VLAN 的配置与应用

一、实验目的 1. 熟悉 VLAN 和 PORT VLAN 的原理； 2. 熟悉华为网络模拟器的使用； 3. 掌握网络拓扑图的绘制； 4. 掌握单交换机内 VLAN 的配置。二、实验设备 PC、华为模拟器 ENSP。三、实验步骤知识准备：VLAN 和 PORT V…...

编程日记 2025/8/23 5:12:40

【C/C++算法】蓝桥杯之递归算法（如何编写想出递归写法）

绪论：冲击蓝桥杯一起加油！！ 每日激励：“不设限和自我肯定的心态：I can do all things。 — Stephen Curry” 绪论： ———————— 早关注不迷路，话不多说安全带系好，发车啦&am…...

编程日记 2025/8/30 12:35:58

coding ability 展开第九幕（位运算——进阶篇）超详细！！！！

文章目录前言丢失的数字两整数之和只出现一次的数字II消失的两个数字总结前言上一篇博客，我们已经把位运算的基础知识，以及基本运算都掌握啦上次的习题还是让人意犹未尽，今天我们来尝试一下难一点的题目位运算熟练起来真的让人觉得做题是…...

编程日记 2025/8/29 18:30:34

Python实现NOA星雀优化算法优化随机森林回归模型项目实战

说明：这是一个机器学习实战项目（附带数据代码文档视频讲解），如需数据代码文档视频讲解可以直接到文章最后关注获取。 1.项目背景在现代数据科学领域，回归分析是解决预测问题的核心工具之一。然而，在面对复…...

编程日记 2025/8/25 22:20:14

蓝桥云客--浓缩咖啡液

4.浓缩咖啡液【算法赛】 - 蓝桥云课问题描述蓝桥杯备赛选手小蓝最近刷题刷到犯困，决定靠咖啡续命。他手上有 N 种浓缩咖啡液，浓度分别是 A1%, A2%, …, AN%，每种存货都是无限的。为了提神又不炸脑，小蓝需要按比例混合这…...

编程日记 2025/8/31 14:50:16

异常【C++】

文章目录异常异常的概念和基本语法异常的三个关键字： 异常抛出和被接收的过程异常的再次抛出再次抛出被非catch（...）捕捉到的异常再次抛出被catch（...）捕捉到的异常异常规范异常安全异常的优缺点优点缺点总结&#x…...

编程日记 2025/8/29 4:08:47

关于图片分类任务的猜想 | 撰写论文 paper

关于图片分类任务的猜想 | 撰写论文 paper 背景Yolo 是一次巨大的飞跃过滤无关的特征Yolo 的问题背景在计算视觉领域，有几个关键的演变。 1）CNN 卷积的出现，这是一个大的创新； 2）从卷积到 AlexNet ，是更…...

编程日记 2025/9/1 4:53:50

路由器和交换机

路由器和交换机分别位于OSI模型和TCP/IP模型的不同网络层次，具体对比如下： 1. 路由器（Router） 所属层级： OSI模型：网络层（第3层）TCP/IP模型：网络互联层（Int…...

编程日记 2025/8/23 4:57:35

jEasyUI 表单验证

jEasyUI 表单验证引言 jEasyUI 是一款流行的 jQuery UI 扩展库，它提供了丰富的 UI 组件和交互效果，极大地方便了前端开发工作。在 jEasyUI 中，表单验证是一个非常重要的功能，它可以帮助开发者确保用户输入的数据符合预期的格式和规则。本文将详细介绍 jEasyUI 表单验证的…...

编程日记 2025/9/2 8:23:53

PIKE 助力知识库进阶：多模型协作下的精准信息 “捕手”

PIKE（通常指的是字节跳动提出的一种技术）增强检索知识库是一种结合了先进的信息检索技术和知识库管理的系统。它旨在提高知识检索的准确性、效率和召回率，以更好地满足用户对知识的需求。特点和工作原理数据增强 ：对知识库中…...

编程日记 2025/8/29 22:47:16

使用Ubuntu18恢复群晖nas硬盘数据外接usb

使用Ubuntu18恢复群晖nas硬盘数据外接usb 1. 接入硬盘2.使用Ubuntu183.查看nas硬盘信息3. 挂载nas3.1 挂载损坏nas硬盘(USB)3.2 挂载当前运行的nas 4. 拷贝数据分批传输 5. 新旧数据对比 Synology NAS 出现故障，DS DiskStation损坏，则可以使用计算机和 U…...

编程日记 2025/8/28 11:23:18

Dify票据识别遇到的分支判断不准确问题

已测试这篇文章中 https://zhuanlan.zhihu.com/p/5465385787 使用多分支条件判断使用不同的大模型识别图片内容发现了细节问题。在使用时若不注意，分支会出现走向不准的问题。需要关注部分下方红框处。1，2后不能跟点。否则会出问。除此之外&#xff0…...

编程日记 2025/8/18 0:39:19

Flutter学习总结之Android渲染对比

一、Android 界面渲染机制（基于原生 View 体系） 1. 核心渲染流程（源码级解析） 三阶段渲染流程（ViewRootImpl驱动）： Measure 阶段（measure()）： View调用onMea…...

编程日记 2025/8/29 23:01:31

Media streaming is a huge topic with a bunch of scattered technologies, protocols, and formats. You may feel like hearing fragments without seeing the big picture. Let’s build that mental map together — here’s a high-level overview that connects everyt…...

编程日记 2025/8/27 17:40:48

引言