插入排序:简单而有效的排序方法
在计算机科学中,排序算法是一个重要且常见的主题,它们用于对数据进行有序排列。插入排序(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…...

UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storms…...

从物理机到云原生:全面解析计算虚拟化技术的演进与应用
前言:我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM(Java Virtual Machine)让"一次编写,到处运行"成为可能。这个软件层面的虚拟化让我着迷,但直到后来接触VMware和Doc…...

【Linux】Linux安装并配置RabbitMQ
目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的,需要先安…...

leetcode_69.x的平方根
题目如下 : 看到题 ,我们最原始的想法就是暴力解决: for(long long i 0;i<INT_MAX;i){if(i*ix){return i;}else if((i*i>x)&&((i-1)*(i-1)<x)){return i-1;}}我们直接开始遍历,我们是整数的平方根,所以我们分两…...

npm安装electron下载太慢,导致报错
npm安装electron下载太慢,导致报错 背景 想学习electron框架做个桌面应用,卡在了安装依赖(无语了)。。。一开始以为node版本或者npm版本太低问题,调整版本后还是报错。偶尔执行install命令后,可以开始下载…...

RocketMQ 客户端负载均衡机制详解及最佳实践
延伸阅读:🔍「RocketMQ 中文社区」 持续更新源码解析/最佳实践,提供 RocketMQ 专家 AI 答疑服务 前言 本文介绍 RocketMQ 负载均衡机制,主要涉及负载均衡发生的时机、客户端负载均衡对消费的影响(消息堆积/消费毛刺等…...