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

【快排与归并排序算法】

作者:指针不指南吗
专栏:算法篇

🐾或许会很慢,但是不可以停下🐾

文章目录

  • 一、快速排序 ( Quick Sort )
  • 二、归并排序 ( Merge Sort )
  • 总结

一、快速排序 ( Quick Sort )

1.思路

  • 找出一个分界点,随机的
  • 调整区间
    分治,双指针,指向两边,往中间走,遇到不满足条件的停下,直到两者都遇到不满足条件的,交换位置,直到两个指针相遇
  • 递归处理两段

分治
三步曲:分成子问题,解决子问题,子问题合并成大问题


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 )

相关文章:

【快排与归并排序算法】

作者&#xff1a;指针不指南吗 专栏&#xff1a;算法篇 &#x1f43e;或许会很慢&#xff0c;但是不可以停下&#x1f43e; 文章目录一、快速排序 ( Quick Sort )二、归并排序 ( Merge Sort )总结一、快速排序 ( Quick Sort ) 1.思路 找出一个分界点&#xff0c;随机的调整区间…...

面试官问我:说说你对JMM内存模型的理解?为什么需要JMM?

点个关注&#xff0c;必回关 随着CPU和内存的发展速度差异的问题&#xff0c;导致CPU的速度远快于内存&#xff0c;所以现在的CPU加入了高速 缓存&#xff0c;高速缓存一般可以分为L1、L2、L3三级缓存。基于上面的例子我们知道了这导致了缓存一致 性的问题&#xff0c;所以加入…...

工程管理系统源码之提高工程项目管理软件的效率

高效的工程项目管理软件不仅能够提高效率还应可以帮你节省成本提升利润 在工程行业中&#xff0c;管理不畅以及不良的项目执行&#xff0c;往往会导致项目延期、成本上升、回款拖后&#xff0c;最终导致项目整体盈利下降。企企管理云业财一体化的项目管理系统&#xff0c;确保…...

SpringBoot集成xxl-job实现

SpringBoot集成xxl-job实现 一、xxl-job介绍 xxl-job是一个分布式任务调度平台&#xff0c;核心设计目标是开发迅速、学习简单、轻量级、易扩展。源码&#xff1a;下载地址编译环境&#xff1a;Maven3、Jdk1.8、MySQL5.7 二、调度中心 初始化调度数据库&#xff0c;执行指定…...

欧几里得度量和余弦度量的可取消生物识别方案

欧几里得度量和余弦度量的可取消生物识别方案 便捷的生物识别数据是一把双刃剑&#xff0c;在为生物识别认证系统的繁荣铺平道路的同时&#xff0c;也带来了个人隐私问题。为了缓解这种担忧&#xff0c;提出了各种生物特征模板保护方案来保护生物特征模板免于信息泄露。现有提案…...

平板作为主机扩展屏的实现

网上有许多教程使用平板作为电脑的拓展屏&#xff0c;但是多数都是需要在电脑和平板上都装上服务器和客户端的软件才行&#xff0c;而且有些系统还没有对应的软件。 那有没有一种方法只需要在主机上运行一个软件&#xff0c;而平板上只需要扫个码就行呢&#xff1f; 答案是当然…...

HTTP和HTTPS有什么区别?如何实现网站的HTTPS?

细心的朋友会发现&#xff0c;我们在浏览网站时&#xff0c;有的网址以http开头&#xff0c;而有的网站却以https开头&#xff0c;那这两者之间有什么区别吗&#xff1f;http的网站如何能变成https呢&#xff1f;本文中科三方针对这个问题做下简单介绍。 什么是http&#xff1…...

Rockstar Games遭黑客攻击,《侠盗猎车手6》90个开发视频外泄

当地时间9月19日&#xff0c;视频游戏开发商Rockstar Games证实&#xff0c;其 热门游戏《侠盗猎车手6》&#xff08;Grand Theft Auto&#xff09;开发片段遭到黑客大规模窃取 &#xff0c;这一泄露事件立即在游戏圈迅速传播。 据报道&#xff0c; 上周末黑客至少泄露了90个游…...

RabbitMQ-客户端源码之AMQPImpl+Method

AMQPImpl类包括AMQP接口&#xff08;public class AMQImpl implements AMQP&#xff09;主要囊括了AMQP协议中的通信帧的类别。 这里以Connection.Start帧做一个例子。 public static class Connection {public static final int INDEX 10;public static class Startextends…...

雅思经验(7)

我发现雅思阅读要命的不是难度&#xff0c;而是时间的把控。考试时间是总共一小时&#xff0c;但是要写三篇文章&#xff0c;之后总共40道题目&#xff0c;也就是说每篇文章平均是13.3道。但是他们很多人说&#xff0c;如果誊写答案需要花掉3、4分钟每篇&#xff0c;也就是说真…...

Ubuntu20.04 用 `hwclock` 或 `timedatectl` 设置RTC硬件时钟为本地时区

Ubuntu20.04用 hwclock 或 timedatectl 设置硬件时区为本地时区 可以用hwclock命令 sudo hwclock --localtime --systohc&#x1f446;效果等同&#x1f447; , --localtime的简写是-l ; --systohc的简写是-w sudo hwclock -l -w也可以用timedatectl命令 &#x1f446;效果等…...

大学物理·第15章【量子物理】

黑体 斯特藩玻耳兹曼定律 维恩定律 光电效应 在光照射下 &#xff0c;电子从金属表面逸出的现象&#xff0c;叫光电效应. 逸出的电子&#xff0c;叫光电子 经典理论&#xff1a; 光电流值与入射光强成正比截止频率&#xff08;红限&#xff09;v0对某种金属来说&#xff0c;只有…...

2010-2019年290个地级市经济发展与城市绿化数据

2010-2019年290个地级市经济发展与城市绿化数据 1、时间&#xff1a;2010-2019年 2、来源&#xff1a;城市统计NJ&#xff0c;缺失情况与NJ一致 3、范围&#xff1a;290个地级市 4、指标&#xff1a; 综合经济&#xff1a;地区生产总值、人均地区生产总值、地区生产总值增…...

【CSS 布局】-多列布局

一、两列布局 两列布局&#xff1a;一列定宽(也有可能由子元素决定宽度)&#xff0c;一列自适应的布局。 创建一个父盒子&#xff0c;和子盒子 <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过度&#xff0c;将会初步介…...

Matter 研讨会回顾(第三期)|乐鑫 Matter 免开发方案与证书服务介绍

1 月 17 日&#xff0c;乐鑫举办了以“乐鑫 Matter 免开发方案与证书服务介绍”为主题的第三期 Matter 线上研讨会&#xff0c;介绍乐鑫开箱即用的 ESP-ZeroCode 模组及其免开发 Matter 方案&#xff0c;以及证书生成和预配置相关服务。欢迎观看研讨会的视频回放了解详情。&…...

函数栈帧的创建和销毁——“C”

各位CSDN的uu们你们好呀&#xff0c;今天小雅兰来为大家介绍一个知识点——函数栈帧的创建和销毁。其实这个知识点&#xff0c;我们很早之前就要讲&#xff0c;但是因为我的一系列原因&#xff0c;才一直拖到了现在&#xff0c;那么&#xff0c;话不多说&#xff0c;让我们一起…...

腾讯云对象存储+企业网盘 打通数据链“最后一公里

对云厂商和企业用户来说&#xff0c;随着数据规模的快速增长&#xff0c;企业除了对存储功能和性能的要求不断增加&#xff0c;也越来越注重数据分发的效率。在传统数据分发的过程中&#xff0c;数据管理员往往需要先在存储桶下载对应的客户方案/交付资料&#xff0c;再使用微信…...

在浏览器输入url到发起http请求,这过程发生了什么

当用户输入url&#xff0c;操作系统会将输入事件传递到浏览器中&#xff0c;在这过程中&#xff0c;浏览器可能会做一些预处理&#xff0c;比如 Chrome 会根据历史统计来预估所输入字符对应的网站&#xff0c;例如输入goog&#xff0c;根据之前的历史发现 90% 的概率会访问「ww…...

PyTorch学习笔记:nn.ReLU——ReLU激活函数

PyTorch学习笔记&#xff1a;nn.ReLU——ReLU激活函数 torch.nn.ReLU(inplaceFalse)功能&#xff1a;逐元素应用ReLU函数对数据进行激活 函数方程&#xff1a; ReLU(x)(x)max⁡(0,x)ReLU(x)(x)^\max(0,x) ReLU(x)(x)max(0,x) 输入&#xff1a; inplace&#xff1a;是否改变输…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

vscode里如何用git

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

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...