【快排与归并排序算法】
作者:指针不指南吗
专栏:算法篇🐾或许会很慢,但是不可以停下🐾
文章目录
- 一、快速排序 ( 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:是否改变输…...
(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲
文章目录 前言第一部分:体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分:体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...
针对药品仓库的效期管理问题,如何利用WMS系统“破局”
案例: 某医药分销企业,主要经营各类药品的批发与零售。由于药品的特殊性,效期管理至关重要,但该企业一直面临效期问题的困扰。在未使用WMS系统之前,其药品入库、存储、出库等环节的效期管理主要依赖人工记录与检查。库…...
WinUI3开发_使用mica效果
简介 Mica(云母)是Windows10/11上的一种现代化效果,是Windows10/11上所使用的Fluent Design(设计语言)里的一个效果,Windows10/11上所使用的Fluent Design皆旨在于打造一个人类、通用和真正感觉与 Windows 一样的设计。 WinUI3就是Windows10/11上的一个…...
