排序算法学习记录-快速排序
快速排序
快速排序关键在于确定一个中间值,使得小于这个中间值的数在左边,大于这个中间值的数在右边。那么中间值该如何确定呢?有以下几种做法
- 首元素,也就是
arr[l]
- 尾元素,也就是
arr[r]
- 中间元素,也就是
arr[(l+r)>>1]
这里是位运算,等价于arr[(l+r)/2^1]
- 中间的一个随机元素
void Qsort(int arr[],int l,int r){if(l>=r) return;int begin = l,end = r,x = arr[(l+r)>>1];//上面是位运算,表示(l+r)/2^1while(begin<=end){while(arr[begin]<x) begin++;while(arr[end]>x) end--;if(begin<=end) swap(&arr[begin++],&arr[end--]);}Qsort(arr,l,end);Qsort(arr,begin,r);
}
//除了和x的比较不带=,其他的都带
快速排序相关变体
题目如下:
求第k大(小)的数,一种做法是堆排序把前k个数找出来就行,另一种就是利用快速排序的思想去做。现暂把中间的分界点称为pivot
,左边的数都小于pivot
,右边的数都大于pivot
。那么假如左边有m个数,右边有n个数。求第k大的数。如果k<n,那么这个数肯定在右边,反之这个数肯定在左边。以此来缩小这个数所在的范围。
归并排序
归并排序的核心思想在于将两个有序的数组合并为一个全局有序的数组。
int tmp[100000];
void merge_sort(int arr[],int begin,int end){if(begin>=end) return;int mid = (begin+end)>>1;merge_sort(arr,begin,mid);merge_sort(arr,mid+1,end);int l_begin = begin,r_begin = mid+1,tmp_index = 0;while(l_begin<=mid && r_begin<=end){if(arr[l_begin]<=arr[r_begin]) tmp[tmp_index++] = arr[l_begin++];else tmp[tmp_index++] = arr[r_begin++];}while(l_begin<=mid) tmp[tmp_index++] = arr[l_begin++];while(r_begin<=end) tmp[tmp_index++] = arr[r_begin++];int k = 0;while(begin<=end){arr[begin++] = tmp[k++];}
}
相关文章:

排序算法学习记录-快速排序
快速排序 快速排序关键在于确定一个中间值,使得小于这个中间值的数在左边,大于这个中间值的数在右边。那么中间值该如何确定呢?有以下几种做法 首元素,也就是arr[l]尾元素,也就是arr[r]中间元素,也就是ar…...
安装windows版本的ros2 humble的时候,最后报错
"[rti_connext_dds_cmake_module][warning] RTI Connext DDS environment script not found (\resource\scripts\rtisetenv_x64Win64VS2017.bat). RTI Connext DDS will not be available at runtime, unless you already configured PATH manually." 意思是没找到。…...

Nginx 学习(十)高可用中间件的配置与实现
一 Keepalived热备 1 概述 调度器出现单点故障,如何解决?Keepalived实现了高可用集群Keepalived最初是为LVS设计的,专门监控各服务器节点的状态Keepalived后来加入了VRRP功能,防止单点故障 2 运行原理 Keepalived检测每个服务器节点状…...

[刷题记录]牛客面试笔刷TOP101
牛客笔试算法必刷TOP101系列,每日更新中~ 1.合并有序链表2023.9.3 合并两个排序的链表_牛客题霸_牛客网 (nowcoder.com) 题意大致为: 将两个链表中的元素按照从小到大的顺序合并成为一个链表. 所给予的条件: 给出的所要合并的链表都是从小到大顺序排列的. 思路: 创建一…...
降水预报之双重惩罚
在降水预报中,通常会出现 "双重惩罚问题 "的指标或度量包括那些常用于预报验证的指标或度量。当假阴性(漏报降水事件)和假阳性(误报)受到同等惩罚或加权时,就会出现双重惩罚问题,这在…...
一条SQL语句的执行过程(附一次两段式提交)
一条SQL语句的完整执行过程是怎样的呢?我们用select和update语句来举例。 注意在mysql8后,进入服务层后,取消了去查询缓存(属于Server服务层)这个步骤,缓存中key是SQL语句,value是值,这样其实并不会提升性…...
Python基础知识详解:数据类型、对象结构、运算符完整分析
文章目录 python基础知识数据类型类型检查对象(object)对象的结构变量和对象类型转换运算符(操作符)1. 算术运算符2. 赋值运算符3. 比较运算符(关系运算符)4. 逻辑运算符5. 条件运算符(三元运算符) 总结 py…...

基于Streamlit的应用如何通过streamlit-authenticator组件实现用户验证与隔离
Streamlit框架中默认是没有提供用户验证组件的,大家在基于streamlit快速实现web应用服务过程中,不可避免的需要配置该应用的访问范围和权限,即用户群体,一般的做法有两种,一种是通过用户密码验证机制,要求只…...

[虚幻引擎插件介绍] DTGlobalEvent 蓝图全局事件, Actor, UMG 相互回调,自由回调通知事件函数,支持自定义参数。
本插件可以在虚幻的蓝图 Actor, Obiect,UMG 里面指定绑定和执行消息,可带自定义参数。 参数支持 Bool,Byte,Int,Int64,Float,Name,String,Text,Ve…...

2023数学建模国赛选题建议及BC题思路
大家好呀,全国大学生数学建模竞赛今天下午开赛啦,在这里先带来初步的选题建议及思路。 目前团队正在写B题和C题完整论文,后续还会持续更新哈,以下只是比较简略的图文版讲解,团队目前正在写B、C题完整论文,…...

vue3:4、组合式API-setup选项
setup每次都要return,好麻烦。怎么解决? 使用 <script setup> 语法糖(底层帮你return了) 写法如下...

【C刷题训练营】第三讲(c语言入门训练)
前言: 大家好,我决定日后逐渐更新c刷题训练营的内容,或许能帮到入门c语言的初学者,如果文章有错误,非常欢迎你的指正! 💥🎈个人主页:Dream_Chaser~ 🎈&…...

简述视频智能分析EasyCVR视频汇聚平台如何通过“AI+视频融合”技术规避八大特殊作业风险
视频智能分析EasyCVR视频汇聚平台可以根据不同的场景需求,让平台在内网、专网、VPN、广域网、互联网等各种环境下进行音视频的采集、接入与多端分发。在视频能力上,视频云存储平台EasyCVR可实现视频实时直播、云端录像、视频云存储、视频存储磁盘阵列、录…...

2023年9月NPDP产品经理国际认证报名,找弘博创新
产品经理国际资格认证NPDP是新产品开发方面的认证,集理论、方法与实践为一体的全方位的知识体系,为公司组织层级进行规划、决策、执行提供良好的方法体系支撑。 【认证机构】 产品开发与管理协会(PDMA)成立于1979年,是…...

【MySQL】MySQL的安装,登录,配置和相关命令
文章目录 前言一. 卸载不需要的环境二. 获取MySQL的yum源三. 安装MySQL和启动四. 尝试登录MySQL方法1:获取临时root密码方法2:没有密码方法3:配置文件 五. 简单配置结束语 前言 本篇文章是基于云服务器;Linux:Centos7…...

攻防世界-WEB-php_rce
打开靶机链接 搜村ThinkPhP V5存在远程命令执行的漏洞 构建payload /index.php?sindex/think\app/invokefunction&functioncall_user_func_array&vars[0]system&vars[1][]ls 查询当前目录文件,没有发现flag。调整payload 得到flag文件,修…...
WRFDA资料同化实践技术
数值预报已经成为提升预报质量的重要手段,而模式初值质量是决定数值预报质量的重要环节。资料同化作为提高模式初值质量的有效方法,成为当前气象、海洋和大气环境和水文等诸多领域科研、业务预报中的关键科学方法。资料同化新方法的快速发展,…...

C++11新特性② | 左值、左值引用、右值与右值引用
目录 1、引言 2、值类别及相关概念 3、左值、右值 4、左值引用、右值引用 5、移动语义 5.1、为什么需要移动语义 5.2、移动语义定义 5.3、转移构造函数 5.4、转移赋值函数 6、标准库函数 std::move 7、完美转发 std::forward VC常用功能开发汇总(专栏文章…...

Python Opencv实践 - Harris角点检测
参考资料:https://blog.csdn.net/wsp_1138886114/article/details/90415190 import cv2 as cv import numpy as np import matplotlib.pyplot as pltimg cv.imread("../SampleImages/chinease_tower.jpg", cv.IMREAD_COLOR) plt.imshow(img[:,:,::-1])#…...
el-upload上传图片到七牛云或阿里云
(1)绑定上传地址,上传数据对象 <el-upload class"upload-demo" :action"uploadUrl" :data"uploadData":on-success"handleSuccess" :file-list"[]" :show-file-list"false"…...

业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...

Maven 概述、安装、配置、仓库、私服详解
目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
C#学习第29天:表达式树(Expression Trees)
目录 什么是表达式树? 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持: 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...
MinIO Docker 部署:仅开放一个端口
MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...

基于PHP的连锁酒店管理系统
有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发,数据库mysql,前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...

AD学习(3)
1 PCB封装元素组成及简单的PCB封装创建 封装的组成部分: (1)PCB焊盘:表层的铜 ,top层的铜 (2)管脚序号:用来关联原理图中的管脚的序号,原理图的序号需要和PCB封装一一…...
Windows 下端口占用排查与释放全攻略
Windows 下端口占用排查与释放全攻略 在开发和运维过程中,经常会遇到端口被占用的问题(如 8080、3306 等常用端口)。本文将详细介绍如何通过命令行和图形化界面快速定位并释放被占用的端口,帮助你高效解决此类问题。 一、准…...

工厂方法模式和抽象工厂方法模式的battle
1.案例直接上手 在这个案例里面,我们会实现这个普通的工厂方法,并且对比这个普通工厂方法和我们直接创建对象的差别在哪里,为什么需要一个工厂: 下面的这个是我们的这个案例里面涉及到的接口和对应的实现类: 两个发…...