当前位置: 首页 > 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 子组件 使用默…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

第八部分:阶段项目 6:构建 React 前端应用

现在&#xff0c;是时候将你学到的 React 基础知识付诸实践&#xff0c;构建一个简单的前端应用来模拟与后端 API 的交互了。在这个阶段&#xff0c;你可以先使用模拟数据&#xff0c;或者如果你的后端 API&#xff08;阶段项目 5&#xff09;已经搭建好&#xff0c;可以直接连…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现指南针功能

指南针功能是许多位置服务应用的基础功能之一。下面我将详细介绍如何在HarmonyOS 5中使用DevEco Studio实现指南针功能。 1. 开发环境准备 确保已安装DevEco Studio 3.1或更高版本确保项目使用的是HarmonyOS 5.0 SDK在项目的module.json5中配置必要的权限 2. 权限配置 在mo…...

职坐标物联网全栈开发全流程解析

物联网全栈开发涵盖从物理设备到上层应用的完整技术链路&#xff0c;其核心流程可归纳为四大模块&#xff1a;感知层数据采集、网络层协议交互、平台层资源管理及应用层功能实现。每个模块的技术选型与实现方式直接影响系统性能与扩展性&#xff0c;例如传感器选型需平衡精度与…...

解决MybatisPlus使用Druid1.2.11连接池查询PG数据库报Merge sql error的一种办法

目录 前言 一、问题重现 1、环境说明 2、重现步骤 3、错误信息 二、关于LATERAL 1、Lateral作用场景 2、在四至场景中使用 三、问题解决之道 1、源码追踪 2、关闭sql合并 3、改写处理SQL 四、总结 前言 在博客&#xff1a;【写在创作纪念日】基于SpringBoot和PostG…...