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

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

 

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

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

相关文章

计算机组成学习-指令系统总结

复习本章时&#xff0c;思考以下问题&#xff1a; 1)什么是指令&#xff1f;什么是指令系统&#xff1f;为什么要引入指令系统&#xff1f;2)一般来说&#xff0c;指令分为哪些部分&#xff1f;每部分有什么用处&#xff1f;3)对于一个指令系统来说&#xff0c;寻址方式多和少…

龙芯loongarch64服务器编译安装maturin

前言 maturin 是一个构建和发布基于 Rust 的 Python 包的工具,但是在安装maturin的时候,会出现如下报错:error: cant find Rust compiler 这里记录问题解决过程中遇到的问题: 1、根据错误的提示需要安装Rust Compiler,首先去其官网按照官网给的解决办法提供进行安装 curl…

SocialSelling社交销售1+5+1方法论系列:社交销售价值何在

社交销售作为差异化的社媒社交营销模式&#xff0c;在实际运营操作过程中需要实现个人、部门与系统的融合打磨&#xff0c;并非只是应用工具那么简单。为了更高效地服务赋能客户&#xff0c;傲途基于实战提炼出社交销售151方法论&#xff0c;在近期系列内容中&#xff0c;我们将…

浅谈安科瑞无线测温设备在挪威某项目的应用

摘要&#xff1a;安科瑞无线温度设备装置通过无线温度收发器和各无线温度传感器直接进行温度值的传输&#xff0c;并采用液晶显示各无线温度传感器所测温度。 Absrtact:Acre wireless temperature device directly transmits the temperature value through the wireless temp…

鸿蒙4.0开发笔记之ArkTS装饰器语法基础@Prop@Link@State状态装饰器(十二)

文章目录 一、哪些是状态装饰器二、StatePropLink状态传递的核心规则三、状态装饰器练习 一、哪些是状态装饰器 1、State&#xff1a;被装饰拥有其所属组件的状态&#xff0c;可以作为其子组件单向和双向同步的数据源。当其数值改变时&#xff0c;会引起相关组件的渲染刷新。 …

力扣116. 填充每个节点的下一个右侧节点指针(详细讲解root根节点的理解)

题目&#xff1a; 给定一个 完美二叉树 &#xff0c;其所有叶子节点都在同一层&#xff0c;每个父节点都有两个子节点。二叉树定义如下&#xff1a; struct Node {int val;Node *left;Node *right;Node *next; } 填充它的每个 next 指针&#xff0c;让这个指针指向其下一个右…

LLM之RAG实战(一):使用Mistral-7b, LangChain, ChromaDB搭建自己的WEB聊天界面

一、RAG介绍 如何使用没有被LLM训练过的数据来提高LLM性能&#xff1f;检索增强生成&#xff08;RAG&#xff09;是未来的发展方向&#xff0c;下面将解释一下它的含义和实际工作原理。 ​ 假设您有自己的数据集&#xff0c;例如来自公司的文本文档。如何让ChatGPT和其他…

ZPLPrinter Emulator SDK for .NET 6.0.23.1123​ Crack

ZPLPrinter Emulator SDK for .NET 适用于 .NET 的 ZPLPrinter 仿真器 SDK 允许您通过编写 C# 或VB.NET 代码针对任何 .NET Framework、.NET CORE、旧版 ASP.NET MVC 和 CORE、Xamarin、Mono 和通用 Windows 平台 (UWP) 作业。 适用于 .NET 的 ZPLPrinter 仿真器 SDK 允许您将…

matplotlib与opencv图像读取与显示的问题

个人博客:Sekyoro的博客小屋 个人网站:Proanimer的个人网站 最近在用opencv和matplotlib展示图片,但是遇到了一些问题,这里展开说说 首先需要明确的是,opencv和matplotlib读取图片都是通道在最后,而前者默认可见光图像是BGR,后者是RGB.此外还有PIL以及imageio等读取图像的工具…

(学习笔记)Xposed模块编写(一)

前提&#xff1a;需要已经安装Xposed Installer 1. 新建一个AS项目 并把MainActvity和activity_main.xml这两个文件删掉&#xff0c;然后在AndriodManifest.xml中去掉这个Activity的声明 2. 在settings.gralde文件中加上阿里云的仓库地址&#xff0c;否则Xposed依赖无法下载 m…

9款热门API接口分享,值得收藏!

电商API接口 干货分享 开始 “ API是什么&#xff1f; API的主要目的是提供应用程序与开发人员以访问一组例程的能力&#xff0c;而又无需访问源码&#xff0c;或理解内部工作机制的细节。提供API所定义的功能的软件称作此API的实现。API是一种接口&#xff0c;故而是一种抽象…

Banana Pi最新的路由器板BPI-R4上市销售,基于MediaTek MT7988A

Banana Pi 发布了一款新的路由器板 Banana Pi BPI-R4&#xff0c;基于配备四核 Arm CPU 的 MediaTek MT7988A SoC。该板不仅仅是Raspberry Pi 的另一个替代品&#xff0c;而且是用于家庭网络和自动化的设备。 Banana Pi BPI-R4 的外形尺寸比单板计算机更像网络设备。对于那些希…

Python函数的基本使用(一)

Python函数的基本使用&#xff08;一&#xff09; 一、函数概述二、函数的定义2.1 函数的语法2.2 语法说明2.3 函数定义的方式2.4 总结 三、函数的调用3.1 函数调用语法3.2 语法说明3.3 函数调用 四、函数的参数4.1 参数的分类4.2 必需参数4.3 默认值参数4.4 关键字参数4.5 不定…

风变科技千万营收的AIGC项目,在Fanbook成功落地,专访风变科技CMO江育麟

在AIGC时代&#xff0c;创作生产力被下放到了每一位普通人身上&#xff0c;然后用户与AIGC应用之间还存在一定的认知与技术沟壑。 最近&#xff0c;【AIGC开放社区】注意到一款AIGC课程项目受到了相当的关注&#xff0c;让许多0基础的学员轻松地学会了使用AIGC技术的基本方法。…

风控交易系统跟单系统资管软件都有哪些功能特点?

资管分仓软件的主要功能就是母账户可以添加子账号&#xff0c;并且设置出入金&#xff0c;手续费、保证金、风控等功能&#xff0c;同时监控端更可以直观的看子账户的交易情况直接折线图展示更加直观&#xff0c;在监控端的最高权限可以直接一键平仓子账户&#xff08;如果子账…

基于jsp的搜索引擎

摘 要 随着互联网的不断发展和日益普及&#xff0c;网上的信息量在迅速地增长&#xff0c;在2004年4月&#xff0c;全球Web页面的数目已经超过40亿&#xff0c;中国的网页数估计也超过了3亿。 目前人们从网上获得信息的主要工具是浏览器&#xff0c;搜索引擎在网络中占有举足轻…

23种设计模式之C++实践(二)

23种设计模式之C++实践 3. 设计模式(二)组合型模式7. 适配器模式——不兼容结构的协调7.2:类适配器模式7.3:双向适配器模式适配器模式总结8.桥接模式——处理多维度变化桥接模式总结9. 组合模式——树形结构的处理9.2 透明组合模式9.3 安全组合模式组合模式总结10. 装饰模式…

【海思SS528 | VDEC】MPP媒体处理软件V5.0 | 视频解码模块——学习笔记

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; &#x1f923;本文内容&#x1f923;&a…

HR看好的字符函数和字符串处理函数!!!

本篇会加入个人的所谓‘鱼式疯言’❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言,而是理解过并总结出来通俗易懂的大白话,我会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的&#xff0c;可能说的不是那么严谨.但小编初心是能让更多人能接受我们这个概念 前言 在本篇…

智能监控平台/视频共享融合系统EasyCVR接入RTSP协议视频流无法播放原因是什么?

视频集中存储/云存储/视频监控管理平台EasyCVR能在复杂的网络环境中&#xff0c;将分散的各类视频资源进行统一汇聚、整合、集中管理&#xff0c;实现视频资源的鉴权管理、按需调阅、全网分发、智能分析等。AI智能/大数据视频分析EasyCVR平台已经广泛应用在工地、工厂、园区、楼…