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

c语言经典算法—二分查找,冒泡,选择,插入,归并,快排,堆排

一、二分查找

         1、前提条件:数据有序,随机访问;

         2、实现:递归实现,非递归实现

         3、注意事项:

                循环退出条件:low <=high,low = high.说明还有一个元素,该元素还要与key进行比较

                mid的取值:mid=(low + high)/2;mid = low + ((high - low)>>1)

                low 和high 的更新:low = mid +1;high = mid - 1;不能写成low = mid +1,high = mid-1;又可能出现死循环;

        代码实现:

1、查找第一个与key相等的元素:

2、查找最后一个与key相等的元素

3、查找最后一个小于等于key值的元素

4、查找第一个大于等于key值的元素

二、冒泡排序

        如何评价一个算法:

        1、时间复杂度:最好情况;最坏情况;平均情况;系数和低阶项

        2、空间复杂度:原地排序(特指空间复杂度为O(1))的排序;

        3、稳定性:数据集中“相等”的元素,如果排序前和排序后的相对次序不变,那么这个排序就是稳定的;

        稳定性就是排序算法的很重要的指标;

冒泡排序:

        比较相邻的元素,如果前一个比后一个大,就交换次序,

        对每一对相邻元素做同样的工作,从第一对到最后一对。最大的元素就会位于最后位置;

        除最后一个元素外,对其他元素重复上面的步骤,直到元素的个数为1;

时间复杂度:

        最好情况原数组有序(O(n));

        最坏情况原数组逆序(比较次数(n-1)+(n-2)+...+1 = (n(n-1))/2)

                                           交换次数:((n-1)+(n-2)+...+1  = (n(n-1))/2)

        平均情况(每一种情况出现的情况是相等的):总情况(N!)

                                (比较次数:大于交换的次数,小于(n(n-1))/2)

                                 (交换次数(n(n-1)/4))

分析:有序元素对,逆序元素对,逆序度,有序度;

有序对:34,24,14

逆序对:12,13,23

排序的过程:增加有序度,减少逆序度,最终达到满有序度;

冒泡排序交换导致有序度+1,逆序度-1;

空间复杂度:O(1);//原地排序

稳定性:稳定,arr[j]>arr[j+1]   才发生交换;

三、选择排序(无论什么数据进去都是(O(n2))的时间复杂度,所以用它的时候数据规模越小越好,唯一好处是不占用额外内存)

        工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后再从剩余未排序中继续寻找最小(大)元素,然后放到已排序序列的末尾,以此类推,直到所有元素均排序完毕;(选择排序不能像冒泡排序一样去优化)

        时间复杂度:O(n2)

                比较次数:(n-1)+ ...+1 =(n(n-1))/2

                交换次数:n-1;

        空间复杂度:O(1)原地排序

        稳定性:不稳定,发生了长距离的交换;

四、插入排序:

        工作原理:通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在从后向前扫描过程中,需要反复把已排序的元素逐步向后挪位,为最新元素提供插入空间;

        时间复杂度:

                最好情况:(O(n))

                                原数组有序(比较次数,(n-1))交换次数:原数组有序(0)

                最坏情况:(O(n2))

                                原数组逆序(比较次数,(n-1)+(n-2)+...+1 = (n(n-1))/2);

交换次数((n-1)+(n-2)+...+1 =(n(n-1))/2:

                平均情况:

                                比较次数:大于交换次数,小于(n(n-1))/2

                                交换次数:(n(n-1))/4(逆序个数)

插入排序好处,当元素基本有序时,其性能非常好;

空间复杂度,O(1),原地排序

稳定性:稳定;

冒泡排序,选择排序,插入排序小结:

        

五、希尔排序(缩小增量排序,插入排序的改进版本):

        第一批打破O(n2)这个时间复杂度的方法;

        gap(希尔):n/2、n/4、...1;

gap = n/2=5

        

先按gap分组,组内使用简单的插入排序(十个元素分为5组);

第一次组间排序完成后,就缩小增量,gap=5/2=2;gap =1;

时间复杂度比O(n2)小,和具体的gap序列相关;

空间复杂度O(1)原地排序;

稳定性:不稳定,会发生长距离交换;

六、归并排序:

        先把大数组分成两个小数组,直到有序再合并;单个数组已经算是有序的;

用递归解决;

        

注意释放堆区数组

        

七、快速排序

        从数列中挑出一个元素,称为“基准”(pivot);(一般情况下可以选几个值取中位数,也可以选第一位,或者随机位)

        重新排序数列,所有元素比基准值小的拜访在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任意边。)在这个分区退出后,改基准就处于数列的中间位置(也就是最终位置)这个操作我们称之为分区(partition);

        递归地把小于基准值元素地子数列和大于基准值元素地子数列排序(左右两边都使用快排);

i 是放下一个比基准值小的位置,j放比基准值大的值;先移动 j 再移动 i ;

先找比基准值小的,再找比基准值大的,交替找直到  i  j 相遇,基准值的位置就确定了;

因为基准值已经保存就可以移动 j 把第一个值覆盖掉(以第一个值为基准)

时间复杂度:

        最好情况:(每次分区都分成大小相等的两份)

        最坏情况:每次基准值都位于最左边或者最右边;

        平均情况(假设每次分成三比一的情况):

空间复杂度:

快速排序的改进策略(基准值的选取(随机选,选择多个元素的中位数);分区操作的优化;选择多个基准值);

八、堆排序

        二叉堆(大顶堆(根节点的键大于左右子树所有结点的键,并且左右子树都是大顶堆);小顶堆(根节点的键小于左右子树所有结点的键,并且左右子树都是小顶堆))

        

把数组看作一个完全二叉树;

堆排算法:

把完全二叉树构建成大顶堆,找到第一个非叶子结点,从后往前构建大顶堆

把堆顶元素和无序区的最后一个元素交换,交换之后无序区的长度减一,

把无序区重新调整成大顶堆,重复上一步操作,直到无序区的长度为1;

归并(缺点:占用内存空间复杂度O(n)),快排,堆排

九、基于比较的排序算法

        证明:基于比较 的排序算法,时间复杂度的下限就是O(nlogn);

相关文章:

c语言经典算法—二分查找,冒泡,选择,插入,归并,快排,堆排

一、二分查找 1、前提条件&#xff1a;数据有序&#xff0c;随机访问&#xff1b; 2、实现&#xff1a;递归实现&#xff0c;非递归实现 3、注意事项&#xff1a; 循环退出条件:low <high,low high.说明还有一个元素&#xff0c;该元素还要与key进行比较 mid的取值&#xf…...

网站SSL证书有什么用

在当今&#xff0c;网站安全对于企业和个人来说至关重要。其中&#xff0c;SSL证书在保护网站和用户数据方面发挥着关键作用。 1&#xff0c;数据加密保护&#xff1a;SSL证书通过使用加密技术&#xff0c;将网站与访问者之间的通信进行加密。这意味着通过SSL保护的网站上的数据…...

ubuntu 20.04 server安装

ubuntu 20.04 server安装 ubuntu-20.04.6-live-server-amd64.iso 安装 安装ubuntu20.04 TLS系统后&#xff0c;开机卡在“A start job is running for wait for network to be Configured”等待连接两分多钟。 cd /etc/systemd/system/network-online.target.wants/在[Servi…...

造数工具调研

开源项目 语言 地址 描述 备注 Faker Python https://github.com/joke2k/faker 一个Python库&#xff0c;可以生成各种各样的假数据&#xff0c;包括SQL语句。它支持多种数据库&#xff0c;包括MySQL、PostgreSQL、Oracle等。Faker可以生成各种类型的数据&#xff0c;如…...

Linux文件系统目录结构

典型的Linux文件系统目录结构的列表 典型的Linux文件系统目录结构的列表。每个目录都有其特定的用途&#xff1a; /bin: 存放系统引导和修复所需的二进制可执行文件&#xff0c;如ls&#xff0c;cp&#xff0c;mv等命令。 /boot: 存放操作系统引导文件&#xff0c;例如内核和…...

CANoe新建XML自动化Test Modules

文章目录 1.打开Test Modules2.新建Environment3.新建XML Test Modules4.新建.can文件5.打开XML Test Modules6.新建xml脚本并保存7.编译8.在.can文件写个测试用例9.修改报告格式为HTML10.运行查看报告后面介绍的文章会重复用到这部分,这里单独介绍下,后面不做重复介绍。 1.…...

国内某发动机制造工厂RFID智能制造应用解决方案

一、工厂布局和装备 国内某发动机制造工厂的装配车间布局合理&#xff0c;设备先进&#xff0c;在这个5万平方米的生产区域内&#xff0c;各个工位之间流程紧密&#xff0c;工厂采用了柔性设备&#xff0c;占比达到了67%&#xff0c;数控化率超过90%&#xff0c;自动化率达到了…...

【SpringCloud Alibaba -- Nacos】Linux 搭建 Nacos 集群

搭建 Nacos 集群 架构 centos安装docker https://docs.docker.com/engine/install/centos/ 详细配置过程 MySql8 mysql数据库配置 数据库脚本 nacos/conf/nacos-mysql.sql Nacos2 application.properties 修改为mysql spring.datasource.platformmysqldb.num1 db.url…...

程序员使用 ChatGPT的 10 种最佳方式

自2022年11月30日发布以来&#xff0c;ChatGPT持续爆火&#xff0c;它在各个方面都产生了巨大的影响力&#xff0c;在软件开发行业&#xff0c;ChatGPT 有潜力彻底改变我们思考和处理软件开发的方式。 ChatGPT 正在改变软件开发流程&#xff0c;它理解自然语言和生成类人文本的…...

各种各类好用热门API推荐

各种各类的好用API推荐&#xff0c;含免费次数~ 天气预报查询&#xff1a;查询全国以及全球多个城市的天气&#xff0c;包含15天天气预报查询。天气预警&#xff1a;可以获取指定城市当前生效中的各类天气预警&#xff0c;如寒潮蓝色预警信号&#xff0c;或一次性拉取全国所有…...

高速串行总线——SATA

SATA简介 SATA的全称是Serial Advanced Technology Attachment(串行高级技术附件&#xff0c;一种基于行业标准的串行硬件驱动器接口)&#xff0c;它是一种电脑总线&#xff0c;主要功能是用作主板和大量存储设备&#xff08;如硬盘及光盘驱动器&#xff09;之间的数据传输 SA…...

不用流氓软件,如何在户外使用手机听下载到家中电脑里的音乐文件呢?

文章目录 本教程解决的问题是&#xff1a;按照本教程方法操作后&#xff0c;达到的效果是本教程使用环境&#xff1a;1 群晖系统安装audiostation套件2 下载移动端app3 内网穿透&#xff0c;映射至公网 很多老铁想在上班路上听点喜欢的歌或者相声解解闷儿&#xff0c;于是打开手…...

函数数组指针示例

函数数组指针是一个指向函数指针数组的指针。它用于存储一组函数指针&#xff0c;使您可以通过函数指针数组的索引来调用不同的函数。函数数组指针通常用于实现函数表或分发不同的操作或处理不同的事件。 以下是一个简单的示例&#xff0c;说明如何声明和使用函数数组指针&…...

万宾科技管网水位监测预警,管网水位的特点有哪些?

以往如果要了解城市地下排水管网的水位变化&#xff0c;需要依靠人工巡检或者排查的方式&#xff0c;这不仅加大了人员的工作量&#xff0c;而且也为市政府带来了更多的工作难题。比如人员监管监测不到位或无法远程监控等情况&#xff0c;都会降低市政府对排水管网的管理能力&a…...

vue element admin master 去掉登陆

vue element admin master 去掉登陆 修改/src/permission.js import router from ./router import store from ./store import { Message } from element-ui import NProgress from nprogress // progress bar import nprogress/nprogress.css // progress bar style import {…...

没有MES管理系统,先用数据采集设备能有用吗

在当前的数字化时代&#xff0c;企业纷纷意识到了数字化转型的重要性。数据被誉为新型生产要素&#xff0c;对于企业的运营和决策具有至关重要的作用。在数字化转型的过程中&#xff0c;许多企业面临着一个共同的问题&#xff1a;如何获取所需的数据&#xff1f; 有两家企业在…...

【JAVA学习笔记】61 - 线程入门、常用方法、同步机制,以及本章作业(难点)

项目代码 https://github.com/yinhai1114/Java_Learning_Code/tree/main/IDEA_Chapter17/src/com/yinhai 线程 一、线程相关概念 1.程序 是为完成特定任务、用某种语言编写的一组指令的集合。简单的说:就是我们写的代码 2.进程 1&#xff09;进程是指运行中的程序&#x…...

C#开发的OpenRA游戏之步兵射击(2)

C#开发的OpenRA游戏之步兵射击(2) 前面已经分析士兵射击的整个过程,理解它是怎么样根据武器来创建弹盒,然后加载子弹。现在来分析子弹是怎么伤害到对方的过程。 继续前面的分析,它创建了子弹类Bullet,在这个类里实现爆炸效果和伤害转化。类Bullet也是由它的信息类Bulle…...

基于Pytorch框架的LSTM算法(一)——单维度单步滚动预测(2)

#项目说明&#xff1a; 说明&#xff1a;1time_steps滚动预测代码 y_norm scaler.fit_transform(y.reshape(-1, 1)) y_norm torch.FloatTensor(y_norm).view(-1)# 重新预测 window_size 12 future 12 L len(y)首先对模型进行训练&#xff1b; 然后选择所有数据的后wind…...

安全操作(安卓推流)程序

★ 安全操作项目 项目描述&#xff1a;安全操作项目旨在提高医疗设备的安全性&#xff0c;特别是在医生离开操作屏幕时&#xff0c;以减少非授权人员的误操作风险。为实现这一目标&#xff0c;我们采用多层次的保护措施&#xff0c;包括人脸识别、姿势检测以及二维码识别等技术…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...

Chrome 浏览器前端与客户端双向通信实战

Chrome 前端&#xff08;即页面 JS / Web UI&#xff09;与客户端&#xff08;C 后端&#xff09;的交互机制&#xff0c;是 Chromium 架构中非常核心的一环。下面我将按常见场景&#xff0c;从通道、流程、技术栈几个角度做一套完整的分析&#xff0c;特别适合你这种在分析和改…...

对象回调初步研究

_OBJECT_TYPE结构分析 在介绍什么是对象回调前&#xff0c;首先要熟悉下结构 以我们上篇线程回调介绍过的导出的PsProcessType 结构为例&#xff0c;用_OBJECT_TYPE这个结构来解析它&#xff0c;0x80处就是今天要介绍的回调链表&#xff0c;但是先不着急&#xff0c;先把目光…...