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

排序算法学习记录-快速排序

快速排序

快速排序关键在于确定一个中间值,使得小于这个中间值的数在左边,大于这个中间值的数在右边。那么中间值该如何确定呢?有以下几种做法

  • 首元素,也就是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++];}
}

相关文章:

排序算法学习记录-快速排序

快速排序 快速排序关键在于确定一个中间值&#xff0c;使得小于这个中间值的数在左边&#xff0c;大于这个中间值的数在右边。那么中间值该如何确定呢&#xff1f;有以下几种做法 首元素&#xff0c;也就是arr[l]尾元素&#xff0c;也就是arr[r]中间元素&#xff0c;也就是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 概述 调度器出现单点故障&#xff0c;如何解决?Keepalived实现了高可用集群Keepalived最初是为LVS设计的&#xff0c;专门监控各服务器节点的状态Keepalived后来加入了VRRP功能&#xff0c;防止单点故障 2 运行原理 Keepalived检测每个服务器节点状…...

[刷题记录]牛客面试笔刷TOP101

牛客笔试算法必刷TOP101系列,每日更新中~ 1.合并有序链表2023.9.3 合并两个排序的链表_牛客题霸_牛客网 (nowcoder.com) 题意大致为: 将两个链表中的元素按照从小到大的顺序合并成为一个链表. 所给予的条件: 给出的所要合并的链表都是从小到大顺序排列的. 思路: 创建一…...

降水预报之双重惩罚

在降水预报中&#xff0c;通常会出现 "双重惩罚问题 "的指标或度量包括那些常用于预报验证的指标或度量。当假阴性&#xff08;漏报降水事件&#xff09;和假阳性&#xff08;误报&#xff09;受到同等惩罚或加权时&#xff0c;就会出现双重惩罚问题&#xff0c;这在…...

一条SQL语句的执行过程(附一次两段式提交)

一条SQL语句的完整执行过程是怎样的呢&#xff1f;我们用select和update语句来举例。 注意在mysql8后&#xff0c;进入服务层后&#xff0c;取消了去查询缓存(属于Server服务层)这个步骤&#xff0c;缓存中key是SQL语句&#xff0c;value是值&#xff0c;这样其实并不会提升性…...

Python基础知识详解:数据类型、对象结构、运算符完整分析

文章目录 python基础知识数据类型类型检查对象&#xff08;object&#xff09;对象的结构变量和对象类型转换运算符(操作符)1. 算术运算符2. 赋值运算符3. 比较运算符&#xff08;关系运算符&#xff09;4. 逻辑运算符5. 条件运算符&#xff08;三元运算符&#xff09; 总结 py…...

基于Streamlit的应用如何通过streamlit-authenticator组件实现用户验证与隔离

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

[虚幻引擎插件介绍] DTGlobalEvent 蓝图全局事件, Actor, UMG 相互回调,自由回调通知事件函数,支持自定义参数。

本插件可以在虚幻的蓝图 Actor&#xff0c; Obiect&#xff0c;UMG 里面指定绑定和执行消息&#xff0c;可带自定义参数。 参数支持 Bool&#xff0c;Byte&#xff0c;Int&#xff0c;Int64&#xff0c;Float&#xff0c;Name&#xff0c;String&#xff0c;Text&#xff0c;Ve…...

2023数学建模国赛选题建议及BC题思路

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

vue3:4、组合式API-setup选项

setup每次都要return&#xff0c;好麻烦。怎么解决&#xff1f; 使用 <script setup> 语法糖&#xff08;底层帮你return了&#xff09; 写法如下...

【C刷题训练营】第三讲(c语言入门训练)

前言: 大家好&#xff0c;我决定日后逐渐更新c刷题训练营的内容&#xff0c;或许能帮到入门c语言的初学者&#xff0c;如果文章有错误&#xff0c;非常欢迎你的指正&#xff01; &#x1f4a5;&#x1f388;个人主页:​​​​​​Dream_Chaser&#xff5e; &#x1f388;&…...

简述视频智能分析EasyCVR视频汇聚平台如何通过“AI+视频融合”技术规避八大特殊作业风险

视频智能分析EasyCVR视频汇聚平台可以根据不同的场景需求&#xff0c;让平台在内网、专网、VPN、广域网、互联网等各种环境下进行音视频的采集、接入与多端分发。在视频能力上&#xff0c;视频云存储平台EasyCVR可实现视频实时直播、云端录像、视频云存储、视频存储磁盘阵列、录…...

2023年9月NPDP产品经理国际认证报名,找弘博创新

产品经理国际资格认证NPDP是新产品开发方面的认证&#xff0c;集理论、方法与实践为一体的全方位的知识体系&#xff0c;为公司组织层级进行规划、决策、执行提供良好的方法体系支撑。 【认证机构】 产品开发与管理协会&#xff08;PDMA&#xff09;成立于1979年&#xff0c;是…...

【MySQL】MySQL的安装,登录,配置和相关命令

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

攻防世界-WEB-php_rce

打开靶机链接 搜村ThinkPhP V5存在远程命令执行的漏洞 构建payload /index.php?sindex/think\app/invokefunction&functioncall_user_func_array&vars[0]system&vars[1][]ls 查询当前目录文件&#xff0c;没有发现flag。调整payload 得到flag文件&#xff0c;修…...

WRFDA资料同化实践技术

数值预报已经成为提升预报质量的重要手段&#xff0c;而模式初值质量是决定数值预报质量的重要环节。资料同化作为提高模式初值质量的有效方法&#xff0c;成为当前气象、海洋和大气环境和水文等诸多领域科研、业务预报中的关键科学方法。资料同化新方法的快速发展&#xff0c;…...

C++11新特性② | 左值、左值引用、右值与右值引用

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

Python Opencv实践 - Harris角点检测

参考资料&#xff1a;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上传图片到七牛云或阿里云

&#xff08;1&#xff09;绑定上传地址&#xff0c;上传数据对象 <el-upload class"upload-demo" :action"uploadUrl" :data"uploadData":on-success"handleSuccess" :file-list"[]" :show-file-list"false"…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

沙箱虚拟化技术虚拟机容器之间的关系详解

问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西&#xff0c;但是如果把三者放在一起&#xff0c;它们之间到底什么关系&#xff1f;又有什么联系呢&#xff1f;我不是很明白&#xff01;&#xff01;&#xff01; 就比如说&#xff1a; 沙箱&#…...

热烈祝贺埃文科技正式加入可信数据空间发展联盟

2025年4月29日&#xff0c;在福州举办的第八届数字中国建设峰会“可信数据空间分论坛”上&#xff0c;可信数据空间发展联盟正式宣告成立。国家数据局党组书记、局长刘烈宏出席并致辞&#xff0c;强调该联盟是推进全国一体化数据市场建设的关键抓手。 郑州埃文科技有限公司&am…...

Visual Studio Code 扩展

Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后&#xff0c;命令 changeCase.commands 可预览转换效果 EmmyLua…...

前端调试HTTP状态码

1xx&#xff08;信息类状态码&#xff09; 这类状态码表示临时响应&#xff0c;需要客户端继续处理请求。 100 Continue 服务器已收到请求的初始部分&#xff0c;客户端应继续发送剩余部分。 2xx&#xff08;成功类状态码&#xff09; 表示请求已成功被服务器接收、理解并处…...

【大模型】RankRAG:基于大模型的上下文排序与检索增强生成的统一框架

文章目录 A 论文出处B 背景B.1 背景介绍B.2 问题提出B.3 创新点 C 模型结构C.1 指令微调阶段C.2 排名与生成的总和指令微调阶段C.3 RankRAG推理&#xff1a;检索-重排-生成 D 实验设计E 个人总结 A 论文出处 论文题目&#xff1a;RankRAG&#xff1a;Unifying Context Ranking…...

网页端 js 读取发票里的二维码信息(图片和PDF格式)

起因 为了实现在报销流程中&#xff0c;发票不能重用的限制&#xff0c;发票上传后&#xff0c;希望能读出发票号&#xff0c;并记录发票号已用&#xff0c;下次不再可用于报销。 基于上面的需求&#xff0c;研究了OCR 的方式和读PDF的方式&#xff0c;实际是可行的&#xff…...

【汇编逆向系列】六、函数调用包含多个参数之多个整型-参数压栈顺序,rcx,rdx,r8,r9寄存器

从本章节开始&#xff0c;进入到函数有多个参数的情况&#xff0c;前面几个章节中介绍了整型和浮点型使用了不同的寄存器在进行函数传参&#xff0c;ECX是整型的第一个参数的寄存器&#xff0c;那么多个参数的情况下函数如何传参&#xff0c;下面展开介绍参数为整型时候的几种情…...