当前位置: 首页 > 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带来的…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...

提升移动端网页调试效率:WebDebugX 与常见工具组合实践

在日常移动端开发中&#xff0c;网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时&#xff0c;开发者迫切需要一套高效、可靠且跨平台的调试方案。过去&#xff0c;我们或多或少使用过 Chrome DevTools、Remote Debug…...

Python训练营-Day26-函数专题1:函数定义与参数

题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一个名为 calculate_circle_area 的函数&#xff0c;该函数接收圆的半径 radius 作为参数&#xff0c;并返回圆的面积。圆的面积 π * radius (可以使用 math.pi 作为 π 的值)要求&#xff1a;函数接收一个位置参数 radi…...