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

【java实现+4种变体完整例子】排序算法中【插入排序】的详细解析，包含基础实现、常见变体的完整代码示例，以及各变体的对比表格

news 来源：原创 2025/8/10 3:20:21

以下是插入排序的详细解析，包含基础实现、常见变体的完整代码示例，以及各变体的对比表格：
在这里插入图片描述

一、插入排序基础实现

原理

将元素逐个插入到已排序序列的合适位置，逐步构建有序序列。

代码示例

public class InsertionSort {void sort(int[] arr) {int n = arr.length;for (int i = 1; i < n; i++) {int key = arr[i]; // 待插入的元素int j = i - 1;// 将比 key 大的元素后移while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key; // 插入到正确位置}}
}

复杂度分析

时间复杂度：
- 最坏/平均：O(n²)（逆序或随机数据）。
- 最好（已有序）：O(n)。
空间复杂度：O(1)。
稳定性：稳定（相同值的元素相对顺序不变）。

二、常见变体及代码示例

1. 优化版（减少移动次数）

改进点：通过减少元素移动的次数，优化内层循环。
适用场景：数据接近有序时效率更高。

public class OptimizedInsertionSort {void sort(int[] arr) {int n = arr.length;for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;// 找到插入位置后一次性移动元素while (j >= 0 && arr[j] > key) {j--;}// 将 j+1 到 i 的元素后移一位for (int k = i; k > j + 1; k--) {arr[k] = arr[k - 1];}arr[j + 1] = key;}}
}

2. 二分插入排序

改进点：用二分查找确定插入位置，减少比较次数。
适用场景：数据规模较大时，减少比较时间。

public class BinaryInsertionSort {void sort(int[] arr) {int n = arr.length;for (int i = 1; i < n; i++) {int key = arr[i];int left = 0, right = i - 1;// 二分查找插入位置while (left <= right) {int mid = (left + right) / 2;if (arr[mid] > key) {right = mid - 1;} else {left = mid + 1;}}// 移动元素并插入for (int j = i - 1; j >= left; j--) {arr[j + 1] = arr[j];}arr[left] = key;}}
}

3. 递归实现

改进点：用递归替代循环，代码结构更清晰。
适用场景：教学或代码风格偏好递归。

public class RecursiveInsertionSort {void sort(int[] arr, int n) {if (n <= 1) return;sort(arr, n - 1); // 先排序前 n-1 个元素int key = arr[n - 1];int j = n - 2;// 将比 key 大的元素后移while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}

三、变体对比表格

变体名称	时间复杂度	空间复杂度	稳定性	主要特点	适用场景
基础插入排序	`O(n²)`（平均/最坏）， `O(n)`（最好）	`O(1)`	稳定	简单易实现，适合小规模或部分有序数据	小数据或接近有序的场景
优化版（减少移动次数）	`O(n²)`（平均/最坏）， `O(n)`（最好）	`O(1)`	稳定	减少内层循环的移动次数	数据接近有序时效率提升
二分插入排序	`O(n²)`（平均/最坏）， `O(n log n)`（比较次数）	`O(1)`	稳定	用二分查找减少比较次数	数据规模较大时减少比较时间
递归实现	`O(n²)`（所有情况）	`O(n)`	稳定	递归替代循环，代码结构清晰	教学或代码风格偏好递归的场景

四、关键选择原则

基础场景：优先使用基础实现，因其简单且适用于小规模数据。
优化需求：
- 接近有序数据：优化版（减少移动次数）可提升效率。
- 大规模数据：二分插入排序通过减少比较次数优化性能。
代码风格：递归实现适合教学或偏好函数式编程的场景，但需注意栈空间开销。
稳定性需求：所有变体均稳定，适用于需要保持元素相对顺序的场景（如排序带键值的记录）。
极端场景：已排序数据时，基础实现的时间复杂度降至 O(n)，是插入排序的优势场景。

通过选择合适的变体，可在特定场景下优化性能或代码可读性，同时保持算法的稳定性。

【java实现+4种变体完整例子】排序算法中【插入排序】的详细解析，包含基础实现、常见变体的完整代码示例，以及各变体的对比表格

以下是插入排序的详细解析，包含基础实现、常见变体的完整代码示例，以及各变体的对比表格： 一、插入排序基础实现原理将元素逐个插入到已排序序列的合适位置，逐步构建有序序列。代码示例 public class InsertionSort {void…...

编程日记 2025/8/10 3:20:21

神经网络的数学之旅：从输入到反向传播

目录神经网络简介神经元激活函数神经网络神经网络的工作过程前向传播（forward）反向传播（backward）训练神经网络神经网络简介神经元在深度学习中，必须要说的就是神经⽹络，或者说是⼈⼯神经⽹络&#…...

编程日记 2025/8/8 21:44:33

软件测试的页面交互标准：怎样有效提高易用性

当用户遇到"反人类"设计时 "这个按钮怎么点不了？"、"错误提示完全看不懂"、"我输入的内容去哪了？"——这些用户抱怨背后，都指向同一个问题：页面交互的易用性缺陷。作为软件测试工程师&a…...

编程日记 2025/8/4 8:46:12

Linux419 三次握手四次挥手抓包 wireshark

还是Notfound 没连接可能我在/home 准备配置静态IP vim ctrlr 撤销 u撤销配置成功准备关闭防火墙准备配置 YUM源 df -h 未看到sr0文件准备排查准备挂载还是没连接计划重启有了不重启了挂载准备修改配置文件准备准备清理缓存 ok 重新修改配…...

编程日记 2025/8/9 6:32:20

玩转Docker | 使用Docker部署tududi任务管理工具

玩转Docker | 使用Docker部署tududi任务管理工具前言一、tududi介绍Tududi简介核心功能特点二、系统要求环境要求环境检查Docker版本检查检查操作系统版本三、部署tududi服务下载镜像创建容器创建容器检查容器状态检查服务端口安全设置四、访问tududi服务访问tududi首页登录tu…...

编程日记 2025/8/5 4:43:29

ueditorplus编辑器已增加AI智能

之前功能请参考：https://www.geh3408.top/blog/76 下载：https://gitee.com/mo3408/ueditorplus 注意：key值需要单独获取，默认为DeepSeek，默认key有限制，请更换为自己的。演示地址：https://www.geh3408.top/ueditorplus/dist 更多体验：ueditorplus编辑器已增加AI智…...

编程日记 2025/8/6 1:34:27

深度学习数据预处理：Dataset类的全面解析与实战指南

前言在深度学习项目中，数据预处理是模型训练前至关重要的一环。一个高效、灵活的数据预处理流程不仅能提升模型性能，还能大大加快开发效率。本文将深入探讨PyTorch中的Dataset类，介绍数据预处理的常见技巧，并通过实战示例展示如何…...

编程日记 2025/8/6 9:15:38

【机器学习-周总结】-第4周

以下是本周学习内容的整理总结，从技术学习、实战应用到科研辅助技能三个方面归纳： 文章目录 📘 一、技术学习模块：TCN 基础知识与结构理解🔹 博客1：【时序预测05】– TCN（Temporal Convolutiona…...

编程日记 2025/8/8 16:51:12

高可靠 ZIP 压缩方案兼容 Office、PDF、TXT 和图片的二阶段回退机制

一、引言在企业级应用中，经常需要将多种类型的文件（如 Office 文档、PDF、纯文本、图片等）打包成 ZIP 并提供给用户下载。但由于文件路径过长、特殊字符或权限等问题，Go 标准库的 archive/zip 有时会出现“压缩成功却实际未写入…...

编程日记 2025/8/7 3:47:13

【HDFS入门】HDFS数据冗余与容错机制解析：如何保障大数据高可靠存储？

目录 1 HDFS冗余机制设计哲学 1.1 多副本存储策略的工程权衡 1.2 机架感知的智能拓扑算法 2 容错机制实现原理 2.1 故障检测的三重保障 2.2 数据恢复的智能调度 3 关键场景容错分析 3.1 数据中心级故障应对 3.2 数据损坏的校验机制 4 进阶优化方案 4.1 纠删码技术实…...

编程日记 2025/8/8 6:24:21

创建媒体对象 libvlc_media_t* m = libvlc_media_new_path(m_pInstance, inputPath.toStdString().c_str()); if (!m) return -1; // 创建失败返回错误 libvlc_media_new_path：根据文件路径创建媒体对象。注意：toStdString().c_str() 在Qt中可能存在临时字符串析构问题，建议…...

编程日记 2025/8/7 12:45:58

【DT】USB通讯失败记录

项目场景： DT小板 USB通讯失败问题描述 V1.1 板子含有降压电路、电容充电电路、姿态传感电路，语音电路、电弧电路、TF卡电路焊接完成：功能正常 V1.2 为方便数传模块拔插，把座子缩小并做在了背面，下载口反向方便狭…...

编程日记 2025/8/8 1:42:58

【笔记】网路安全管理-实操

一、系统安全防护-Windows 开始-》管理工具-》本地安全策略-》账户策略-》密码策略-》 1.密码必须符合复杂性要求。双击打开-》勾选已启用-》单击：应用-》单击：确定 2.密码长度最小值。双击打开-》设置密码长度最小值为：？个字符 3.密码最短使用期限。双击打开-》设置密码…...

编程日记 2025/7/30 14:03:03

FFMPEG-视频解码-支持rtsp|rtmp|音视频文件（低延迟）

本人亲测解码显示对比延迟达到7到20毫秒之间浮动兼容播放音视频文件、拉流RTSP、RTMP等网络流基于 Qt 和 FFmpeg 的视频解码播放器类，继承自 QThread，实现了视频流的解码、播放控制、帧同步和错误恢复等功能工作流程初始化阶段: 用户设置URL和显示尺寸调用play()启动线程解…...

编程日记 2025/8/9 8:09:48

LDR、MOV和STR指令详解

文章目录前言一、LDR指令详解 1.基本语法 2.寻址方式 3.伪指令形式二、MOV指令详解 1.基本语法 2.常见用法 3.特殊变体三、STR指令详解 1.基本语法 2.寻址方式四、三者区别与联系 1.基本语法 2.操作效率 3.大数值处理总结前言 ARM汇编中的LDR、MOV和STR是三个最基础也最…...

编程日记 2025/8/8 4:40:43

MATLAB 控制系统设计与仿真 - 41

鲁棒控制的其他函数 - 回路成型函数 loopsyn 灵敏度问题由鲁棒控制工具箱中的loopsyn就可以直接求解，该函数采用H无穷回路成型算法设计控制器，函数的调用格式为： [K,CL,gamma,info] loopsyn(G,Gd) % G为受控对象模型% Gd为期望的回路传递函…...

编程日记 2025/8/6 13:24:41

Scade 语言词法介绍

Scade 6 是一种具备形式化语法与形式化语义的领域特定语言（注1）。自2008年发布（注5）起，在 Scade Suite 产品系列中语言定义方面到目前未产生重要的改变(注2)。在下面的内容中将介绍Scade 语言的词法(注3)。注1&#x…...

编程日记 2025/7/30 15:25:17

Replicate Python client

本文翻译整理自：https://github.com/replicate/replicate-python 文章目录一、关于 Replicate Python 客户端相关链接资源关键功能特性二、1.0.0 版本的重大变更三、安装与配置1、系统要求2、安装3、认证配置四、核心功能1、运行模型2、异步IO支持3、流式输出模型…...

编程日记 2025/8/9 20:35:46

LLM做逻辑推理题 - 如何找出不标准的球？

题目: 有80个外观一致的小球，其中一个和其它的重量不同，（不知道更轻还是更重）。现在给你一个天平，允许你称四次，把重量不同的球找出来，怎么称？ 1. 答案第1次称量：天平…...

编程日记 2025/8/3 1:55:11

[密码学基础]国密算法深度解析：中国密码标准的自主化之路

国密算法深度解析：中国密码标准的自主化之路国密算法（SM系列算法）是中国自主研发的密码技术标准体系，旨在打破国际密码技术垄断，保障国家信息安全。本文将从技术原理、应用场景和生态发展三个维度，全面解…...

编程日记 2025/8/6 9:34:34

【计算机视觉】三维视觉项目 - Colmap二维图像重建三维场景

COLMAP 3D重建项目概述项目功能项目运行方式1. 环境准备2. 编译 COLMAP3. 数据准备4. 运行 COLMAP 常见问题及解决方法1. **编译问题**2. **运行问题**3. **数据问题** 项目实战建议项目参考文献项目概述 COLMAP 是一个开源的三维重建软件，专注于 Structure-from…...

编程日记 2025/8/7 23:26:28

基于Fabric.js的选座布局系统开发笔记

项目概述最近开发了一个简单的选座布局系统，主要用于会议、活动或餐厅等场景的座位和桌子布局设计。系统基于HTML5 Canvas和Fabric.js库实现，支持添加座位、桌子，并能保存布局数据。技术栈 • HTML5 Canvas：作为绘图的基础 •…...

编程日记 2025/8/8 1:21:16

PHP怎样连接MySQL数据库？

方法一：使用 mysqli 扩展 mysqli 是 MySQL 的改进版扩展，提供了面向对象和过程化的接口。面向对象风格 <?php$servername "localhost"; $username "your_username"; $password "your_password"; $dbname &quo…...

编程日记 2025/8/5 1:33:53

将飞帆制作的网页作为 Vue 2 组件引入到自己网页中使用

飞帆平台有一个功能：不仅所有的网页都是通过控件搭建而成，而且生成的网页又是一个大控件，可以导入到你自己的网页使用。这篇文章，我们要讲的就是如何将飞帆生成的网页作为控件（组件）导入到自己的网页中。…...

编程日记 2025/7/30 15:25:03

Python制作简易PDF查看工具PDFViewerV1.0显示优化

原文说明为不破坏原文结构，因此功能优化不在原文中维护了。关于这款工具原文请通过下面链接访问。Python制作简易PDF查看工具PDFViewerV1.0 这款小工具基本功能已经可以作为一款文档浏览器使用，但还有一些美中不足的地方，本文将介绍对文本查找功能的优化调整。优化效果 …...

编程日记 2025/8/7 11:49:16

YOLOv11改进有效涨点专栏：从理论到实战的深度优化指南

## YOLOv11的进化之路在目标检测领域，YOLO系列算法始终保持着革命性的创新步伐。YOLOv11作为该系列的最新演进版本，在保持实时检测优势的同时，通过架构层面的深度优化实现了精度与速度的平衡。本文将从**七大核心模块**出发，系统性地解析针对YOLOv11的有效改进方案，涵盖从…...

编程日记 2025/8/5 8:37:21

【EDA软件】【设计约束和分析操作方法】

1. 设计约束设计约束主要分为物理约束和时序约束。物理约束主要包括I/O接口约束（如引脚分配、电平标准设定等物理属性的约束）、布局约束、布线约束以及配置约束。时序约束是FPGA内部的各种逻辑或走线的延时，反应系统的频率和速度的约束…...

编程日记 2025/8/4 10:38:28

JVM基础认知：JVM到底是什么？为什么它如此重要？

随着 Java 语言在企业级应用、互联网服务、嵌入式系统等领域的广泛采用，JVM（Java Virtual Machine，Java虚拟机）成为了支撑整个生态的核心基础。初学者往往会把注意力集中在 Java 代码本身，却忽视了背后那台“看不见的机…...

编程日记 2025/8/9 18:02:51

javassist

使用javassist获取参数名 1，添加依赖需要在pom.xml文件中添加下面的依赖： <dependency><groupId>org.javassist</groupId><artifactId>javassist</artifactId><version>3.28.0-GA</version> </depende…...

编程日记 2025/8/2 23:10:16

【C++算法】66.栈_比较含退格的字符串

文章目录题目链接：题目描述：解法C 算法代码： 题目链接： 844. 比较含退格的字符串题目描述： 解法用字符串来模拟栈。 C 算法代码： class Solution { public:bool backspaceCompare(string s, string t…...

编程日记 2025/8/10 1:41:13

游戏引擎学习第235天:在 Windows 上初始化 OpenGL

奇怪有问题之前没注意到这个问题是Count 0 GlobalConstants_Renderer_UsedDebugCamer 打开的话会有Bug Count是零的话就不让排序了 game.h: 查阅 TODO 列表大家好，欢迎来到 game Hero，这是一档我们在直播中一起编写完整游戏的节目。不幸的是&a…...

编程日记 2025/8/7 11:42:26

FPGA系列之DDS信号发生器设计（DE2-115开发板）

一、IP核 IP(Intellectual Property)原指知识产权、著作权等，在IC设计领域通常被理解为实现某种功能的设计。IP模块则是完成某种比较复杂算法或功能（如FIR滤波器、FFT、SDRAM控制器、PCIe接口、CPU核等）并且参数可修改的电路模块&#xff0c…...

编程日记 2025/8/4 1:42:16

修改Theme SHELL美化panel

安装使用使用Tweaks进行设置需要创建.themes文件夹，在当前目录下 mkdir ~/.themes从官网下载文件 https://www.gnome-look.org/p/1013030 将打包压缩文件移动到~/themes，并解压 tar -xvf 01-Flat-Remix-Light-20250413.tar.xz然后使用按 Alt F2…...

编程日记 2025/8/8 4:23:58

Sentinel源码—5.FlowSlot借鉴Guava的限流算法二

大纲 1.Guava提供的RateLimiter限流使用示例 2.Guava提供的RateLimiter简介与设计 3.继承RateLimiter的SmoothBursty源码 4.继承RateLimiter的SmoothWarmingUp源码 3.继承RateLimiter的SmoothBursty源码 (1)SmoothBursty的初始化流程 (2)SmoothBursty的初始化完成后的变量…...

编程日记 2025/7/30 15:24:40

自由学习记录（56）

从贴图空间（texture space）将值还原到切线空间（tangent space）向量 tangentNormal.xy (packedNormal.xy * 2 - 1) * _BumpScale; 背后的知识点：法线贴图中的 RGB 是在 0~1 范围内编码的向量所以贴图法线是怎么“压…...

编程日记 2025/7/30 15:24:38

计算机网络八股——HTTP协议与HTTPS协议

前言： 到时候我想要写一篇文章就是：在浏览器中输入URL并按下回车会发生什么？ 然后将几篇文章全部串联到一起，现在几天的任务就是将这里的每个小部分进行一个详细的介绍 HTTP1.1简述与特性 Web 上的通信都是建⽴在 HTTP 协议上的…...

编程日记 2025/8/4 1:16:46

JAVAEE(网络原理—UDP报头结构）

我们本篇文章要讲的是UDP的报头结构以及注意事项。下面呢，我先说一下UDP是什么？ 1.UDP是什么？ UDP是一种网络协议。网络协议是计算机网络中，为了使不同设备之间能够准确、高效地进行数据交换和通信，而预先制定的一…...

编程日记 2025/8/5 12:28:57

Redis-分布式锁

Redis-分布式锁文章目录 Redis-分布式锁1.基本原理和不同方式实现方式对比2.Redis分布式锁的基本实现思路3.分布式锁误删问题一4.分布式锁误删问题二5.Redission1.功能介绍2.快速入门3.可重入锁原理4.锁重试和WatchDog机制1.锁重试2. WatchDog 机制（锁自动续期&…...

编程日记 2025/8/10 1:36:07

如何优雅地为 Axios 配置失败重试与最大尝试次数

在 Vue 3 中，除了使用自定义的 useRequest 钩子函数外，还可以通过 axios 的拦截器或 axios-retry 插件实现接口请求失败后的重试逻辑。以下是两种具体方案的实现方式： 方案一：使用 axios 拦截器实现重试实现步骤： 通…...

编程日记 2025/8/8 7:22:47

Windows使用SonarQube时启动脚本自动关闭

一、解决的问题 Windows使用SonarQube时启动脚本自动关闭，并发生报错： ERROR: Elasticsearch did not exit normally - check the logs at E:\Inori_Code\Year3\SE\sonarqube-25.2.0.102705\sonarqube-25.2.0.102705\logs\sonarqube.log ERROR: Elastic…...

编程日记 2025/8/5 19:14:21

MYSQL初阶（暂为自用草稿）

目录基本操作 database操作 table操作数据类型 INT类型 bit类型 FLOAT类型 CHAR类型 DATE类型 SEL类型表的约束列约束 NULL DEFAULT PRIMARY KEY UNIQUE KEY 表约束 PRIMARY KEY FOREIGN KEY 其他补充 AUTO_INCREMENT COMMENT ZEROFILL 表的CRUD …...

编程日记 2025/8/8 18:18:52

交换排序——快速排序

交换排序的基本思路：把序列中的两个元素进行比较，根据需求对两个元素进行交换。特点是较大的元素向序列的尾部移动，较小的元素向序列的前部移动。 hoare法在序列中任取一个元素作为基准值，一趟排序完成之后，以基准值为…...

编程日记 2025/8/9 15:59:27

资源-又在网上淘到金了

前言： 本期再分享网上冲浪发现的特效/动画/视频资源网站。一、基本介绍： mantissa.xyz，about作者介绍为：Midge “Mantissa” Sinnaeve （米奇辛纳夫）是一位屡获殊荣的艺术家和导演，提供动画、…...

编程日记 2025/8/5 1:33:42

CSS中的`transform-style`属性：3D变换的秘密武器

在CSS中，当我们尝试创建复杂的3D场景时，transform-style属性变得尤为重要。它决定了子元素是在3D空间中呈现还是被展平到2D平面中。本文将深入探讨transform-style的用法，并通过具体的代码示例来展示如何利用这个属性来增强你的网页设计。什…...

编程日记 2025/8/5 4:34:43

Step文件无法编辑怎么办？

Step文件无法编辑怎么办？ 这里介绍两种方法， 1、直接导入准备step文件，solidworks导入后是这样，不能在上面直接编辑图 1 点击右键，选择解除特征（不同版本的可能不太一样，这里是solidworks2…...

编程日记 2025/8/6 2:14:47

从 LabelImg 到 Label Studio！AI 数据标注神器升级，Web 版真香

视频讲解： 从 LabelImg 到 Label Studio！AI 数据标注神器升级，Web 版真香 Label Studio 支持图像、文本、音频、视频、时间序列等多类型数据标注，覆盖计算机视觉（目标检测、语义分割）、自然语言处理&#x…...

编程日记 2025/8/9 16:56:14

纯FPGA实现驱动AD9361配置的思路和实现之一概述

我们在做ZYNQ系统开发时候做的IP基本都是AXI_LITE_SLAVE，是SLAVE，从设备。就是提供了若干寄存器接口供MASTER进行读写。SLAVE里面的逻辑通过读写动作或者读写的数据进行响应的动作。这种方式的好处是硬件层面可以访问寄存器，软件层面是可以实…...

编程日记 2025/8/7 20:06:07

Nacos配置中心服务端源码解析

文章目录概述一、配置持久化到数据库二、发布事件2.1、事件发布者端2.1.1、DefaultPublisher#publish2.1.2、DefaultPublisher#run2.1.3、DefaultPublisher#receiveEvent 2.2、事件订阅者端2.2.1、Subscriber#onEvent2.2.2、ConfigCacheService#dump 总结：Nacos 配…...

编程日记 2025/8/5 14:25:59