排序算法之--插入排序

文章目录

    • 一、简介
    • 二、算法思路分析
    • 三、算法复杂度分析:
      • 3.1、时间复杂度方面:
      • 3.2、空间复杂度方面:
    • 四、代码实现:

一、简介

        插入排序是一种简单直观的排序算法,‌它的工作原理是通过构建有序序列,‌该算法适用于少量数据的排序。‌在插入排序中,‌每一个元素都会插入到已经排序的序列中,‌通过比较和移动元素来达到排序的目的。‌

二、算法思路分析

        插入排序的关键在于:要理解何为插入,现有一随机数组arr = [4,7,5,3,6],对其进行排序。首先忘掉这是一个数组,扑克牌大家都玩过吧,以扑克牌举例,假设扑克牌的排序从左至右依次变大
第一手: 取到:4,手中就一张牌,结束
第二手: 取到:7,当前手中牌:【4】,对比: 4 < 7 直接4右边,结束
第三手: 取到:5,当前手中牌:【4、7】,对比: 7 > 5,7向右移动一位,给左边留个插牌的位 置,再对比:4 < 5,插到4的右一位。
在这里插入图片描述

第四手: 取到:3,当前手中牌:【4、5、7】,对比:7 > 3,7向右移动一位,给左边留个插牌的位置,再对比:5 》3,5向右移一位(7后移留下的位置),给左边留个插牌的位置,再对比:4>3,4向右移一位,4左边没牌了那就放在最左边。
在这里插入图片描述

第五手: 取到:6,当前手中牌【3、4、5、7】,对比:7 》6, 7向右移动一位,给左边留个插牌的位置,再对比:5 < 6,插到5的右一位。
至此手中的扑克牌变成【3、4、5、6、7】

在这里插入图片描述

三、算法复杂度分析:

3.1、时间复杂度方面:

        最好情况时间复杂度:‌当待排序序列已经是有序时,‌每次插入一个元素只需要进行一次比较即可确定其位置,‌因此最好情况下的时间复杂度为O(n)。‌
        最坏情况时间复杂度:‌当待排序序列是逆序的,‌即每个元素都比前一个元素大,‌这时每次插入一个元素需要进行多次比较才能找到正确的位置,‌最坏情况下的时间复杂度为O(n^2)。‌
        平均情况时间复杂度:‌由于插入排序在最好和最坏情况下的时间复杂度分别对应于序列已有序和序列完全逆序的情况,‌因此在实际应用中,‌其平均时间复杂度也是O(n^2)。‌

3.2、空间复杂度方面:

        插入排序是一种就地排序算法,‌它不需要额外的存储空间来排序数据,‌因此其空间复杂度为O(1)。‌这意味着它在处理数据时不会占用额外的存储空间,‌非常适合处理数据量较小的情况。‌

四、代码实现:

    public static void insertSort(int[] pokerArr) {for ( int i = 1; i < pokerArr.length; i++ ) {//当前取到的牌int newPoker = pokerArr[i];int j = i - 1;//与手中牌对比,确定插入位置while ( j > 0 && pokerArr[j] > newPoker ) {//手中第j张牌 > 当前取的牌 当第j张牌右移一位pokerArr[j + 1] = pokerArr[j];//再对比左边的牌,直到左边无牌、或者左边牌 < 当前取的牌,结束j--;}//将牌插入最终位置pokerArr[j+1] = newPoker;}}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/399257.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

水表数字识别4:C/C++实现水表数字识别(含源码 可实时检测)

水表数字识别4&#xff1a;C/C实现水表数字识别(含源码 可实时检测) 目录 水表数字识别4&#xff1a;C/C实现水表数字识别(含源码 可实时检测) 1. 前言 2. 水表数字分割模型 &#xff08;1&#xff09; 将Pytorch模型转换ONNX模型 &#xff08;2&#xff09; 将ONNX模型转…

NoSQL 之Redis集群模式

目录 案例概述 redis工作模式 主从模式 哨兵模式 redis cluster模式 Redis集群介绍 Redis集群的优势 Redis集群的实现方法 Redis-Cluster数据分片 Redis-Cluster的主从复制模型 Redis集群部署 案例部署 安装redis 检查redis的状态 修改配置文件 重启启动redis服…

C#小桌面程序调试出错,如何解决??

&#x1f3c6;本文收录于《CSDN问答解惑-专业版》专栏&#xff0c;主要记录项目实战过程中的Bug之前因后果及提供真实有效的解决方案&#xff0c;希望能够助你一臂之力&#xff0c;帮你早日登顶实现财富自由&#x1f680;&#xff1b;同时&#xff0c;欢迎大家关注&&收…

pythonUI自动化007::pytest的组成以及运行

pytest组成&#xff1a; 测试模块&#xff1a;以“test”开头或结尾的py文件 测试用例&#xff1a;在测试模块里或测试类里&#xff0c;名称符合test_xxx函数或者示例函数。 测试类&#xff1a;测试模块里面命名符合Test_xxx的类 函数级&#xff1a; import pytestclass Test…

大数据面试SQL(七):累加刚好超过各省GDP40%的地市名称

文章目录 累加刚好超过各省GDP40%的地市名称 一、题目 二、分析 三、SQL实战 四、样例数据参考 累加刚好超过各省GDP40%的地市名称 一、题目 现有各省地级市的gdp数据,求从高到低累加刚好超过各省GDP40%的地市名称&#xff0c;临界地市也需要。 例如&#xff1a; 浙江省…

物理网卡MAC修改器v3.0-直接修改网卡内部硬件MAC地址,重装系统不变!

直接在操作系统里就能修改网卡硬件mac地址&#xff0c;刷新网卡mac序列号硬件码机器码&#xff0c;电脑主板集成网卡&#xff0c;pcie网卡&#xff0c;usb有线网卡&#xff0c;usb无线网卡&#xff0c;英特尔网卡&#xff0c;瑞昱网卡全支持&#xff01; 一键修改mac&#xff0…

求1000以内的水仙花数【C语言】

求1000以内的水仙花数 #include <stdio.h> //包含标准输入输出头文件&#xff0c;用于使用printf函数int main() { //程序的主函数开始int a, b, c, i; //i用于循环遍历100到999之间的所有数&#xff08;三位数&#xff09;&#xff0c;a, b, c分别用于存储当前数i的百位…

SPSS 数据分析,掌握这 6 大模块就够

SPSS 全称为「社会科学统计软件包」&#xff0c;是 IBM 公司推出的一系列用于统计学分析运算、数据挖掘、预测分析和决策支持任务的软件产品及相关服务的总称。 图中我们看到 SPSS 有 23 个方法模块&#xff0c;虽然我们不能每个模块都能用到&#xff0c;但作为一个科研工作者…

C++-类与对象(上篇)

一、目标&#xff1a; 1. 面向过程和面向对象初步认识 2. 类的引入 3. 类的定义 4. 类的访问限定符及封装 5. 类的作用域 6. 类的实例化 7. 类的对象大小的计算 8. 类成员函数的 this 指针 二、对类与对象的介绍&#xff1a; 1.面向过程和面向对象初步认识 &#xff1a…

前端代码编辑神器:sublime text 4(WinMac)中文注册版

Sublime Text 4 是一款广受欢迎的文本和代码编辑器&#xff0c;由程序员 Jon Skinner 于2008年开发。这款编辑器以其漂亮的用户界面和强大的功能而著称&#xff0c;适用于多种编程语言的开发。 主要特点&#xff1a; 用户界面&#xff1a;Sublime Text 4 拥有一个简洁且美观的…

旧手机拍摄的视频模糊可以修复清晰吗?

你是否时常“考古”一些老电影、老动漫来回忆旧日时光&#xff1f;你是否也有一些珍贵的录像&#xff0c;带你重温过去的美好&#xff1f;然而&#xff0c;我们已经习惯了高清体验&#xff0c;回头再看曾经的旧影像&#xff0c;画质或许“渣”的让人不忍直视。 旧手机像素不好&…

[VBA]使用VBA在Excel中 操作 形状shape 对象

excel已关闭地图插件,对于想做 地图可视化 的,用形状来操作是一种办法,就是要自行找到合适的 地图形状,修改形状颜色等就可以用于 可视化展示不同省市销量、人口等数据。 引言 在Excel中,通过VBA(Visual Basic for Applications)可以极大地增强数据可视化和报告自动化…

【ARM CoreLink 系列 5.5 -- CI-700 Debug trace and PMU 】

文章目录 Debug trace and PMUCI-700 Debug trace 系统概述DTC DomainDTC Domain 约束条件DTM device portsDTM FIFO BufferDTM FIFO 缓冲区特点Debug trace and PMU 本篇文章主要是介绍 CI-700中实现的 Debug Trace (DT) and Performance Monitoring Unit (PMU). CI-700 Deb…

运维高级内容--lvs按权重值轮询调度

创建5台主机(一些配置是基于实验一的基础)&#xff1a; 客户端client 172.25.254.200路由器route 172.25.254.100 192.168.0.100 &#xff08;需要eth0、eth1两个网关&#xff09;LVS 192.168.0.50webserver1 192.168.0.10webserver2 192.168.0.20 1.LVS主机&#xff1a; vim…

pytorch多GPU训练简明教程

1. Torch 的两种并行化模型封装 1.1 DataParallel DataParallel 是 PyTorch 提供的一种数据并行方法&#xff0c;用于在单台机器上的多个 GPU 上进行模型训练。它通过将输入数据划分成多个子部分&#xff08;mini-batches&#xff09;&#xff0c;并将这些子部分分配给不同的 G…

python爬取B站视频实验

实验17&#xff1a;爬虫2 文章目录 实验17&#xff1a;爬虫21.实验目标及要求2. 实验主要内容3.实验小结 1.实验目标及要求 &#xff08;1&#xff09;掌握有关爬虫的包 &#xff08;2&#xff09;掌握爬虫方法 &#xff08;3&#xff09;爬取B站卡塔尔世界杯若干视频 2. 实验…

day09——集合ArrayList

ArrayList类 ArrayList表示一种集合&#xff0c;它是一个容器&#xff0c;用来存储数据的&#xff0c;类似于数组。但不同于数组&#xff0c;数组一旦创建大小不变&#xff0c;而集合大小是可变的。 ArrayList常用方法 ArrayList是泛型类&#xff0c;可以约束存储的数据类型…

MapReduce入门教程

这可不是目录 入门定义与说明数据分析Map和Reduce阶段的任务<Kn,Vn>分析MapReduce的数据类型其他说明(持续更新) 开发案例(持续更新)自定义的wordcountcsv文件操作序列化操作 入门 定义与说明 数据分析 以下未数据分析示意图 Map和Reduce阶段的任务 Map阶段的任务&a…

AVL树模拟实现

目录 前言 什么叫平衡呢&#xff1f; 平衡因子 代码实现 基础结构 函数部分 构造部分 Insert函数 旋转情况(敲重点&#xff01;&#xff01;&#xff01;~\(≧▽≦)/~) 1、右右情况 ——— 左单旋 左旋总步骤 拆解 为什么叫左旋呢&#xff1f; 代码 2、左左情况 …

考研概率论如何复习最高效?能拿满分

概率论跟哪写老师的课程&#xff1f; 推荐三个老师&#xff1a; 喻老&#xff1a;基础讲的很好 喻老的线性代数课在今年已经非常有名&#xff0c;但其实他讲授的概率论课程同样十分出色。喻老的课程特点在于讲解非常细致&#xff0c;特别适合基础较为薄弱的学生。此外&#…