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

快速排序笔记

一、quick_sort方法中如果 i=l,j=r 会死循环的分析

1、示例代码

void quick_sort(int a[],int l,int r){if(l>=r) return;int i=l,j=r; //此处设置会导致死循环int x = num[(l+r)>>1];while(i<j){while(a[++i] <x); //死循环的地方while(a[--j] >x);if(i<j) swap(a[i],a[j]);}quick_sort(a,l,j);quick_sort(a,j+1,r);
}

2、代码分析

因为数组a默认值都是,i的坐标越过了选中的数x ,并且x往后的数都小于0或者没有明确赋值(此种情况为0)此后a[i]的值都会小于x,导致死循环。而
while(a[--j] >x); 就不会导致因为j往左移终究会变成没有明确赋值的0,所以循环会结束。

3、示例

假如就两个数 98 97,i=1(值97,i坐标往右移动,值变成0,始终小于选出来的数98,导致死循环)

4、心得

算法当中有很多默认值的地方,比如此处的数组a的未明确下标的值都为0,为一个隐含条件,可以帮忙判断是否发生死循环。

二、无限划分的分析

1、重要结论

当以i划分区间,选数不能选到左边界,则a[x] = a[(L+R+1)>>1]
当以j划分区间,选数不能选到右边界,则a[x]=a[(L+R)>>1]

2、逻辑分析

假设选的数是a[x] ,退出循环时,a[l] …a[i-1] 都是a[x];a[j+1]…a[r] 都是>x,a[j]<a[x][x],a[i]>
image-20230826164400548

3、示例

以3 1 2 5 4 这个五个数排序为例:
image-20230826161149245

4、心得

退出循环时的条件判断,有些退出循环时的条件很明确,比如以i划分,选数为L时,退出循环时i=L,但是j就不确定,只能是比L小的某一个位置。对于明确的位置是算法中一些重要判断的条件。

相关文章:

快速排序笔记

一、quick_sort方法中如果 il,jr 会死循环的分析 1、示例代码 void quick_sort(int a[],int l,int r){if(l>r) return;int il,jr; //此处设置会导致死循环int x num[(lr)>>1];while(i<j){while(a[i] <x); //死循环的地方while(a[--j] >x);if(i<j) swap(a…...

JAVA:(JSON反序列化Long变成了Integer)java.lang.Integer cannot be cast to java.lang.Long

困扰了好几个小时。。。 场景&#xff1a;mybatisplus从数据库取数据&#xff0c;只是用了最基础的 LambdaQueryWrapper 来查询&#xff0c;实体类如下。 TableField(typeHandler JacksonTypeHandler.class) private Set<Long> ids; 得到的Set数据却是Set<Integer…...

ui设计师简历自我评价(合集)

UI设计最新面试题及答案 1、说说你是怎么理解UI的? UI是最直观的把产品展示展现在用户面前的东西&#xff0c;是一个产品的脸面。人开始往往是先会先喜欢上美好的事物后&#xff0c;在去深究内在的东西的。 那么也就意味着一个产品的UI首先要做的好看&#xff0c;无论风格是…...

Nginx 反向代理

一. Nginx 反向代理 1.1 反向代理介绍 在计算机网络中&#xff0c;反向代理一般指代理服务器&#xff0c;其首先代替内网的服务器接收客户端请求 并从一个或多个服务器检索资源&#xff0c;然后将这些资源返回给客户端。在客户端看来&#xff0c;这些资 源就好像来自代理服务…...

[论文阅读笔记25]A Comprehensive Survey on Graph Neural Networks

这是一篇GNN的综述, 发表于2021年的TNNLS. 这篇博客旨在对GNN的基本概念做一些记录. 论文地址: 论文 1. 引言, 背景与定义 对于图像数据来说, CNN具有平移不变性和局部连接性, 因此可以在欧氏空间上良好地学习. 然而, 对于具有图结构的数据(例如社交网络 化学分子等)就需要用…...

iview时间控件 动态不可选日期 可选择24小时范围内 时间往后退24小时

演示 html 设定 起始时间 触发on-change 方法结束时间 options 动态设置不可选择的日期。 <!-- 起始时间 --> <FormItem :label"$t(startTime)" prop"startTime"><DatePickertransfertype"datetime":placeholder"$t(pleas…...

Rest学习环境搭建:服务消费者

建一个子模块 导入依赖 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apache…...

JVM内存模型介绍

内存模型 内存模型如下图所示 堆 堆是Java虚拟机所管理的内存最大一块。堆是所有线程共享的一块内存区域&#xff0c;在虚拟机启动时创建。此内存区域唯一的目的就是存放对象实例。所有的对象实例都在这里分配内存 Java堆是垃圾收集器管理的主要区域。从内存回收的角度来看&am…...

2000-2021年地级市产业升级、产业结构高级化面板数据

2000-2021年地级市产业升级、产业结构高级化面板数据 1、时间&#xff1a;2000-2021年 2、范围&#xff1a;地级市 3、指标&#xff1a;年份、地区、行政区划代码、地区、所属省份、地区生产总值、第一产业增加值、第二产业增加值、第三产业增加值、第一产业占GDP比重、第二…...

Java实现密码加密实现步骤【bcrypt算法】

一、SpringBoot和SSM框架均可实现密码加密的方法 在Spring Boot和SSM中实现密码加密可以使用bcrypt算法。bcrypt是一种密码哈希函数&#xff0c;通过将密码与随机生成的盐值进行混合&#xff0c;然后再进行多次迭代的计算&#xff0c;最终生成一个安全的哈希密码。 下面是使用…...

商城-学习整理-集群-K8S(二十三)

目录 一、k8s 集群部署1、k8s 快速入门1&#xff09;、简介2&#xff09;、架构1、整体主从方式2、Master 节点架构3、Node 节点架构 3&#xff09;、概念4&#xff09;、快速体验1、安装 minikube2、体验 nginx 部署升级 5&#xff09;、流程叙述 2、k8s 集群安装1、kubeadm2、…...

MATLAB算法实战应用案例精讲-【深度学习】强化学习

目录 基础知识点 马尔科夫决策过程 策略梯度定理 蒙特卡洛策略梯度定理 REINFORCE 算法...

时间和日期--Python

1. 时间&#xff1a;time模块 总结&#xff1a;2. datetime模块 相比与time模块&#xff0c;datetime模块的接口更直观、更容易调用 2.1 datetime模块定义的类 &#xff08;1&#xff09;datetime.date:表示日期的类。常用的属性有&#xff1a;year、month、day; &#xff…...

【Git】学习总结

【Git】学习总结 【一】安装【二】Git克隆项目代码【1】idea下载git项目【2】创建新的分支【3】新建的分支推送到远程【4】合并最新代码到主分支【5】切换分支 【三】提交本地项目到远程&#x1f680;1. 配置 Git&#x1f680;2. 创建项目远程仓库&#x1f680;3. 初始化本地仓…...

手写Spring源码——实现一个简单的spring framework

这篇文章主要带大家实现一个简单的Spring框架&#xff0c;包含单例、多例bean的获取&#xff0c;依赖注入、懒加载等功能。文章内容会持续更新&#xff0c;感兴趣的小伙伴可以持续关注一下。 目录 一、创建Java项目 二、开始实现Spring 1、创建BeanFactory接口 2、创建Appl…...

银河麒麟服务器、centos7服务器一键卸载mysql脚本

脚本 # 查看mysql相关的rpm包写到rmsql.sh文件中 rpm -aq | grep -i mysql >rmsql.sh # 修改文件为卸载mysql的脚本文件 sed -i -e s/^/yum remove -y / rmsql.sh # 修改文本权限 chmod 777 rmsql.sh # 全盘查找mysql相关文件&#xff0c;写到my.sh脚本中 find / -name mysq…...

【随笔】- 程序员的40岁后健身计划

【随笔】- 40岁后程序员的健身计划 文章目录 【随笔】- 40岁后程序员的健身计划一、树立健身信心&#xff0c;制订坚持计划二、挑选让你舒适的方式三、调整速度&#xff0c;以间歇式训练为主四、刚开始锻炼&#xff0c;别求太快五、增加力量、柔韧性和平衡练习六、运动多样化七…...

后端项目开发:集成Druid数据源

Druid作为连接池中间件可以监控数据库访问性能&#xff0c;对数据库密码加密&#xff0c;查看SQL执行日志&#xff0c;扩展JDBC。 添加依赖 <!-- druid --> <dependency><groupId>com.alibaba</groupId><artifactId>druid-spring-boot-starter&…...

深度学习11:Transformer

目录 什么是 Transformer&#xff1f; Encoder Decoder Attention Self-Attention Context-Attention 什么是 Transformer&#xff08;微软研究院笨笨&#xff09; RNN和Transformer区别 Universal Transformer和Transformer 区别 什么是 Transformer&#xff1f; ​ …...

免费开源跨平台视频下载器 支持数百站点视频和音频下载-ytDownloader

ytDownloader&#xff1a; ytDownloader是一款免费开源跨平台视频下载器&#xff0c;帮助用户从数百个网站下载不同格式的视频和提取音频&#xff0c;使用简单&#xff0c;复制视频链接粘贴即可下载&#xff0c;支持4K画质视频下载&#xff0c;支持Linux、Windows 和 macOS平台…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

实现弹窗随键盘上移居中

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

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...