【快排与归并排序算法】
作者:指针不指南吗
专栏:算法篇🐾或许会很慢,但是不可以停下🐾
文章目录
- 一、快速排序 ( Quick Sort )
- 二、归并排序 ( Merge Sort )
- 总结
一、快速排序 ( Quick Sort )
1.思路
- 找出一个分界点,随机的
- 调整区间
分治,双指针,指向两边,往中间走,遇到不满足条件的停下,直到两者都遇到不满足条件的,交换位置,直到两个指针相遇- 递归处理两段
分治
三步曲:分成子问题,解决子问题,子问题合并成大问题

- 代码模板
void quick_sort (int q [ ] , int l , int r )
{if (l>= r) return ; //区间个数为 1,或者 0,返回int i =l-1;j=r+1;x=q[l+r>>1]; // i指左边, j指最右边,范围大点,要包含 l , r while(i<=j){do i++;while(q[i]>x); //指针移动,直到出现不满足条件的情况do j--;while(q[j]<x);if(i<j) swap(q[i],q[j]; //找到 2个,交换}quick_sort(q,l,j),quick_sort(q,j+1,r); //递归}
二、归并排序 ( Merge Sort )
1.思路
- 确定一个分界点
- 递归排序
- 合二为一
分成两组数据,然后两组数据从最小的比较,谁小放在temp数组,,其中一组数据已经走完了,另一组还剩着,把剩余的放在temp数组后面,最后temp 赋值给 q 即原始数组
2.代码模板
void merge_sort(int q[],int l,int r)
{if(l>=r) return ; //区间只有一个元素或没有,返回 int mid=l+r>>1; //确定中间值 merge_sort(q,l,mid),merge_sort(q,mid+1,r); //递归排序 int i=l,j=mid+1,k=0;while(i<=mid&&j<=r){if(q[i]<=q[j]) temp[k++]=q[i++]; //谁小,谁就先存储在temp中 else temp[k++]=q[j++];}while(i<=mid) temp[k++]=q[i++]; //谁有剩余即其数大,存储在temp后面 while(j<=r) temp[k++]=q[j++];for(int i=l,j=0;i<=r;i++,j++) q[i]=temp[j]; //拷贝到原数组
}
总结
快排和归并排序💭
- 思路上
快排是先处理两边,再递归
归并是先递归,在处理两边
- 时间复杂度上
快排 和 归并排序 的时间复杂度都是 O(log2nlog_{2}nlog2n )
- 快排平均 O(log2nlog_{2}nlog2n ),最坏情况可以达到 O(n2n^2n2)
- 归并排序的最坏和最好情况都是 O(log2nlog_{2}nlog2n )
相关文章:
【快排与归并排序算法】
作者:指针不指南吗 专栏:算法篇 🐾或许会很慢,但是不可以停下🐾 文章目录一、快速排序 ( Quick Sort )二、归并排序 ( Merge Sort )总结一、快速排序 ( Quick Sort ) 1.思路 找出一个分界点,随机的调整区间…...
面试官问我:说说你对JMM内存模型的理解?为什么需要JMM?
点个关注,必回关 随着CPU和内存的发展速度差异的问题,导致CPU的速度远快于内存,所以现在的CPU加入了高速 缓存,高速缓存一般可以分为L1、L2、L3三级缓存。基于上面的例子我们知道了这导致了缓存一致 性的问题,所以加入…...
工程管理系统源码之提高工程项目管理软件的效率
高效的工程项目管理软件不仅能够提高效率还应可以帮你节省成本提升利润 在工程行业中,管理不畅以及不良的项目执行,往往会导致项目延期、成本上升、回款拖后,最终导致项目整体盈利下降。企企管理云业财一体化的项目管理系统,确保…...
SpringBoot集成xxl-job实现
SpringBoot集成xxl-job实现 一、xxl-job介绍 xxl-job是一个分布式任务调度平台,核心设计目标是开发迅速、学习简单、轻量级、易扩展。源码:下载地址编译环境:Maven3、Jdk1.8、MySQL5.7 二、调度中心 初始化调度数据库,执行指定…...
欧几里得度量和余弦度量的可取消生物识别方案
欧几里得度量和余弦度量的可取消生物识别方案 便捷的生物识别数据是一把双刃剑,在为生物识别认证系统的繁荣铺平道路的同时,也带来了个人隐私问题。为了缓解这种担忧,提出了各种生物特征模板保护方案来保护生物特征模板免于信息泄露。现有提案…...
平板作为主机扩展屏的实现
网上有许多教程使用平板作为电脑的拓展屏,但是多数都是需要在电脑和平板上都装上服务器和客户端的软件才行,而且有些系统还没有对应的软件。 那有没有一种方法只需要在主机上运行一个软件,而平板上只需要扫个码就行呢? 答案是当然…...
HTTP和HTTPS有什么区别?如何实现网站的HTTPS?
细心的朋友会发现,我们在浏览网站时,有的网址以http开头,而有的网站却以https开头,那这两者之间有什么区别吗?http的网站如何能变成https呢?本文中科三方针对这个问题做下简单介绍。 什么是http࿱…...
Rockstar Games遭黑客攻击,《侠盗猎车手6》90个开发视频外泄
当地时间9月19日,视频游戏开发商Rockstar Games证实,其 热门游戏《侠盗猎车手6》(Grand Theft Auto)开发片段遭到黑客大规模窃取 ,这一泄露事件立即在游戏圈迅速传播。 据报道, 上周末黑客至少泄露了90个游…...
RabbitMQ-客户端源码之AMQPImpl+Method
AMQPImpl类包括AMQP接口(public class AMQImpl implements AMQP)主要囊括了AMQP协议中的通信帧的类别。 这里以Connection.Start帧做一个例子。 public static class Connection {public static final int INDEX 10;public static class Startextends…...
雅思经验(7)
我发现雅思阅读要命的不是难度,而是时间的把控。考试时间是总共一小时,但是要写三篇文章,之后总共40道题目,也就是说每篇文章平均是13.3道。但是他们很多人说,如果誊写答案需要花掉3、4分钟每篇,也就是说真…...
Ubuntu20.04 用 `hwclock` 或 `timedatectl` 设置RTC硬件时钟为本地时区
Ubuntu20.04用 hwclock 或 timedatectl 设置硬件时区为本地时区 可以用hwclock命令 sudo hwclock --localtime --systohc👆效果等同👇 , --localtime的简写是-l ; --systohc的简写是-w sudo hwclock -l -w也可以用timedatectl命令 👆效果等…...
大学物理·第15章【量子物理】
黑体 斯特藩玻耳兹曼定律 维恩定律 光电效应 在光照射下 ,电子从金属表面逸出的现象,叫光电效应. 逸出的电子,叫光电子 经典理论: 光电流值与入射光强成正比截止频率(红限)v0对某种金属来说,只有…...
2010-2019年290个地级市经济发展与城市绿化数据
2010-2019年290个地级市经济发展与城市绿化数据 1、时间:2010-2019年 2、来源:城市统计NJ,缺失情况与NJ一致 3、范围:290个地级市 4、指标: 综合经济:地区生产总值、人均地区生产总值、地区生产总值增…...
【CSS 布局】-多列布局
一、两列布局 两列布局:一列定宽(也有可能由子元素决定宽度),一列自适应的布局。 创建一个父盒子,和子盒子 <div class"container clearfix"><div class"left ">定宽</div><div class"right…...
从C语言向C++过渡
文章目录前言1.命名空间1.域的概念2.命名空间的使用2.C输入&输出3.缺省参数1.概念2.分类3.注意事项4.函数重载5.引用1.概念2.使用注意事项3.引用使用场景4.指针和引用的区别6.内联函数7.auto关键字8.nullptr前言 C被成为带类的C,本文由C语言向C过度,将会初步介…...
Matter 研讨会回顾(第三期)|乐鑫 Matter 免开发方案与证书服务介绍
1 月 17 日,乐鑫举办了以“乐鑫 Matter 免开发方案与证书服务介绍”为主题的第三期 Matter 线上研讨会,介绍乐鑫开箱即用的 ESP-ZeroCode 模组及其免开发 Matter 方案,以及证书生成和预配置相关服务。欢迎观看研讨会的视频回放了解详情。&…...
函数栈帧的创建和销毁——“C”
各位CSDN的uu们你们好呀,今天小雅兰来为大家介绍一个知识点——函数栈帧的创建和销毁。其实这个知识点,我们很早之前就要讲,但是因为我的一系列原因,才一直拖到了现在,那么,话不多说,让我们一起…...
腾讯云对象存储+企业网盘 打通数据链“最后一公里
对云厂商和企业用户来说,随着数据规模的快速增长,企业除了对存储功能和性能的要求不断增加,也越来越注重数据分发的效率。在传统数据分发的过程中,数据管理员往往需要先在存储桶下载对应的客户方案/交付资料,再使用微信…...
在浏览器输入url到发起http请求,这过程发生了什么
当用户输入url,操作系统会将输入事件传递到浏览器中,在这过程中,浏览器可能会做一些预处理,比如 Chrome 会根据历史统计来预估所输入字符对应的网站,例如输入goog,根据之前的历史发现 90% 的概率会访问「ww…...
PyTorch学习笔记:nn.ReLU——ReLU激活函数
PyTorch学习笔记:nn.ReLU——ReLU激活函数 torch.nn.ReLU(inplaceFalse)功能:逐元素应用ReLU函数对数据进行激活 函数方程: ReLU(x)(x)max(0,x)ReLU(x)(x)^\max(0,x) ReLU(x)(x)max(0,x) 输入: inplace:是否改变输…...
终极Markdown Viewer:5分钟打造你的浏览器技术文档阅读器
终极Markdown Viewer:5分钟打造你的浏览器技术文档阅读器 【免费下载链接】markdown-viewer Markdown Viewer / Browser Extension 项目地址: https://gitcode.com/gh_mirrors/ma/markdown-viewer 你是否厌倦了在浏览器中查看Markdown文件时格式混乱的体验&a…...
终极指南:如何在ComfyUI中掌握IPAdapter Plus图像风格迁移技术
终极指南:如何在ComfyUI中掌握IPAdapter Plus图像风格迁移技术 【免费下载链接】ComfyUI_IPAdapter_plus 项目地址: https://gitcode.com/gh_mirrors/co/ComfyUI_IPAdapter_plus 在AI图像生成领域,ComfyUI IPAdapter Plus插件正在成为图像风格迁…...
专科ENSP毕设实战:基于eNSP的校园网高可用架构设计与配置避坑指南
最近在帮几个专科的学弟学妹看他们的eNSP毕业设计,发现大家普遍卡在几个地方:拓扑画得挺漂亮,但一配置就各种不通;协议背得滚瓜烂熟,但实际命令敲下去就报错;最后答辩演示时,一拔线整个网络就瘫…...
从MATLAB算法到MiniCPM-V-2_6模型:科学计算与AI的融合实践
从MATLAB算法到MiniCPM-V-2_6模型:科学计算与AI的融合实践 如果你经常和MATLAB打交道,可能会遇到这样的场景:跑完一个复杂的仿真,生成了几十张图表和一堆数据,然后需要花上半天时间,手动整理结果、撰写分析…...
VINS_Fusion轨迹评估实战:如何用evo工具搞定MH_01_easy数据集测试(附完整代码修改指南)
VINS_Fusion轨迹精度评估全流程:从数据准备到evo工具深度解析 1. 环境配置与工具准备 在开始评估VINS_Fusion的轨迹精度之前,我们需要确保开发环境已经正确配置。以下是必要的准备工作: 基础环境要求: Ubuntu 18.04/20.04 LTS&…...
采购管理系统:为企业实现降本增效、强化供应链韧性
在数字化浪潮下,采购管理已从传统的成本中心演变为企业的战略职能和价值引擎。选择一款合适的采购管理软件,对于企业实现降本增效、强化供应链韧性、赋能战略决策至关重要。本文将为您盘点市场上主流的五款采购管理软件,深入剖析其核心能力。…...
Android 11 自动亮度算法优化与曲线配置解析
1. Android 11自动亮度技术演进 记得第一次用上Android 11的手机时,最让我惊喜的就是屏幕亮度调节变得特别"聪明"。以前在电影院掏出手机总被刺得睁不开眼,现在却能像人眼一样自然地适应环境。这背后其实是Google对自动亮度算法做了重大升级&a…...
IEEE论文LaTeX排版技巧(十一)| 尾页双栏平衡优化实战指南
1. 为什么尾页双栏平衡如此重要? 当你熬夜改完论文准备提交时,有没有发现最后一页的两栏长度总是不对称?左边栏挤得满满当当,右边栏却空出一大截,这种视觉上的不平衡会直接影响评审专家对你论文的第一印象。我在审阅学…...
Qwen3-0.6B-FP8高性能推理:FP8量化不损质量,数学/代码生成保持SOTA
Qwen3-0.6B-FP8高性能推理:FP8量化不损质量,数学/代码生成保持SOTA 最近在部署大模型时,你是不是也经常遇到这样的困扰:模型效果确实不错,但推理速度慢、显存占用高,稍微复杂点的任务就得等半天。特别是像…...
政务大模型在智能客服中的实践:从架构设计到性能优化
最近在参与一个政务智能客服系统的项目,从零开始基于大模型技术构建了一套服务。政务领域的客服系统和我们常见的电商或通用客服很不一样,它对于准确性、稳定性和安全性的要求极高。今天就来分享一下我们在这个项目中的实践,从架构设计到性能…...
