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

基础算法(3):排序(3)插入排序

1.插入排序实现

     插入排序的工作原理是:通过构建有序序列,对于未排序数据,在已经排序的序列从后向前扫描,找到位置并插入,类似于平时打扑克牌时,将牌从大到小排列,每次摸到一张牌就插入到正确的位置。

     实现逻辑:

  (1)从第一个元素出现,该元素认为已经被排好序

  (2)取出下一个元素,在已经排序的序列中从后向前扫描

    (3)如果扫描到某个元素大于取出的新元素,将该元素移到下一个位置

  (4)重复(3),直到找到已排序的元素小于或者等于新元素的位置

  (5)将新元素插入到该位置后面

  (6)重复(2)-(5)

     代码实现:

void insertSort(int* arr,int len)
{for(int i=i;i<len;i++){int cur=arr[i];int j=i-1;while(j>=0&&arr[j]>cur){arr[j+1]=arr[j];j--;}arr[j+1]=cur;}
}

2.插入排序的时间复杂度

     问题规模仍然为n,最好情况是序列是升序,这样只需要比较n-1次,最坏情况是序列是降序,需要比较n(n-1)次,所以时间复杂度为O(n^2)

3.leetcode题目

3.1 删除某些元素后的数组均值

void insertionSort(int *a ,int n){int i,j;int tmp ;for(i = 1; i < n; ++i){for(j = i - 1; j>=0; --j){if(a[j] > a[j+1]){tmp = a[j];a[j] = a[j+1];a[j+1] = tmp; }}}
}
double trimMean(int* arr, int arrSize){insertionSort(arr,arrSize);int cnt = arrSize / 20;double count = 0;for(int i = cnt; i < arrSize - cnt; ++i){count += arr[i];}return count /  (arrSize - 2*cnt);
}

3.2  去掉最低工资和最高工资后的工资平均值

double average(int* salary,int salarySize){for (int i = 1; i < salarySize; i++) {int tmp = salary[i];int j = i - 1;for (; j >= 0 && tmp < salary[j]; j--) {salary[j + 1] = salary[j];}salary[j + 1] = tmp;}double ans=0;for(int i=1;i<salarySize-1;i++){ans+=salary[i];}return ans/(salarySize-2); 
}

3.3 学生分数的最小差值

int minimumDifference(int* nums, int numsSize, int k) {for (int i = 1; i < numsSize; i++){int tmp = nums[i];int j = i - 1;for (; j >= 0 && tmp < nums[j]; j--) {nums[j + 1] = nums[j];}nums[j + 1] = tmp;}int ret=100000;for(int i=0;i+k-1<numsSize;i++){int ans=nums[i+k-1]-nums[i];if(ans<ret){ret=ans;}}return ret;
}

相关文章:

基础算法(3):排序(3)插入排序

1.插入排序实现 插入排序的工作原理是&#xff1a;通过构建有序序列&#xff0c;对于未排序数据&#xff0c;在已经排序的序列从后向前扫描&#xff0c;找到位置并插入&#xff0c;类似于平时打扑克牌时&#xff0c;将牌从大到小排列&#xff0c;每次摸到一张牌就插入到正确的位…...

Vue3-18-侦听器watch()、watchEffect() 的基本使用

什么是侦听器 个人理解&#xff1a;当有一个响应式状态&#xff08;普通变量 or 一个响应式对象&#xff09;发生改变时&#xff0c;我们希望监听到这个改变&#xff0c;并且能够进行一些逻辑处理。那么侦听器就是来帮助我们实现这个功能的。侦听器 其实就是两个函数&#xff…...

mysql 5.7.34升级到5.7.44修补漏洞

mysql 5.7.34旧版本&#xff0c;漏扫有漏洞&#xff0c;升级到最新版本 旧版本5.7.34在 /home/mysql/mysql中安装 备份旧版本数据还有目录 数据库备份升级 tar -xf mysql-5.7.44-el7-x86_64.tar #覆盖旧版本数据库文件 #注意看看文件是否和你起服务的用户一样 \cp -r mysql-5…...

基于电子密码锁具有掉电存储系统设计

**单片机设计介绍&#xff0c;基于电子密码锁具有掉电存储系统设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 电子密码锁是一种使用电子技术实现开关门的装置&#xff0c;通常由密码输入板、电控锁、控制电路等组成。其中&a…...

清华大学考研复试上机题之二叉树的遍历

问题描述&#xff1a; 编一个程序&#xff0c;读入用户输入的一串先序遍历字符串&#xff0c;根据此字符串建立一个二叉树&#xff08;以指针方式存储&#xff09;。 例如如下的先序遍历字符串&#xff1a;ABC##DE#G##F### 其中#表示的是空格&#xff0c;空格字符代表空树。…...

java全栈体系结构-架构师之路(持续更新中)

Java 全栈体系结构 数据结构与算法实战&#xff08;已更&#xff09;微服务解决方案数据结构模型(openresty/tengine)实战高并发JVM虚拟机实战性能调优并发编程实战微服务框架源码解读集合框架源码解读分布式架构解决方案分布式消息中间件原理设计模式JavaWebJavaSE新零售电商项…...

【C语言】超详解strncpystrncatstrncmpstrerrorperror的使⽤和模拟实现

&#x1f308;write in front :&#x1f50d;个人主页 &#xff1a; 啊森要自信的主页 ✏️真正相信奇迹的家伙&#xff0c;本身和奇迹一样了不起啊&#xff01; 欢迎大家关注&#x1f50d;点赞&#x1f44d;收藏⭐️留言&#x1f4dd;>希望看完我的文章对你有小小的帮助&am…...

【Spring Boot 】Spring Boot 常用配置总结

文章目录 前言1.多环境配置application.propertiesapplication.yaml 2.常用配置3.配置读取4.自定义配置 前言 在涉及项目开发时&#xff0c;通常我们会灵活地把一些配置项集中在一起&#xff0c;如果你的项目不是很大的情况下&#xff0c;那么通过配置文件集中不失为一个很好的…...

Day60力扣打卡

打卡记录 1682分了记录下&#xff0c;希望下回能突破1700捏&#x1f923;&#x1f923;。作为一个菜鸟&#x1f628;&#xff0c;知道自己不太行&#x1f62d;&#x1f44a;&#xff0c;从以前的周赛稳定1题到稳定2题&#x1f97a;&#xff0c;到现在的时有时无的3题&#x1f9…...

Axure的动态图使用以及说明

认识Axure动态图 Axure动态图是Axure中的一种功能&#xff0c;它允许用户在原型中添加动画效果和交互动作&#xff0c;使原型更加生动和具有真实的用户体验。用户可以通过添加动态图来展示页面过渡、按钮点击、下拉菜单等交互操作的效果。 这是&#xff1a;就是我们今天要叫的…...

力扣 | 437. 路径总和 III

437. 路径总和 III mport java.util.ArrayList; import java.util.List;/*** int的取值范围&#xff1a;* -2^31 ~ 2^31-1* <p>* -2147483648 ~ 2147483647&#xff08;约等于10的9次方&#xff09;* <p>* long long的取值范围&#xff1a;* -2^63 ~ (2^63-1&…...

如何部署自己的服务渲染页面为Pdf文档

前言 相信大家都觉得官方发布的文档生成模块https://docs.mendix.com/appstore/modules/document-generation/很有用&#xff0c;它能把Mendix页面像素级导出到Pdf文件中&#xff0c;这对于归档等业务非常有价值。但部署依赖公有云提供的渲染服务&#xff0c;而中国本土用户对…...

常用的调试方法(段错误产生原因)

C 语言中常用的调试技巧和 demo C语言中常用的调试方法 打印调试信息 GDB 调试器 编写单元测试 段错误产生原因 初学时两种常用的段错误调试方法 C 语言中常用的调试技巧和 demo 当程序员进行调试时&#xff0c;他们通常会使用一些调试语句或技巧来帮助他们理解代码的执行过程…...

[云原生] Docker 入门指南:镜像、容器、卷和网络解析

Docker 是一种流行的容器化平台&#xff0c;它以其强大的功能和易用性在软件开发和部署领域广受欢迎。本文将带领您逐步探索 Docker 中的四个核心概念&#xff1a;镜像、容器、卷和网络。通过了解这些概念的是什么、为什么以及如何使用&#xff0c;您将能够更好地理解和利用 Do…...

机器学习-聚类问题

前言 聚类算法又叫做”无监督分类“&#xff0c;目标是通过对无标记训练样本来揭示数据的内在性质及 规律&#xff0c;为进一步的数据分析提供基础。 Kmeans 作为聚类算法的典型代表&#xff0c;Kmeans可以说是最简单的聚类算法&#xff0c;没有之一&#xff0c;那她是怎么完…...

leetcode9.回文数java解法

力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 给你一个整数 x &#xff0c;如果 x 是一个回文整数&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 回文数是指正序&#xff08;从左向右&#xff09;和倒序&#xff08;从右向左&…...

图论专栏一《图的基础知识》

图论&#xff08;Graph Theory&#xff09;是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形&#xff0c;这种图形通常用来描述某些实体之间的某种特定关系&#xff0c;用点代表实体&#xff0c;用连接两点的线表示两个实体间具有的…...

得帆云为玉柴打造CRM售后服务管理系统,实现服务全过程管理|基于得帆云低代码的CRM案例系列

广西玉柴机器股份有限公司 广西玉柴机器股份有限公司始建于1992年&#xff0c;是国内行业首家赴境外上市的中外合资企业&#xff0c;产品远销亚欧美非等180多个国家和地区。公司总部设在广西玉林市&#xff0c;下辖11家子公司&#xff0c;生产基地布局广西、江苏、安徽、山东等…...

智能优化算法应用:基于蝠鲼觅食算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于蝠鲼觅食算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于蝠鲼觅食算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.蝠鲼觅食算法4.实验参数设定5.算法结果6.…...

vue2 以及 vue3 自定义组件使用 v-model使用默认值以及自定义事件

vue2 以及 vue3 自定义组件使用 v-model使用默认值以及自定义事件 1. vue2 自定义组件的 v-model vue2官网&#xff0c;自定义组件官方解释&#xff1a;一个组件上的 v-model 默认会利用名为 value 的 prop 和名为 input 的事件上代码代码中使用了 element-ui 子组件 使用默…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

二维FDTD算法仿真

二维FDTD算法仿真&#xff0c;并带完全匹配层&#xff0c;输入波形为高斯波、平面波 FDTD_二维/FDTD.zip , 6075 FDTD_二维/FDTD_31.m , 1029 FDTD_二维/FDTD_32.m , 2806 FDTD_二维/FDTD_33.m , 3782 FDTD_二维/FDTD_34.m , 4182 FDTD_二维/FDTD_35.m , 4793...