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

快速排序

目录

什么是快速排序:

图解:

递归法:

 方法一(Hoare法):

  代码实现:

        思路分析:

       方法二(挖坑法):

        代码实现:

        思路分析:

        非递归法:

        图解:

        代码实现:

        思路分析:

        快速排序是不稳定的。


什么是快速排序:

        任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

图解:

        

         假设 0 下标的数字 3 作为我们的基准值,先看上图的left 和 right ,他们一开始是在start 和 end 的位置。

        在走的过程中,right 先走,直到遇到比 3 小的数字停下来,再到 left 走,直到遇到比 3 大的数字停下来;然后交换 此时 left 下标 和 right 下标 的数字,然后不断重复此过程,直到left 与 right 相遇停止;再把最后left 和 right 相遇的 下标位置 与 我们设定的基准值 3 交换;这样就保证了此时的left 位置的下标的左边都是比他小的,右边都是比他大的。也可以说此时的left 下标的数据已经有序了。(用 par 记录left 和 right相遇的位置)

        然后,再看此图:

        

         因为使用了 par 记录了 left 和 righjt 相遇的的位置,那么下次划分 一段数据左边则 使用 start 和 par - 1 作为一段新的数据的 left 和 right ,右边 使用 par + 1 和 end 作为一段新的数据的 left 和 right ,不断细分排序重复下去,直到start 与 end 相遇停止划分;看上图绿色椭圆圈出来的start ,那是在 1 下标右边走划分出来的一段,此时start 大于了 end ,也算一种停止划分条件。

        所以,停止划分的条件是 start >= end

递归法:

 方法一(Hoare法):

  代码实现:
public static void quickSortHoare(int[] arr) {quick(arr,0,arr.length - 1);}private static void quick(int[] arr, int start, int end) {if(start >= end) {return;}int par = parrtion(arr,start,end);//往左走quick(arr,start,par - 1);//往右走quick(arr,par + 1,end);}private static int parrtion(int[] arr, int left, int right) {int i = left;int ret = arr[left];while(left < right) {while(left < right && arr[right] >= ret) {right--;}while(left < right && arr[left] <= ret) {left++;}//交换swap(arr,left,right);}//交换swap(arr,i,left);return left;}private static void swap(int[] arr,int i,int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}
        思路分析:

        结合上面我们分析的图解,有个要注意的是 parrtion 方法里 的 left < right && arr[right] >= ret 和 left < right && arr[left] <= ret 这两个的循环条件,前提都要加上 left < right ,因为如果 对于一段已经有序的数据,假设我们使用对一个最小的数据作为基准值,第一个 arr[right] >= ret 循环 判断条件会一直让 right --,如果没有left < right 作为前提条件,会导致 right 越界。

        

       方法二(挖坑法):

        代码实现:
 public static void quickSort2(int[] arr) {quick(arr,0,arr.length - 1);}private static void quick2(int[] arr, int start, int end) {if(start >= end) {return;}int par = parrtion2(arr,start,end);//往左走quick2(arr,start,par - 1);//往右走quick2(arr,par + 1,end);}private static int parrtion2(int[] arr, int left, int right) {int ret = arr[left];while(left < right) {while(left < right && arr[right] >= ret) {right--;}arr[left] = arr[right];while(left < right && arr[left] <= ret) {left++;}arr[right] = arr[left];}arr[left] = ret;return left;}private static void swap(int[] arr,int i,int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}
        思路分析

        挖坑法 与 Hoare 法思路很相像,不同的是;

        挖坑法 是把 right 找到比 基准值 小的时候,把此时 的 right 下标的值给到 left 下标;left 找到比 基准值 大的时候,把此时 的 left 下标的值给到 right 下标。

        最后,由于一开始使用了 ret 存储了基准值,所以当 left 与 right 相遇时把 ret 给到 left 下标的位置。

        

        非递归法:

        图解:

         

        快速排序非递归的方法我们借助了一个栈,用来存放数据的下标;

        先把一段数据的 left 给到 栈里,再把 right 给到 栈里,然后排完一段序后,得到 par ,再把一段新的数据的 left 和 right 给到 栈里。

        要注意,当:

        

         这是分出来的一段数据,当par右边只剩一个元素时,那么右边剩下的一个元素是有序的,par 左边同理。

        代码实现

public static void quickSortNor(int[] arr) {int left = 0;int right = arr.length - 1;int par = parrtion3(arr,left,right);Stack<Integer> stack = new Stack<>();//左边有两个元素及以上if(left + 1 < par) {stack.push(left);stack.push(par - 1);}//右边有两个元素及以上if(par < right - 1) {stack.push(par + 1);stack.push(right);}while(!stack.isEmpty()) {right = stack.pop();left = stack.pop();par = parrtion3(arr,left,right);//左边有两个元素及以上if(left + 1 < par) {stack.push(left);stack.push(par - 1);}//右边有两个元素及以上if(par < right - 1) {stack.push(par + 1);stack.push(right);}}}private static int parrtion3(int[] arr, int left, int right) {int ret = arr[left];while(left < right) {while(left < right && arr[right] >= ret) {right--;}arr[left] = arr[right];while(left < right && arr[left] <= ret) {left++;}arr[right] = arr[left];}arr[left] = ret;return left;}

        思路分析

        结合上面的图解,一开始在循环外,我们排了一次序,得到了 par ,再把对应的 left 和 right 给到栈里。

        当栈不为空时,栈弹出的第一个元素作为相应一段数据 right ,下一个是对应的 left ,原因是我们放入栈时是先 left 再 right;再对其排序后得到新的 par ,再结合图解分析。直到栈为空时结束。

        

        快速排序是不稳定的。

相关文章:

快速排序

目录 什么是快速排序&#xff1a; 图解&#xff1a; 递归法&#xff1a; 方法一&#xff08;Hoare法&#xff09;&#xff1a; 代码实现&#xff1a; 思路分析&#xff1a; 方法二&#xff08;挖坑法&#xff09;&#xff1a; 代码实现&#xff1a; 思路分析&#xff1a; 非递…...

国内 ChatGPT Plus/Pro 订阅教程

1. 登录 chat.openai.com 依次点击 Login &#xff0c;输入邮箱和密码 2. 点击升级 Upgrade 登录自己的 OpenAI 帐户后&#xff0c;点击左下角的 Upgrade to Plus&#xff0c;在弹窗中选择 Upgrade plan。 如果升级入口无法点击&#xff0c;那就访问这个网址&#xff0c;htt…...

易仓科技ai面试

请解释PHP中的面向对象编程的基本概念&#xff0c;并举例说明如何在PHP中定义一个类。 回答思路&#xff1a;需理解类、对象、继承和多态等基本概念&#xff0c;并能通过实例代码展示如何定义类及其属性和方法。 . 类&#xff08;Class&#xff09; 类是一个封装了数据和操作…...

LabVIEW用户界面(UI)和用户体验(UX)设计

作为一名 LabVIEW 开发者&#xff0c;满足功能需求、保障使用便捷与灵活只是基础要求。在如今这个用户体验至上的时代&#xff0c;为 LabVIEW 应用程序设计直观且具有美学感的界面&#xff0c;同样是不容忽视的关键任务。一个优秀的界面设计&#xff0c;不仅能提升用户对程序的…...

字玩FontPlayer开发笔记14 Vue3实现多边形工具

目录 字玩FontPlayer开发笔记14 Vue3实现多边形工具笔记整体流程临时变量多边形组件数据结构初始化多边形工具mousedown事件mousemove事件监听mouseup事件渲染控件将多边形转换为平滑的钢笔路径 字玩FontPlayer开发笔记14 Vue3实现多边形工具 字玩FontPlayer是笔者开源的一款字…...

低代码与 Vue.js:技术选型与架构设计

在当下数字化转型的浪潮中&#xff0c;企业对应用开发的效率和质量有着极高的追求。低代码开发平台的兴起&#xff0c;为企业提供了一条快速构建应用的捷径&#xff0c;而 Vue.js 作为热门的前端框架&#xff0c;与低代码开发平台的结合备受关注。如何做好两者的技术选型与架构…...

比较循环与迭代器的性能:Rust 零成本抽象的威力

一、引言 在早期的 I/O 项目中&#xff0c;我们通过对 String 切片的索引和 clone 操作来构造配置结构体&#xff0c;这种方法虽然能确保数据所有权的正确传递&#xff0c;但既显得冗长&#xff0c;又引入了不必要的内存分配。随着对 Rust 迭代器特性的深入了解&#xff0c;我…...

一文了解zookeeper

1.ZooKeeper是什么 简单来说&#xff0c;她是一个分布式的&#xff0c;开放源码的分布式应用程序协调服务 具体来说&#xff0c;他可以做如下事情&#xff1a; 分布式配置管理&#xff1a;ZooKeeper可以存储配置信息&#xff0c;应用程序可以动态读取配置信息。分布式同步&a…...

算法题(67):最长连续序列

审题&#xff1a; 需要我们在O&#xff08;n&#xff09;的时间复杂度下找到最长的连续序列长度 思路&#xff1a; 我们可以用两层for循环&#xff1a; 第一层是依次对每个数据遍历&#xff0c;让他们当序列的首元素。 第二层是访问除了该元素的其他元素 但是此时时间复杂度来到…...

大中型企业专用数据安全系统 | 天锐蓝盾终端安全 数据安全

天锐蓝盾系列产品是专门为大中型企业量身定制的数据安全防护产品体系&#xff0c;涵盖天锐蓝盾DLP、天锐蓝盾终端安全管理系统、天锐蓝盾NAC以及其他搭配产品&#xff0c;致力于实现卓越的数据安全防护、施行严格的网络准入控制以及构建稳固的终端安全管理体系。通过全方位的防…...

Deepseek解读 | UE像素流送与实时云渲染技术的差别

为了实现UE引擎开发的3D/XR程序推流&#xff0c;绝大多数开发者会研究像素流送&#xff08;Pixel Streaming&#xff09;的使用方法&#xff0c;并尝试将插件集成在程序中。对于短时、少并发、演示场景而言&#xff0c;像素流送可以满足基本需求。当3D/XR项目进入落地交付周期后…...

CTFSHOW-WEB入门-PHP特性109-115

题目&#xff1a;web 109 1. 题目&#xff1a; 2. 解题思路&#xff1a;题目要求获得两个参数&#xff0c;v1 v2&#xff0c;if语句中的意思是要求两个参数都包含字母&#xff0c;条件满足的话&#xff0c;执行 echo new 类名&#xff08;方法&#xff08;&#xff09;&#xf…...

模糊综合评价法:原理、步骤与MATLAB实现

引言 在复杂决策场景中&#xff0c;评价对象往往涉及多个相互关联的模糊因素。模糊综合评价法通过建立模糊关系矩阵&#xff0c;结合权重分配与合成算子&#xff0c;实现对多因素系统的科学评价。本文详细讲解模糊综合评价法的数学原理、操作步骤&#xff0c;并辅以MATLAB代码…...

【数据结构-红黑树】

文章目录 红黑树红黑树介绍红黑树的五个基本性质红黑树的平衡原理红黑树的操作红黑树的操作 代码实现节点实现插入和查询操作 红黑树 红黑树介绍 红黑树&#xff08;Red-Black Tree&#xff09;是一种自平衡的二叉查找树&#xff08;Binary Search Tree, BST&#xff09;&…...

【STM32】舵机SG90

1.舵机原理 舵机内部有一个电位器&#xff0c;当转轴随电机旋转&#xff0c;电位器的电压会发生改变&#xff0c;电压会带动转一定的角度&#xff0c;舵机中的控制板就会电位器输出的电压所代表的角度&#xff0c;与输入的PWM所代表的角度进行比较&#xff0c;从而得出一个旋转…...

【Linux】Socket编程—TCP

&#x1f525; 个人主页&#xff1a;大耳朵土土垚 &#x1f525; 所属专栏&#xff1a;Linux系统编程 这里将会不定期更新有关Linux的内容&#xff0c;欢迎大家点赞&#xff0c;收藏&#xff0c;评论&#x1f973;&#x1f973;&#x1f389;&#x1f389;&#x1f389; 文章目…...

c++11 for auto不定参数

数量不定的模板参数。参数分为一个和一包两部分。 ​ 冒号的左边声明一个变量。右手边必须是一个容器。从容器(某种数据结构)中找出每一个元素设置到左边这个变量。11之前可以用容器的迭代器去取数据。或者标准库里的foreach...

C#+redis实现消息队列的发布订阅功能

代码 参考c#redis stream实现消息队列以及ack机制文章的思路&#xff0c;实现 SubscribeAttribute.cs using System;namespace DotnetQueue.Attributes {/// <summary>/// 订阅特性/// </summary>[AttributeUsage(AttributeTargets.Method, Inherited false)]pu…...

Docker容器基本操作

容器的基本操作 操作命令&#xff08;全&#xff09;命令&#xff08;简&#xff09;容器的创建docker container run <image name>docker run <image name>容器的列出&#xff08;up&#xff09;docker container lsdocker ps容器的列出&#xff08;up和exit&…...

从无序到有序:上北智信通过深度数据分析改善会议室资源配置

当前企业普遍面临会议室资源管理难题&#xff0c;预约机制不完善和临时会议多导致资源调度不合理&#xff0c;既有空置又有过度拥挤现象。 针对上述问题&#xff0c;上北智信采用了专业数据分析手段&#xff0c;巧妙融合楼层平面图、环形图、折线图和柱形图等多种可视化工具&a…...

Rust CLI工具bard-rs:终端直连Google Gemini并实时保存Markdown对话

1. 项目概述&#xff1a;一个Rust写的Google Gemini命令行工具 如果你和我一样&#xff0c;日常喜欢在终端里干活&#xff0c;同时又需要频繁地和Google Gemini&#xff08;以前叫Bard&#xff09;打交道&#xff0c;来回在浏览器和编辑器之间切换、复制粘贴对话内容&#xff…...

终极指南:3分钟掌握BOTW存档编辑器,打造你的专属海拉鲁冒险

终极指南&#xff1a;3分钟掌握BOTW存档编辑器&#xff0c;打造你的专属海拉鲁冒险 【免费下载链接】BOTW-Save-Editor-GUI A Work in Progress Save Editor for BOTW 项目地址: https://gitcode.com/gh_mirrors/bo/BOTW-Save-Editor-GUI 你是否厌倦了在《塞尔达传说&am…...

别再只盯着圈图了!用iTOL和MEGA搞定进化树美化与解读的保姆级指南

从MEGA到iTOL&#xff1a;进化树可视化美化的全流程实战解析 当你用MEGA完成进化树构建后&#xff0c;是否对着默认生成的"简陋"树图感到无从下手&#xff1f;科研论文中的精美进化树并非专业绘图软件的产物&#xff0c;而是通过iTOL等工具对原始数据进行深度加工的结…...

ChatGPT 2023年1月更新解读:模型表现、事实性、数学能力与停止生成按钮

&#x1f525;个人主页&#xff1a;杨利杰YJlio❄️个人专栏&#xff1a;《Sysinternals实战教程》《Windows PowerShell 实战》《WINDOWS教程》《IOS教程》《微信助手》《锤子助手》 《Python》 《Kali Linux》 《那些年未解决的Windows疑难杂症》&#x1f31f; 让复杂的事情更…...

开发工具分发遇阻,苹果开发者计划收费高、验证难,代码签名领域价格离谱!

苹果让开发者压力倍增2026年5月9日&#xff0c;开发者正在开发一款简单的开发者工具&#xff0c;旨在让管理Claude Code配置文件变得更轻松。该工具首个版本已发布&#xff0c;可在ccode.kronis.dev查看&#xff0c;或访问Itch.io页面下载或购买预编译的二进制文件&#xff0c;…...

PHP接入Bing AI:非官方库实现聊天与图像生成功能详解

1. 项目概述&#xff1a;一个让PHP应用接入Bing AI的“瑞士军刀” 如果你正在用PHP做项目&#xff0c;又眼馋ChatGPT和DALL-E这类AI能力&#xff0c;但不想去折腾复杂的OpenAI API或者被网络环境卡脖子&#xff0c;那今天聊的这个工具可能正对你的胃口。 maximerenou/php-bin…...

Boost电路空载时为什么会“炸管”?一个仿真实验带你看清电压失控全过程

Boost电路空载炸管现象全解析&#xff1a;从仿真实验到工程防护 Boost电路作为开关电源设计的核心拓扑之一&#xff0c;其空载状态下的电压失控问题一直是工程师们关注的焦点。当负载突然断开时&#xff0c;看似稳定的电路可能瞬间变成"电压炸弹"&#xff0c;轻则导致…...

如何快速配置Scroll Reverser:面向新手的macOS滚动方向管理完整指南

如何快速配置Scroll Reverser&#xff1a;面向新手的macOS滚动方向管理完整指南 【免费下载链接】Scroll-Reverser Per-device scrolling prefs on macOS. 项目地址: https://gitcode.com/gh_mirrors/sc/Scroll-Reverser 你是否经常在MacBook触控板和鼠标之间切换&#…...

AI训练数据质量保障:垃圾进垃圾出的预防策略

一、AI时代数据质量的核心价值在人工智能技术飞速发展的今天&#xff0c;AI模型的性能表现早已成为企业核心竞争力的重要组成部分。从智能客服的精准应答到自动驾驶的安全决策&#xff0c;从金融风控的风险预警到医疗影像的辅助诊断&#xff0c;AI模型的每一次输出都深刻影响着…...

Seraphine:英雄联盟玩家的智能数据助手与BP自动化工具

Seraphine&#xff1a;英雄联盟玩家的智能数据助手与BP自动化工具 【免费下载链接】Seraphine 英雄联盟战绩查询工具 项目地址: https://gitcode.com/gh_mirrors/se/Seraphine 你还在为每次进入游戏前手动查询队友对手战绩而烦恼吗&#xff1f;还在为BP阶段的手忙脚乱而…...