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

插入排序:简单而有效的排序方法

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

insertionSort1.jpg

插入排序的原理及性能分析

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

insertionSort.png

插入排序的步骤

插入排序的步骤可以简单概括为以下几个阶段:

  1. 初始状态: 将数组的第一个元素视为已排序部分,其余部分为未排序部分。

  2. 逐个插入: 从未排序部分选择一个元素,将其插入到已排序部分的正确位置。为了插入,将已排序部分中大于待插入元素的元素向右移动一个位置。

  3. 重复: 重复上述插入步骤,直到所有元素都被插入到已排序部分。

  4. 完成: 当算法完成时,整个数组就被排序了。

insertionSort3ed1ad8f9c96f9d8.png

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),因为它只需要常量级别的额外空间来存储临时变量。

  • 稳定性

插入排序是一种稳定的排序算法,即具有相等键值的元素在排序后仍然保持相对顺序。

  • 适用性

插入排序适用于小型数据集或已接近排序状态的数据集。对于大型数据集,插入排序的性能会变得相对较差,并且不如一些更高级的排序算法,如快速排序或归并排序。

  • 优点

插入排序的优点是实现简单,易于理解和调试。在某些情况下,它可能比其他排序算法更快,尤其是对于小型数据集。

  • 缺点

插入排序的缺点是其时间复杂度较高,特别是在大型数据集上。对于大规模数据,更高效的排序算法通常更受欢迎。

总结

总的来说,插入排序是一种简单但性能较差的排序算法,主要用于教学和小型数据集。在实际应用中,通常会选择更高效的排序算法,以提高排序速度。

相关文章:

插入排序:简单而有效的排序方法

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

OpenGL之光照贴图

我们需要拓展之前的系统,引入漫反射和镜面光贴图(Map)。这允许我们对物体的漫反射分量和镜面光分量有着更精确的控制。 漫反射贴图 我们希望通过某种方式对物体的每个片段单独设置漫反射颜色。我们仅仅是对同样的原理使用了不同的名字:其实都是使用一张覆盖物体的图像,让我…...

隐私交易成新刚需,Unijoin 凭什么优势杀出重围?

随着区块链技术的普及和发展&#xff0c;全球加密货币用户在持续增长&#xff0c;根据火币研究院公布的数据&#xff0c;2022年全球加密用户已达到 3.2亿人&#xff0c;目前全球人口总数超过了 80亿&#xff0c;加密货币用户渗透率已达到了 4%。 尤其是在 2020 年开启的 DeFi 牛…...

小谈设计模式(12)—迪米特法则

小谈设计模式&#xff08;12&#xff09;—迪米特法则 专栏介绍专栏地址专栏介绍 迪米特法则核心思想这里的“朋友”指当前对象本身以参数形式传入当前对象的对象当前对象的成员变量直接引用的对象目标 Java程序实现程序分析 总结 专栏介绍 专栏地址 link 专栏介绍 主要对目…...

Foxit PDF

Foxit PDF 福昕PDF 软件&#xff0c;可以很好的编辑PDF文档。 调整&#xff30;&#xff24;&#xff26;页面大小 PDF文档中&#xff0c;一个页面大&#xff0c;一个页面小 面对这种情况,打开Foxit PDF 右键单击需要调整的页面,然后选择"调整页面大小". 可以选择…...

《Python趣味工具》——ppt的操作(刷题版)

前面我们对PPT进行了一定的操作&#xff0c;并将其中的文字提取到了word文档中。现在就让我们来刷几道题巩固巩固吧&#xff01; 文章目录 1. 查看PPT&#xff08;上&#xff09;2. 查看PPT&#xff08;中&#xff09;3. 查看PPT&#xff08;下&#xff09;4. PPT的页码5. 大学…...

实战型开发--3/3,clean code

编程的纯粹 hmmm&#xff0c;一开始在这个环节想聊一些具体的点&#xff0c;其实也就是《clean code》这本书中的点&#xff0c;但这个就还是更流于表面&#xff1b; 因为编码的过程&#xff0c;就更接近于运动员打球&#xff0c;艺术家绘画&#xff0c;棋手下棋的过程&#x…...

家用无线路由器如何用网线桥接解决有些房间无线信号覆盖不好的问题(低成本)

环境 光猫ZXHN F677V9 水星MW325R 无线百兆路由器 100M宽带&#xff0c;2.4G无线网络 苹果手机 安卓平板电脑 三室一厅94平 问题描述 家用无线路由器如何用网线桥接解决有些房间无线信号不好问题低成本解决&#xff0c;无线覆盖和漫游 主路由器用的运营商的光猫自带无…...

【Golang】网络编程

网络编程 网络模型介绍 OSI七层网络模型 在软件开发中我们使用最多的是上图中将互联网划分为五个分层的模型&#xff1a; 物理层数据链路层网络层传输层应用层 物理层 我们的电脑要与外界互联网通信&#xff0c;需要先把电脑连接网络&#xff0c;我们可以用双绞线、光纤、…...

使用策略模式优化多重if/else

一、为什么需要策略模式&#xff1f; 作为前端程序员&#xff0c;我们经常会遇到这样的场景&#xff0c;例如 进入一个营销活动页面&#xff0c;会根据后端下发的不同 type &#xff0c;前端页面展示不同的弹窗。 async getMainData() {try {const res await activityQuery()…...

逆强化学习

1.逆强化学习的理论框架 1.teacher的行为被定义成best 2.学习的网络有两个&#xff0c;actor和reward 3.每次迭代中通过比较actor与teacher的行为来更新reward function&#xff0c;基于新的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.注解解析 注解解析就是判断类上、方法上、成员变量上是否存在注解&#xff0c;并把注解里的内容给解析出来 2.如何解析注解&#xff1f; 思想&#xff1a;要解析谁上面的注解&#xff0c;就应该先拿到谁&#xff08;通过反射&#xff09;如果要解析类…...

mysql面试题14:讲一讲MySQL中什么是全同步复制?底层实现?

该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:讲一讲mysql中什么是全同步复制?底层实现? MySQL中的全同步复制(Synchronous Replication)是一种复制模式,主服务器在写操作完成后,必须等待…...

Linux驱动设备号分配与自动创建设备节点

Linux 驱动设备号 对于 Linux 系统&#xff0c;为了识别和管理设备&#xff0c;每个设备便使用一个唯一的编号来标记设备&#xff0c;每个注册到内核的设备都需要一个编号&#xff0c;这个编号就是设备号&#xff0c;为了细分设备号分为主设备号和次设备号。 由于 Linux 的设…...

基于MFC和OpenCV实现人脸识别

基于MFC和OpenCV实现人脸识别 文章目录 基于MFC和OpenCV实现人脸识别1. 项目说明1. 创建项目2. 启动窗口3. 登录窗口-添加窗口、从启动窗口跳转4. 启动窗口-美化按钮5. 登录窗口-美化按钮、雪花视频6. 注册窗口-美化按钮、雪花视频、从启动窗口跳转7. 注册窗口-开启摄像头8. 注…...

力扣 -- 377. 组合总和 Ⅳ

解题步骤&#xff1a; 参考代码&#xff1a; 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(…...

阿里云新账户什么意思?老用户、产品首购详细说明

阿里云新账户、老账号、产品首购和同人账号什么意思&#xff1f;阿里云账号分为云新账户、老账户、产品首购、同人账号和同一用户&#xff0c;阿里云官方推出的活动很多是限制账号类型的&#xff0c;常见的如阿里云新用户&#xff0c;什么是阿里云新用户&#xff1f;是指从未在…...

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&#xff1a; {% load static %} <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Title</title><link rel"stylesheet" href"{% static plugins…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

【堆垛策略】设计方法

堆垛策略的设计是积木堆叠系统的核心&#xff0c;直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法&#xff0c;涵盖基础规则、优化算法和容错机制&#xff1a; 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则&#xff1a; 大尺寸/重量积木在下&#xf…...

嵌入式学习之系统编程(九)OSI模型、TCP/IP模型、UDP协议网络相关编程(6.3)

目录 一、网络编程--OSI模型 二、网络编程--TCP/IP模型 三、网络接口 四、UDP网络相关编程及主要函数 ​编辑​编辑 UDP的特征 socke函数 bind函数 recvfrom函数&#xff08;接收函数&#xff09; sendto函数&#xff08;发送函数&#xff09; 五、网络编程之 UDP 用…...

6.9-QT模拟计算器

源码: 头文件: widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QMouseEvent>QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic:Widget(QWidget *parent nullptr);…...