插入排序:简单而有效的排序方法
在计算机科学中,排序算法是一个重要且常见的主题,它们用于对数据进行有序排列。插入排序(Insertion Sort)是其中一个简单但有效的排序算法。本文将详细解释插入排序的原理和步骤,并提供Java语言的实现示例。

插入排序的原理及性能分析
插入排序的核心思想是逐个将未排序的元素插入到已排序的部分中,构建有序序列。这个过程类似于整理扑克牌,每次拿出一张牌并将其插入到已排序的牌堆中。

插入排序的步骤
插入排序的步骤可以简单概括为以下几个阶段:
-
初始状态: 将数组的第一个元素视为已排序部分,其余部分为未排序部分。
-
逐个插入: 从未排序部分选择一个元素,将其插入到已排序部分的正确位置。为了插入,将已排序部分中大于待插入元素的元素向右移动一个位置。
-
重复: 重复上述插入步骤,直到所有元素都被插入到已排序部分。
-
完成: 当算法完成时,整个数组就被排序了。

Java实现插入排序
以下是使用Java语言实现插入排序算法的示例代码:
public class Test {public static void main(String[] args) {int[] arr = new int[]{5,2,4,6,7,1,3};insertionSort(arr);}public static void insertionSort(int[] arr){System.out.println("原始数组:"+ Arrays.toString(arr));//获取数组长度int len = arr.length;// 循环 len-1 次,进行数组排序。第一次将数组的第一个元素视为已排序的部分,// 每次将未排序部分的第一个元素插入到已排序的部分。for(int i = 1 ; i< len ; i++){//目标元素,未排序部分的第一个元素,即当前循环中要插入排序的元素int target = arr[i];//已排序元素中的最后一个元素的下标int j = i-1;// 循环已排序的部分的数组,找到目标元素应该存放的下标while (j>= 0 && arr[j] > target ){// 如果插入元素小于当前元素,则将当前元素后移一位arr[j+1] = arr[j];// 当前已排序的数据比较元素的下标前移一位j--;}//将目标元素插入到正确的位置arr[j+1] = target;// 打印每趟排序完成后的数组状态,以便查看排序进度System.out.println("第"+i+"趟排序完成的数组:"+ Arrays.toString(arr));}System.out.println("排序完成的数组:"+ Arrays.toString(arr));}
}
以上代码演示了如何使用插入排序对一个整数数组进行排序。插入排序算法的核心思想是逐个将未排序的元素插入到已排序的部分,直到整个数组排序完成。
性能及优缺点的分析
插入排序(Insertion Sort)是一种简单但性能较差的排序算法,其性能取决于输入数据的初始顺序。以下是对插入排序性能的分析:
- 时间复杂度
在最坏情况下,插入排序的时间复杂度为 O ( n 2 ) O(n^2) O(n2),其中n是数组的长度。这是因为在最坏情况下,每个元素都需要与已排序部分中的所有元素进行比较和移动。在最好情况下,如果输入数据已经接近有序,插入排序的时间复杂度可以降至O(n),因为很少需要移动元素。
- 空间复杂度
插入排序是一种稳定排序算法,其空间复杂度为O(1),因为它只需要常量级别的额外空间来存储临时变量。
- 稳定性
插入排序是一种稳定的排序算法,即具有相等键值的元素在排序后仍然保持相对顺序。
- 适用性
插入排序适用于小型数据集或已接近排序状态的数据集。对于大型数据集,插入排序的性能会变得相对较差,并且不如一些更高级的排序算法,如快速排序或归并排序。
- 优点
插入排序的优点是实现简单,易于理解和调试。在某些情况下,它可能比其他排序算法更快,尤其是对于小型数据集。
- 缺点
插入排序的缺点是其时间复杂度较高,特别是在大型数据集上。对于大规模数据,更高效的排序算法通常更受欢迎。
总结
总的来说,插入排序是一种简单但性能较差的排序算法,主要用于教学和小型数据集。在实际应用中,通常会选择更高效的排序算法,以提高排序速度。
相关文章:
插入排序:简单而有效的排序方法
在计算机科学中,排序算法是一个重要且常见的主题,它们用于对数据进行有序排列。插入排序(Insertion Sort)是其中一个简单但有效的排序算法。本文将详细解释插入排序的原理和步骤,并提供Java语言的实现示例。 插入排序的…...
OpenGL之光照贴图
我们需要拓展之前的系统,引入漫反射和镜面光贴图(Map)。这允许我们对物体的漫反射分量和镜面光分量有着更精确的控制。 漫反射贴图 我们希望通过某种方式对物体的每个片段单独设置漫反射颜色。我们仅仅是对同样的原理使用了不同的名字:其实都是使用一张覆盖物体的图像,让我…...
隐私交易成新刚需,Unijoin 凭什么优势杀出重围?
随着区块链技术的普及和发展,全球加密货币用户在持续增长,根据火币研究院公布的数据,2022年全球加密用户已达到 3.2亿人,目前全球人口总数超过了 80亿,加密货币用户渗透率已达到了 4%。 尤其是在 2020 年开启的 DeFi 牛…...
小谈设计模式(12)—迪米特法则
小谈设计模式(12)—迪米特法则 专栏介绍专栏地址专栏介绍 迪米特法则核心思想这里的“朋友”指当前对象本身以参数形式传入当前对象的对象当前对象的成员变量直接引用的对象目标 Java程序实现程序分析 总结 专栏介绍 专栏地址 link 专栏介绍 主要对目…...
Foxit PDF
Foxit PDF 福昕PDF 软件,可以很好的编辑PDF文档。 调整PDF页面大小 PDF文档中,一个页面大,一个页面小 面对这种情况,打开Foxit PDF 右键单击需要调整的页面,然后选择"调整页面大小". 可以选择…...
《Python趣味工具》——ppt的操作(刷题版)
前面我们对PPT进行了一定的操作,并将其中的文字提取到了word文档中。现在就让我们来刷几道题巩固巩固吧! 文章目录 1. 查看PPT(上)2. 查看PPT(中)3. 查看PPT(下)4. PPT的页码5. 大学…...
实战型开发--3/3,clean code
编程的纯粹 hmmm,一开始在这个环节想聊一些具体的点,其实也就是《clean code》这本书中的点,但这个就还是更流于表面; 因为编码的过程,就更接近于运动员打球,艺术家绘画,棋手下棋的过程&#x…...
家用无线路由器如何用网线桥接解决有些房间无线信号覆盖不好的问题(低成本)
环境 光猫ZXHN F677V9 水星MW325R 无线百兆路由器 100M宽带,2.4G无线网络 苹果手机 安卓平板电脑 三室一厅94平 问题描述 家用无线路由器如何用网线桥接解决有些房间无线信号不好问题低成本解决,无线覆盖和漫游 主路由器用的运营商的光猫自带无…...
【Golang】网络编程
网络编程 网络模型介绍 OSI七层网络模型 在软件开发中我们使用最多的是上图中将互联网划分为五个分层的模型: 物理层数据链路层网络层传输层应用层 物理层 我们的电脑要与外界互联网通信,需要先把电脑连接网络,我们可以用双绞线、光纤、…...
使用策略模式优化多重if/else
一、为什么需要策略模式? 作为前端程序员,我们经常会遇到这样的场景,例如 进入一个营销活动页面,会根据后端下发的不同 type ,前端页面展示不同的弹窗。 async getMainData() {try {const res await activityQuery()…...
逆强化学习
1.逆强化学习的理论框架 1.teacher的行为被定义成best 2.学习的网络有两个,actor和reward 3.每次迭代中通过比较actor与teacher的行为来更新reward function,基于新的reward function来更新actor使得actor获得的reward最大。 loss的设计相当于一个排序问…...
postgresql新特性之Merge
postgresql新特性之Merge 创建测试表测试案例 创建测试表 create table cps.public.test(id integer primary key,balance numeric,status varchar(1));测试案例 官网介绍 merge into test t using ( select 1 id,0 balance,Y status) s on(t.id s.id) -- 当匹配上了,statu…...
【注解】注解解析与应用场景
注解解析与应用场景 1.注解解析 注解解析就是判断类上、方法上、成员变量上是否存在注解,并把注解里的内容给解析出来 2.如何解析注解? 思想:要解析谁上面的注解,就应该先拿到谁(通过反射)如果要解析类…...
mysql面试题14:讲一讲MySQL中什么是全同步复制?底层实现?
该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:讲一讲mysql中什么是全同步复制?底层实现? MySQL中的全同步复制(Synchronous Replication)是一种复制模式,主服务器在写操作完成后,必须等待…...
Linux驱动设备号分配与自动创建设备节点
Linux 驱动设备号 对于 Linux 系统,为了识别和管理设备,每个设备便使用一个唯一的编号来标记设备,每个注册到内核的设备都需要一个编号,这个编号就是设备号,为了细分设备号分为主设备号和次设备号。 由于 Linux 的设…...
基于MFC和OpenCV实现人脸识别
基于MFC和OpenCV实现人脸识别 文章目录 基于MFC和OpenCV实现人脸识别1. 项目说明1. 创建项目2. 启动窗口3. 登录窗口-添加窗口、从启动窗口跳转4. 启动窗口-美化按钮5. 登录窗口-美化按钮、雪花视频6. 注册窗口-美化按钮、雪花视频、从启动窗口跳转7. 注册窗口-开启摄像头8. 注…...
力扣 -- 377. 组合总和 Ⅳ
解题步骤: 参考代码: class Solution { public:int combinationSum4(vector<int>& nums, int target) {int nnums.size();vector<double> dp(target1);//初始化dp[0]1;//填表for(int i1;i<target;i){for(int j0;j<n;j){//填表if(…...
阿里云新账户什么意思?老用户、产品首购详细说明
阿里云新账户、老账号、产品首购和同人账号什么意思?阿里云账号分为云新账户、老账户、产品首购、同人账号和同一用户,阿里云官方推出的活动很多是限制账号类型的,常见的如阿里云新用户,什么是阿里云新用户?是指从未在…...
C++ YAML使用
C++工程如何使用YAML-cpp 一、前期准备工作 1、已安装minGW、cmake、make等本地工具。 2、下载YAML-cpp第三方开源代码(一定要下载最新的release版本,不然坑很多)。 3、生成YAML-cpp静态库 (1)在yaml-cpp-master下建立build文件夹; (2)在该文件夹下生成MakaFile文…...
十二、Django之模板的继承+用户列表
模板的继承 新建layout.html: {% load static %} <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Title</title><link rel"stylesheet" href"{% static plugins…...
以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...
PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...
成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
