当前位置: 首页 > 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;是否改变输…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...

【SpringBoot自动化部署】

SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一&#xff0c;能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时&#xff0c;需要添加Git仓库地址和凭证&#xff0c;设置构建触发器&#xff08;如GitHub…...