当前位置: 首页 > 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命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

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

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

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...