快速排序+快速定位
快速排序算法采用了分治法以及递归作为解决问题的思想。在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。
快速排序算法
算法思路
快速排序算法的思路是,先在arr[s,t]中随意选取一个点作为排序的基准点x,再确定基准点在数组中的下标,一定下标i确定后,该下标i左边的所有元素均小于x,右边的所有元素均大于x.此时采用递归继续对数组[s,i-1]以及[i+1,t]做快速排序,左右区间不再合法即可退出循环。分治的思想就体现在同时对基准点的左右区间再次做快速排序上。
找基准点
首先,姑且认为区间左端的第一个元素就是基准点x,再定义两个下标i与j分别记录区间的原始左端点与右端点,先从右端点开始往左查找,如果arr[j]>=x且i<j,则j--,这样能够确保基准点右边的元素都大于或等于基准点;若遇到arr[j]<x,则将arr[j]放到基准点原来的位置;紧接着下标i往右查找,如果arr[i]<=x且i<j,则i++,这样能够保障基准点左边的元素都小于或等于基准点;若遇到arr[i]>x,则将arr[i]放到上次j的位置;重复上述操作,直到i==j,将基准点放在arr[i]上,即arr[i]=x.
代码实现
#include<iostream>
using namespace std;
#include<algorithm>//快速查找算法,查找第k小的元素void quick_sort(int*arr,int l,int r){//递归退出条件if(l>=r){return ;}int i = l;int j = r;//以区间最左侧的元素最为基准点int x = arr[l];//调整基准点while(i<j){//找到一个比基准点小的数while(i<j && arr[j]>=x) j--;if(i<j){//将arr[j]放到最左边arr[i] = arr[j];} //找一个比基准点大的数while(i<j && arr[i]<=x) i++;if(i<j){arr[j] = arr[i];}} arr[i] = x;//调整基准点//对基准点的左区间排序quick_sort(arr,l,i-1);//对基准点的右区间排序quick_sort(arr,i+1,r);
}
void Myprint(int val){cout<<val<<" ";
}int main(){int arr[12]={10,2,1,3,6,5,4,7,9,8,42,99};int len = sizeof(arr)/sizeof(int);quick_sort(arr,0,len-1);for_each(arr,arr+len,Myprint);cout<<endl;return 0;
}快速定位算法
问题引入
已知定长为len的int数组,需要查出第k小的元素。
算法思路
借鉴快速排序的思路,基准点必定大于或等于其左区间的元素,小于或等于右区间的元素,因此找到一个下标为k-1的基准点等价于找到第k小的元素。我们只需要在原快速排序算法删改一些代码即可获得快速排序算法的代码实现。
代码实现
#include<iostream>
using namespace std;//快速查找算法,查找第k小的元素int quick_select(int*arr,int l,int r, int k){int i = l;int j = r;//以区间左端点为基准点int x = arr[l];//调整基准点while(i<j){//找到一个比基准点小的数while(i<j && arr[j]>=x) j--;if(i<j){//将arr[j]放到最左边arr[i] = arr[j];} //找一个比基准点大的数while(i<j && arr[i]<=x) i++;if(i<j){arr[j] = arr[i];}} arr[i] = x;//调整基准点//判断基准点x的下标i是否与k-1相同if(i==k-1) return arr[i];else if(i<k-1)return quick_select(arr,i+1,r,k);elsereturn quick_select(arr,l,i-1,k);
}int main(){int arr[12]={10,2,1,3,6,5,4,7,9,8,42,99};int k = 12;int len = sizeof(arr)/sizeof(int);cout<<quick_select(arr,0,len-1,k)<<endl;//答案无疑是99return 0;
}可见,当i<k-1时,说明第k小的元素在基准点的右侧,只需要再查找基准点的右侧区间;当i>k-1时,说明第k小的元素在基准点的左侧,只需要再查找基准点的左侧区间
相关文章:
快速排序+快速定位
快速排序算法采用了分治法以及递归作为解决问题的思想。在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以…...
nginx http rewrite module 详解
大家好,我是 17。 今天和大家聊聊 nginx http rewrite module 。 简单来说, ngx_http_rewrite_module module 用正则匹配请求,改写请求,然后做跳转。可以是内部跳转,也可以是外部跳转。 学习这个模块的时候…...
机器学习可解释性一(LIME)
随着深度学习的发展,越来越多的模型诞生,并且在训练集和测试集上的表现甚至于高于人类,但是深度学习一直被认为是一个黑盒模型,我们通俗的认为,经过训练后,机器学习到了数据中的特征,进而可以正…...
CV学习笔记-MobileNet
MobileNet 文章目录MobileNet1. MobileNet概述2. 深度可分离卷积(depthwise separable convolution)2.1 深度可分离卷积通俗理解2.2 深度可分离卷积对于参数的优化3. MobileNet网络结构4. 代码实现4.1 卷积块4.2 深度可分离卷积块4.3 MobileNet定义4.4 完…...
C++进阶——继承
C进阶——继承 1.继承的概念及定义 面向对象三大特性:封装、继承、多态。 概念: 继承(inheritance)机制是面向对象程序设计使代码可以复用的最重要的手段,它允许程序员在保持原有类特 性的基础上进行扩展,增加功能,这…...
数据结构---单链表
专栏:数据结构 个人主页:HaiFan. 专栏简介:从零开始,数据结构!! 单链表前言顺序表的缺陷链表的概念以及结构链表接口实现打印链表中的元素SLTPrintphead->next!NULL和phead!NULL的区别开辟空间SLTNewNod…...
redis数据结构的底层实现
文章目录一.引言二.redis的特点三.Redis的数据结构a.字符串b.hashc.listd.sete.zset(有序集合)一.引言 redis是一个开源的使用C语言编写、支持网络、可基于内存亦可持久化的日志型、key-value的NoSQL数据库。 通常使用redis作为缓存中间件来降低数据库的压力,除此…...
【JavaSE】复习(进阶)
文章目录1.final关键字2.常量3.抽象类3.1概括3.2 抽象方法4. 接口4.1 接口在开发中的作用4.2类型和类型之间的关系4.3抽象类和接口的区别5.包机制和import5.1 包机制5.2 import6.访问控制权限7.Object7.1 toString()7.2 equals()7.3 String类重写了toString和equals8.内部类8.1…...
Java 主流日志工具库
日志系统 java.util.logging (JUL) JDK1.4 开始,通过 java.util.logging 提供日志功能。虽然是官方自带的log lib,JUL的使用确不广泛。 JUL从JDK1.4 才开始加入(2002年),当时各种第三方log lib已经被广泛使用了JUL早期存在性能问题&#x…...
产品经理有必要考个 PMP吗?(含PMP资料)
现在基本上做产品的都有一个PMP证件,从结果导向来说,不对口不会有这么大范围的人来考,但是需要因地制宜,在公司内部里,标准程序并不流畅,产品和项目并不规范,关系错综复杂。 而产品经理的职能又…...
什么是原型、原型链?原型和原型链的作用
1、ES6之前,继承都用构造函数来实现;对象的继承,先申明一个对象,里面添加实例成员<!DOCTYPE html> <html><head><meta charset"utf-8" /><title></title></head><body><script…...
条件期望4
条件期望例题----快排算法的分析 快速排序算法的递归定义如下: 有n个数(n≥2n\geq 2n≥2), 一开始随机选取一个数xix_ixi, 并将xix_ixi和其他n-1个数进行比较, 记SiS_iSi为比xix_ixi小的元素构成的集合, Siˉ\bar{S_i}Siˉ为比xix_ixi大的元素构成的集合, 然后分…...
网络协议分析(2)判断两个ip数据包是不是同一个数据包分片
一个节点收到两个IP包的首部如下:(1)45 00 05 dc 18 56 20 00 40 01 bb 12 c0 a8 00 01 c0 a8 00 67(2)45 00 00 15 18 56 00 b9 49 01 e0 20 c0 a8 00 01 c0 a8 00 67分析并判断这两个IP包是不是同一个数据报的分片&a…...
6.2 负反馈放大电路的四种基本组态
通常,引入交流负反馈的放大电路称为负反馈放大电路。 一、负反馈放大电路分析要点 如图6.2.1(a)所示电路中引入了交流负反馈,输出电压 uOu_OuO 的全部作为反馈电压作用于集成运放的反向输入端。在输入电压 uIu_IuI 不变的情况下,若由于…...
MySQL进阶之锁
锁是计算机中协调多个进程或线程并发访问资源的一种机制。在数据库中,除了传统的计算资源竞争之外,数据也是一种提供给许多用户共享的资源,如何保证数据并发访问的一致性和有效性是数据库必须解决堆的一个问题,锁冲突也是影响数据…...
【Mac 教程系列】如何在 Mac 上破解带有密码的 ZIP 压缩文件 ?
如何使用 fcrackzip 在 Mac 上破解带有密码的 ZIP 压缩文件? 用 markdown 格式输出答案。 在 Mac 上破解带有密码的 ZIP 压缩文件 使用解压缩软件,如The Unarchiver,将文件解压缩到指定的文件夹。 打开终端,输入 zip -er <zipfile> &…...
【Acwing 周赛复盘】第92场周赛复盘(2023.2.25)
【Acwing 周赛复盘】第92场周赛复盘(2023.2.25) 周赛复盘 ✍️ 本周个人排名:1293/2408 AC情况:1/3 这是博主参加的第七次周赛,又一次体会到了世界的参差(这次周赛记错时间了,以为 19:15 开始&…...
L1-087 机工士姆斯塔迪奥
在 MMORPG《最终幻想14》的副本“乐欲之所瓯博讷修道院”里,BOSS 机工士姆斯塔迪奥将会接受玩家的挑战。 你需要处理这个副本其中的一个机制:NM 大小的地图被拆分为了 NM 个 11 的格子,BOSS 会选择若干行或/及若干列释放技能,玩家…...
本周大新闻|索尼PS VR2立项近7年;传腾讯将引进Quest 2
本周大新闻,AR方面,传立讯精密开发苹果初代AR头显,第二代低成本版将交给富士康;iOS 16.4代码曝光新的“计算设备”;EM3推出AR眼镜Stellar Pro;努比亚将在MWC2023推首款AR眼镜。VR方面,传闻腾讯引…...
aws console 使用fargate部署aws服务快速跳转前端搜索栏
测试过程中需要在大量资源之间跳转,频繁的点击不如直接搜索来的快,于是写了一个搜索框方便跳转。 前端的静态页面可以通过s3静态网站托管实现,但是由于中国区需要备案的原因,可以使用ecs fargate部署 步骤如下: 编写…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
