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

面试重点---快速排序

快排单趟

快速排序是我们面试中的重点,这个知识点也很抽象,需要我们很好的掌握,而且快速排序的代码也是非常重要,需要我们懂了还不行,必须要手撕代码,学的透彻。

在研究快速排序之前,我们首先看一个动画,先自己看几遍,看能不能看懂它在干什么。

这个动画就是我们快排的总体过程,如果你没有看懂也不用急,我用文字来帮助你理解这个过程。我们定义了一个key,他是6这个数字,然后L和R分别在数组的最左边和最右边,首先让R先走,让R找到比key小的数,第一个找的是5,然后不动,再让L向右移动,找到比key大的数,不动,将L和R交换,再继续移动,直到L和R相遇,相遇之后,与key交换,就达到了下面这幅图的效果。

 仔细观察可以发现,我们的6到达了它应该到达的位置,并且,6的左边都比6小,6的右边都比6大。这是我们快排的单趟过程。

快排的全过程

上面我们研究了快排的单趟,而我们怎么将它的单趟结合起来,让整个数组的顺序都排好呢?下面我们来看一组图,演示一下快排的全过程。

这就是快速排序的全过程,是不是很熟悉,就是我们之前二叉树里面接触的递归,有没有想起来呢?

这就是我们实现快排的过程。

key的选取

首先我们思考一个问题,当我们的数组是有序的,那么,效率会发生什么变化呢?

是不是就像上图一样,我们这个时间复杂度就从N*logN变成了N^2呢?效率瞬间就下降了一个层次,为了避免这样的情况发生,我们思考的解决方案就是将我们选取的k不固定的选在第一个,这样就避免了上图的样子,效率也会蹭蹭往上涨,那么,k 用什么办法选呢?

第一种方法就是随机选取,第二种方法就是取中间值,我个人认为还是第二种科学一点,第二种方法的k值是可控的,科学的,不是随机生成的。 

全部代码见下篇文章。

相关文章:

面试重点---快速排序

快排单趟 快速排序是我们面试中的重点,这个知识点也很抽象,需要我们很好的掌握,而且快速排序的代码也是非常重要,需要我们懂了还不行,必须要手撕代码,学的透彻。 在研究快速排序之前,我们首先…...

[MIT6.5840]MapReduce

MapReduce Lab 地址 https://pdos.csail.mit.edu/6.824/labs/lab-mr.html 论文地址 https://static.googleusercontent.com/media/research.google.com/zh-CN//archive/mapreduce-osdi04.pdf 工作原理 简单来讲,MapReduce是一种分布式框架,可以用来处理…...

【系统架构设计师】计算机组成与体系结构 ⑯ ( 奇偶校验码 | CRC 循环冗余码 | 海明码 | 模 2 除法 )

文章目录 一、校验码1、校验码由来2、奇偶校验码3、CRC 循环冗余码 ( 重点考点 )4、海明码校验 ( 软考不经常考到 ) 二、CRC 循环冗余码 ( 重点考点 )1、模 2 除法概念2、模 2 除法步骤3、模 2 除法示例4、CRC 循环冗余码示例 15、CRC 循环冗余码示例 2 参考之前的博客 : 【计…...

springboot,service 层统一异常抛出时,throws Exception写在接口上还是实现类上

springboot,service 层统一异常抛出时,throws Exception写在实现接口上,不是直接写在实现类上...

深度学习高效性网络

为了减轻Transformer笨重的计算成本,一系列工作重点开发了高效的Vision Transformer,如Swin Transformer、PVT、Twins、CoAtNet和MobileViT。 1、字节TRT-ViT 兼具CNN的速度、Transformer精度的模型 TRT-ViT(Transformer-based Vision Tra…...

PyQt ERROR:ModuleNotFoundError: No module named ‘matplotlib‘

Solution:打开cmd输入指令下载malplotlib pip install matplotlib...

Flutter Geolocator插件使用指南:获取和监听地理位置

Flutter Geolocator插件使用指南:获取和监听地理位置 简介 geolocator 是一个Flutter插件,提供了一个简单易用的API来访问特定平台的地理位置服务。它支持获取设备的最后已知位置、当前位置、连续位置更新、检查设备上是否启用了位置服务,以…...

网站基本布局CSS

代码 <!DOCTYPE html> <html> <head><meta charset"utf-8"><meta name"viewport" content"widthdevice-width, initial-scale1"><title></title><style type"text/css">body {margi…...

ssm框架整合,异常处理器和拦截器(纯注解开发)

目录 ssm框架整合 第一步&#xff1a;指定打包方式和导入所需要的依赖 打包方法&#xff1a;war springMVC所需依赖 解析json依赖 mybatis依赖 数据库驱动依赖 druid数据源依赖 junit依赖 第二步&#xff1a;导入tomcat插件 第三步&#xff1a;编写配置类 SpringCon…...

古籍双层PDF制作教程:保姆级古籍数字化教程

在智慧古籍数字化项目中&#xff0c;很多图书馆要求将古籍导出为双层PDF&#xff0c;并且确保输出双层PDF底层文本与上层图片偏移量控制在1毫米以内。那么本教程带你使用古籍数字化平台&#xff0c;3分钟把一个古籍书籍转化为双侧PDF。 第1步&#xff1a;上传古籍 点批量上传…...

Git 删除 远端的分支

要删除 Git 远端的分支&#xff08;例如&#xff1a; V3.2.1.13&#xff09;&#xff1a; 可以执行以下命令 git push origin --delete V3.2.1.13这条命令会向远端的仓库删除名为 V3.2.1.13 的分支。如果这个分支只在远端仓库存在而没有对应的本地分支&#xff0c;那么删除后这…...

PrgogressBar实现原理分析

ProgressBar 是 Android 中用于显示进度条的控件&#xff0c;它可以用来表示任务的完成程度或者加载进度等信息。ProgressBar 有两种主要类型&#xff1a;一种是确定性的&#xff08;determinate&#xff09;&#xff0c;另一种是不确定性的&#xff08;indeterminate&#xff…...

【HarmonyOS】HarmonyOS NEXT学习日记:七、页面与组件的生命周期

【HarmonyOS】HarmonyOS NEXT学习日记&#xff1a;七、页面与组件的生命周期 页面和组件 组件&#xff1a;用Component装饰的代码称为自定义组件页面&#xff1a;Entry装饰的组件即页面的根节点 组件生命周期 aboutToAppear&#xff1a;在创建自定义组件的新实例后&#xf…...

【iOS】——Block循环引用

循环引用原因 如果在Block中使用附有_ _strong修饰符的对象类型自动变量&#xff0c;那么当Block从栈复制到堆时&#xff0c;该对象为Block所持有&#xff0c;这样容易引起循环引用。 HPPerson *person [[HPPerson alloc] init];person.block ^{NSLog("person.age--- …...

shell脚本自动化安装启动各种服务

1、自动化配置dns服务器 A主机&#xff1a;vim dns.sh #!/bin/bash# 自动化部署dns# 1、下载bind# 2、修改配置文件# vim /etc/named.conf # listen-on port 53 { 127.0.0.1;any; }; 修改&#xff08;定位替换&#xff09;# allow-query { localhost;any; }; 修改&am…...

Python - 开源库 ReportLab 库合并 CVS 和图像生成 PDF 文档

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/140281680 免责声明&#xff1a;本文来源于个人知识与公开资料&#xff0c;仅用于学术交流&#xff0c;欢迎讨论&#xff0c;不支持转载。 Report…...

Java编写SIP协议

1、编写Server代码 package com.genersoft.iot.vmp.sip; import javax.sip.*; import javax.sip.message.*; import javax.sip.header.*; import java.util.*;public class SimpleSipServer implements SipListener {private SipFactory sipFactory;private SipStack sipStack…...

大型语言模型LLM的核心概念

本文主要介绍了目前主流的&#xff0c;几个大型语言模型LLM的整个训练过程 通常分为下面的几个阶段 1. 预训练 采用互联网上的大量数据进行训练&#xff0c;这一阶段大模型LLM的主体已定&#xff0c;找出共性并且压缩成一个模型。模型的参数量不是越大越好&#xff0c;遵循合理…...

软件测试---网络基础、HTTP

一、网络基础 &#xff08;1&#xff09;Web和网络知识 网络基础TCP/IP 使用HTTP协议访问Web WWW万维网的诞生 WWW万维网的构成 &#xff08;2&#xff09;IP协议 &#xff08;3&#xff09;可靠传输的TCP和三次握手策略 &#xff08;4&#xff09;域名解析服务DNS &#xff0…...

韩顺平0基础学java——第39天

p820-841 jdbc和连接池 1.JDBC为访问不同的数据库提供了统一的接口&#xff0c;为使用者屏蔽了细节问题。 2.Java程序员使用JDBC&#xff0c;可以连接任何提供了JDBC驱动程序的数据库系统&#xff0c;从而完成对数据库的各种操作。 3.jdbc原理图 JDBC带来的好处 2.JDBC带来的…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...