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

排序算法介绍(一)插入排序

0. 简介       

        插入排序(Insertion Sort) 是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用 in-place 排序(即只需用到 O(1) 的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。


1. 插入排序的实现

插入排序的基本思想:

  1. 从第一个元素开始,该元素可以认为已经被排序;
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  5. 将新元素插入到该位置后;
  6. 重复步骤2~5。

插入排序过程演示:

367e3c9d2d6d4004a720bba75ba79dab.gif


2. 插入排序时空间复杂度分析

插入排序的时间复杂度和空间复杂度如下:

  1. 时间复杂度:

    • 最坏情况(逆序):每次插入都需要移动元素,总共需要移动的次数较多,所以时间复杂度是 O(n^2)。
    • 最好情况(已排序):每次插入只需要比较一次,所以时间复杂度是 O(n)。
    • 平均情况:时间复杂度是 O(n^2)。
  2. 空间复杂度:

    • 插入排序只需要一个额外空间用于临时存储要插入的元素,所以空间复杂度是 O(1)。

总结:插入排序的平均和最坏情况时间复杂度都是 O(n^2),空间复杂度是 O(1)。

需要注意的是,插入排序适用于部分已排序的情况,这时其效率会相对较高。


3. 插入排序C语言代码

C代码实现:

#include <stdio.h>  void insertionSort(int arr[], int n) {  int i, key, j;  for (i = 1; i < n; i++) {  key = arr[i];  j = i - 1;  //将arr[0..i-1]中大于key的元素移动到当前位置之前的一个位置 while (j >= 0 && arr[j] > key) {  arr[j + 1] = arr[j];  j = j - 1;  }  arr[j + 1] = key;  }  
}  void printArray(int arr[], int n) {  int i;  for (i = 0; i < n; i++) {  printf("%d ", arr[i]);  }  printf("\n");  
}  int main() {  int arr[] = {12, 11, 13, 5, 6};  int n = sizeof(arr) / sizeof(arr[0]);  insertionSort(arr, n);  printArray(arr, n);  return 0;  
}

代码详解:

  1. void insertionSort(int arr[], int n) 函数定义了一个对整数数组 arr[] 进行插入排序的函数,其中 n 是数组的长度。
  2. for 循环中,从数组的第二个元素开始(索引为1),每一个元素都被视为需要插入到已排序子数组的新元素。key 存储了当前正在考虑的元素的值。
  3. while 循环用于移动所有大于 key 的已排序元素向右移动一位,以便为 key 提供空间。一旦找到 key 的正确位置或到达数组的开头,循环就会停止。然后,将 key 插入到正确的位置。
  4. printArray 函数用于打印已排序的数组。在 main 函数中,我们定义了一个需要排序的数组,并调用 insertionSort 函数进行排序。最后,打印已排序的数组。

4. 插入排序代码运行结果

代码运行结果:

f7ddfc2c5dca40b383151c15cfa754d2.png

 

相关文章:

排序算法介绍(一)插入排序

0. 简介 插入排序&#xff08;Insertion Sort&#xff09; 是一种简单直观的排序算法&#xff0c;它的工作原理是通过构建有序序列&#xff0c;对于未排序数据&#xff0c;在已排序序列中从后向前扫描&#xff0c;找到相应位置并插入。插入排序在实现上&#xff0c;通常…...

2023新优化应用:RIME-CNN-LSTM-Attention超前24步多变量回归预测算法

程序平台&#xff1a;适用于MATLAB 2023版及以上版本。 霜冰优化算法是2023年发表于SCI、中科院二区Top期刊《Neurocomputing》上的新优化算法&#xff0c;现如今还未有RIME优化算法应用文献哦。RIME主要对霜冰的形成过程进行模拟&#xff0c;将其巧妙地应用于算法搜索领域。 …...

RNN:文本生成

文章目录 一、完整代码二、过程实现2.1 导包2.2 数据准备2.3 字符分词2.4 构建数据集2.5 定义模型2.6 模型训练2.7 模型推理 三、整体总结 采用RNN和unicode分词进行文本生成 一、完整代码 这里我们使用tensorflow实现&#xff0c;代码如下&#xff1a; # 完整代码在这里 imp…...

Rust UI开发(五):iced中如何进行页面布局(pick_list的使用)?(串口调试助手)

注&#xff1a;此文适合于对rust有一些了解的朋友 iced是一个跨平台的GUI库&#xff0c;用于为rust语言程序构建UI界面。 这是一个系列博文&#xff0c;本文是第五篇&#xff0c;前四篇链接&#xff1a; 1、Rust UI开发&#xff08;一&#xff09;&#xff1a;使用iced构建UI时…...

Linux学习笔记2

web服务器部署&#xff1a; 1.装包&#xff1a; [rootlocalhost ~]# yum -y install httpd 2.配置一个首页&#xff1a; [rootlocalhost ~]# echo i love yy > /var/www/html/index.html 启动服务&#xff1a;[rootlocalhost ~]# systemctl start httpd Ctrl W以空格为界…...

数据结构算法-插入排序算法

引言 玩纸牌 的时候。往往 需要将牌从乱序排列变成有序排列 这就是插入排序 插入排序算法思想 先看图 首先第一个元素 我默认已有序 那我们从第二个元素开始&#xff0c;依次插入到前面已有序的部分中。具体来说&#xff0c;我们将第二个元素与第一个元素比较&#xff0c;…...

安装Kuboard管理K8S集群

目录 第一章.安装Kuboard管理K8S集群 1.安装kuboard 2.绑定K8S集群&#xff0c;完成信息设定 3.内网安装 第二章.kuboard-spray安装K8S 2.1.先拉镜像下来 2.2.之后打开后&#xff0c;先熟悉功能&#xff0c;注意版本 2.3.打开资源包管理&#xff0c;选择符合自己服务器…...

网络安全行业大模型调研总结

随着人工智能技术的发展&#xff0c;安全行业大模型SecLLM&#xff08;security Large Language Model&#xff09;应运而生&#xff0c;可应用于代码漏洞挖掘、安全智能问答、多源情报整合、勒索情报挖掘、安全评估、安全事件研判等场景。 参考&#xff1a; 1、安全行业大模…...

Linux AMH服务器管理面板本地安装与远程访问

最近&#xff0c;我发现了一个超级强大的人工智能学习网站。它以通俗易懂的方式呈现复杂的概念&#xff0c;而且内容风趣幽默。我觉得它对大家可能会有所帮助&#xff0c;所以我在此分享。点击这里跳转到网站。 文章目录 1. Linux 安装AMH 面板2. 本地访问AMH 面板3. Linux安装…...

Sharding-Jdbc(3):Sharding-Jdbc分表

1 分表分库 LogicTable 数据分片的逻辑表&#xff0c;对于水平拆分的数据库(表)&#xff0c;同一类表的总称。 订单信息表拆分为2张表,分别是t_order_0、t_order_1&#xff0c;他们的逻辑表名为t_order。 ActualTable 在分片的数据库中真实存在的物理表。即上个示例中的t_…...

zookeeper集群 +kafka集群

1.zookeeper kafka3.0之前依赖于zookeeper zookeeper是一个开源&#xff0c;分布式的架构&#xff0c;提供协调服务&#xff08;Apache项目&#xff09; 基于观察者模式涉及的分布式服务管理架构 存储和管理数据&#xff0c;分布式节点上的服务接受观察者的注册&#xff0c…...

2022年全国大学生数据分析大赛医药电商销售数据分析求解全过程论文及程序

2022年全国大学生数据分析大赛 医药电商销售数据分析 原题再现&#xff1a; 问题背景   20 世纪 90 年代是电子数据交换时代&#xff0c;中国电子商务开始起步并初见雏形&#xff0c;随后 Web 技术爆炸式成长使电子商务处于蓬勃发展阶段&#xff0c;目前互联网信息碎片化以…...

Python版本与opencv版本的对应关系

python版本要和opencv版本相对应&#xff0c;否则安装的时候会报错。 可以到Links for opencv-python上面查看python版本和opencv版本的对应关系&#xff0c;如图&#xff0c;红框内是python版本&#xff0c;绿框内是opencv版本。 查看自己的python版本后&#xff0c;使用下面…...

【开源视频联动物联网平台】LiteFlow

LiteFlow是一个轻量且强大的国产规则引擎框架&#xff0c;可用于复杂的组件化业务的编排领域。它基于规则文件来编排流程&#xff0c;支持xml、json、yml三种规则文件写法方式&#xff0c;再复杂的逻辑过程都能轻易实现。LiteFlow于2020年正式开源&#xff0c;2021年获得开源中…...

家用智能门锁——智能指纹锁方案

智能指纹锁产品功能&#xff1a; 1&#xff1a;指纹识别技术&#xff1a;光学传感器、半导体传感器或超声波传感器等。 2&#xff1a;指纹容量&#xff1a;智能指纹锁可以存储的指纹数量&#xff0c;通常在几十到几百个指纹之间。 3&#xff1a;解锁时间&#xff1a;指纹识别和…...

Qt6 QRibbon 一键美化Qt界面

强烈推荐一个 github 项目&#xff1a; https://github.com/gnibuoz/QRibbon 作用&#xff1a; 在几乎不修改任何你自己代码的情况下&#xff0c;一键美化你的 UI 界面。 代码环境&#xff1a;使用 VS2019 编译 Qt6 GUI 程序&#xff0c;继承 QMainWindow 窗口类 一、使用方法 …...

JAVA IO:NIO

1.阻塞 IO 模型 ​ 最传统的一种 IO 模型&#xff0c;即在读写数据过程中会发生阻塞现象。当用户线程发出 IO 请求之后&#xff0c;内核会去查看数据是否就绪&#xff0c;如果没有就绪就会等待数据就绪&#xff0c;而用户线程就会处于阻塞状态&#xff0c;用户线程交出 CPU。当…...

Python 在控制台打印带颜色的信息

#格式&#xff1a;  设置颜色开始 &#xff1a;\033[显示方式;前景色;背景色m #说明&#xff1a; 前景色 背景色 颜色 --------------------------------------- 30 40 黑色 31 41 红色 32 …...

SQL Server 数据库,创建触发器避免数据被更改

5.4触发器 触发器是一种特殊类型的存储过程&#xff0c;当表中的数据发生更新时将自动调用&#xff0c;以响应INSERT、 UPDATE 或DELETE 语句。 5.4.1什么是触发器 1.触发器的概念 触发器是在对表进行插入、更新或删除操作时自动执行的存储过程&#xff0c;触发器通常用于强…...

C语言实现植物大战僵尸(完整版)

实现这个游戏需要Easy_X 这个在我前面一篇C之番外篇爱心代码有程序教你怎么下载&#xff0c;大家可自行查看 然后就是需要植物大战僵尸的素材和音乐&#xff0c;需要的可以在评论区 首先是main.cpp //开发日志 //1导入素材 //2实现最开始的游戏场景 //3实现游戏顶部的工具栏…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

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. 执行器…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...

适应性Java用于现代 API:REST、GraphQL 和事件驱动

在快速发展的软件开发领域&#xff0c;REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名&#xff0c;不断适应这些现代范式的需求。随着不断发展的生态系统&#xff0c;Java 在现代 API 方…...

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...