【手撕排序2】快速排序


🍃 如果觉得本系列文章内容还不错,欢迎订阅🚩
🎊个人主页:小编的个人主页
🎀 🎉欢迎大家点赞👍收藏⭐文章
✌️ 🤞 🤟 🤘 🤙 👈 👉 👆 🖕 👇 ☝️ 👍

目录

  • 🐼前言
  • 🐼快速排序
  • 🐼hoare版本
  • 🐼挖坑版本
  • 🐼前后指针版本
  • 🐼文末

🐼前言

🌟在上一节我们实现了希尔排序,感受到了插入排序的魅力,如果感兴趣的小伙伴,可以阅读我的上一篇文章:> 希尔排序,这节小编将带领大家感受交换排序的美学。

🐼快速排序

🔍 快速排序:快速排序是一种二叉树结构的交换排序,思想是:任取排序序列中的数字为基准值,按照基准值将待排序列划分为左右两个子序列,保证左序列的值均小于基准值,右序列的值均大于基准值。然后左右子序列重复该过程,直到所有元素都排列在相应位置上为止
📋 总结:找基准值,划分左子序列,划分右子序列。每一轮排序都能定位一个基准值,这样每一次递归一个基准值就在相应位置上了。

🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
快速排序主逻辑:

//快速排序
void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}int keyi = PartSort1(arr, left, right);//基准值QuickSort(arr, left,keyi-1);//左序列QuickSort(arr, keyi+1, right);//右序列
}

🌻代码解析

📋设置递归出口,如果左索引大于右索引,表示定位到所有基准值。接着,找基准值,保证左序列的值均小于基准值,右序列的值均大于基准值。keyi的位置已经排好,再递归左子树,(左序列:[left,keyi-1])再递归右子树(右序列[ keyi+1, right])
下面我们来实现找基准值,并让这个左序列的值均小于基准值,右序列的值均大于基准值这个步骤。

🐼hoare版本

🍐在上述 PartSort1⽤于按照基准值将区间[left,right)中的元素进行划分。我们先来实现hoare版本。
在hoare版本中,初始我们让基准值keyi就是第一个元素的下标,还需要定义两个指针left,right,一个指针right从右向左找比基准值小的或相等的元素,一个指针left需要从左向右找比基准值大的或相等元素。找到了两个元素,进行交换(并让left和right分别走一步,避免死循环),直到left>right,跳出循环。最后,让keyi处的值与右下标right的值交换。即arr[right]作为新的基准值,这样right作为基准值在该在的位置,也保证了左序列的值均小于基准值,右序列的值均大于基准值。
数组 {4,6,7,2,1,8,9,5,3 ,0}进行一轮:
在这里插入图片描述

hoare版本代码实现

// 快速排序hoare版本
int PartSort1(int* arr, int left, int right)
{int keyi = left;left++;//从keyi的下一个位置找while (left <= right){//从右向左找比基准值小的while (left<=right && arr[right] > arr[keyi]){right--;}//从左向右找比基准值大的while (left <= right && arr[left] < arr[keyi]){left++;}//找到满足的right和leftif (left <= right){Swap(&arr[left++], &arr[right--]);}}//将基准值与右坐标交换Swap(&arr[keyi], &arr[right]);return right;
}

👀为什么在找基准值的最后(left>right),一定是arr[right]<=arr[keyi]
因为在遍历的过程中,left从左向右走,一定保证了比基准值小,当right走到left左边,一定比arr[keyi]小。
👀为什么在交换过程中,不是直接交换,交换完让right,left走一步?
在我们写的hoare排序版本中,我们right从右向左找比基准值小的或相等的元素,一个指针left需要从左向右找比基准值大的或相等元素。所以对于{2,2,2,2,2}这样的序列,left和right找到完,如果不更新,会造成死循环。
👀为什么left从左向右为什么要找到大于或等于的元素,为什么不直接找到大于的元素呢?
如果一定找到比基准值大或比基准值小的元素,那么对于一组升序的数字{1,2,3,4,5…}right从右向左找比基准值小的或相等的元素,直到找到了1,基准值1与1交换。然后基准值没有左序列,只有右序列,那么每次找基准值要排序的个数都少1。所以,如果数组原本就有序,或数组元素时间复杂度过高,就为O(N^2).
👀为什么当left和right相遇了,不跳出循环?
当left和right指针相遇时,并不立即跳出循环的原因是,即使两个指针相遇,它们指向的位置的元素可能与基准值不等,需要进一步比较和交换以达到排序的目的,比如如果left和right同时指向4,基准值为2,此时让2,4交换,显然错误,所以,right需要小于left。
🍂画图剖析:
排列数组为{4,1,6,7,3}
在这里插入图片描述
🍀测试结果:
在这里插入图片描述

🐼挖坑版本

🍐挖坑版本的还是需要需要创建两个指针leftright,其思想是:我们需要先事先挖好一个坑hole,假设坑位刚开始是起始位置。保存基准值key为起始坑的位置(key = arr[hole])。
🍐现在我们需要填坑,从右向左找一个比基准值小的数据,找到后立即放入左边坑中,当前位置变为新的"坑",然后从左向右找出比基准大的数据,找到后立即放入右边坑中,当前位置变为新的"坑",结束循环后将最开始存储的基准值放入当前的"坑"中返回当前"坑"下标(即基准值下标)。
挖坑版本代码实现:

// 快速排序挖坑法
int PartSort2(int* arr, int left, int right)
{int hole = left;int key = arr[hole];//保存起始洞值while (left < right){//从右向左找到一个比基准值小的while (left<right && arr[right]>key){right--;}//该值覆盖洞值,并更新洞arr[hole] = arr[right];hole = right;while (left<right && arr[left]<key){left++;}arr[hole] = arr[left];hole = left;}arr[hole] = key;//返回基准值return hole;
}

🍂画图剖析:
在这里插入图片描述

🔍我们需要不断地从右向左找到比基准值小的,拿来填旧坑位,当前坑位就变成了新坑位,从左向右找到比基准值大的,拿来填旧坑位,当前坑位就变成了新坑位,最后,将最开始的基准值与当前坑位交换,当前坑位就是新基准值下标。这样从左向右找比基准值小的数据,放到前面。保证一轮循环下来。比基准值小的都在左边,比基准值大的都在右边。

🐼前后指针版本

🍐在前后指针中我们需要定义前后指针prev,cur。其思想是:让cur去前面探路,如果cur找到比基准值小的,然后prev先++,再将cur和prev所在位置交换。否则cur就一直向后找。最后,跳出循环,交换基准值和prev所在的数据。
🍐这样从左向右找比基准值小的数据,放到前面。保证一轮循环下来。比基准值小的都在左边,比基准值大的都在右边。
前后指针代码:

// 快速排序前后指针法
int PartSort3(int* arr, int left, int right)
{int prev = left, cur = prev + 1;int keyi = left;while (cur<=right){if (arr[cur] < arr[keyi] && cur != ++prev){Swap(&arr[cur], &arr[prev]);}cur++;}Swap(&arr[keyi], &arr[prev]);return prev;
}

🍂画图剖析:
在这里插入图片描述

👀为什么限制条件要加上cur != ++prev
因为当prev先走向下一个位置,此时刚好和cur重合,此时交换是无意义的,应该让cur继续移动。
👀为什么要先让prev++,再与cur交换
因为prev所在位置是已经调整好的数据,所以要先让prev先移动到下一个位置。

🐼文末

感谢你看到这里,如果觉得本篇文章对你有帮助,点个赞👍 吧,你的点赞就是我更新的最大动力 ⛅️🌈 ☀️

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/466751.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Stable Diffusion的解读(一)

Stable Diffusion的解读&#xff08;一&#xff09; 文章目录 Stable Diffusion的解读&#xff08;一&#xff09;摘要Abstract一、机器学习部分1. Stable Diffusion的早期工作1.1 从编码器谈起1.2 第一条路线&#xff1a;VAE和DDPM1.3 第二条路线&#xff1a;VQVAE1.4 路线的交…

2024年该了解的常用渲染工具

随着图形技术和计算机科学的飞速发展&#xff0c;渲染工具在多个领域中的应用越来越广泛&#xff0c;包括影视特效、建筑设计、工业设计、游戏开发等。了解并掌握一些常用的渲染工具对于设计师和艺术家来说至关重要。 一、效果图建模及渲染软件 Autodesk 3ds Max 拥有强大的建…

解决 “Error: listen EACCES: permission denied 0.0.0.0:80“ 错误

前言 在开发过程中&#xff0c;我们经常会遇到各种各样的错误。其中一个常见的错误是 Error: listen EACCES: permission denied 0.0.0.0:80。这个错误通常发生在尝试启动一个开发服务器时&#xff0c;服务器试图绑定到80端口&#xff0c;但由于权限不足而失败。本文将详细介绍…

flink 内存配置(一):设置Flink进程内存

flink 内存配置&#xff08;一&#xff09;&#xff1a;设置Flink进程内存 flink 内存配置&#xff08;二&#xff09;&#xff1a;设置TaskManager内存 flink 内存配置&#xff08;三&#xff09;&#xff1a;设置JobManager内存 flink 内存配置&#xff08;四&#xff09;…

51c嵌入式~电路~合集14

我自己的原文哦~ https://blog.51cto.com/whaosoft/12443598 一、嵌入式开发中的滤波器设计 什么是滤波器&#xff1f; 各种传感器信号多多少少会携带一些噪声信号&#xff0c;那么通过滤波器就能够更好的降低和去除噪声&#xff0c;还原真实有用信号。 滤波器是一个电路&…

安卓图片的着色教程(tint的使用)

目录 基础夯实&#xff1a;一、Tint的定义与作用二、Tint的应用场景三、Tint的使用方法四、Tint的优势五、注意事项 使用教程&#xff1a;一、xml文件中使用tint效果展示完整代码 二、代码中使用tint效果展示完整代码 三、使图片的主题和背景反色效果展示完整代码 四、运行例程…

Vulnhub靶机——DC-4

#环境准备 dc-4靶机&#xff1a;网卡nat模式 192.168.200.144 kali攻击机&#xff1a;网卡nat模式 192.168.200.129 #渗透过程 #信息收集 老规矩&#xff0c;先用nmap看看有什么端口可以搞 还是一如既往的80和22 访问80端口是一个登录界面&#xff0c;一上来就让我进行爆…

以太网交换安全:MAC地址漂移

一、什么是MAC地址漂移&#xff1f; MAC地址漂移是指设备上一个VLAN内有两个端口学习到同一个MAC地址&#xff0c;后学习到的MAC地址表项覆盖原MAC地址表项的现象。 MAC地址漂移的定义与现象 基本定义&#xff1a;MAC地址漂移发生在一个VLAN内的两个不同端口学习到相同的MAC地…

.NET6中WPF项目添加System.Windows.Forms引用

.NET6中WPF项目添加System.Windows.Forms引用 .NET6的WPF自定义控件默认是不支持System.Windows.Forms引用的&#xff0c;需要添加这个引用方法如下&#xff1a; 1. 在项目浏览器中找到项目右击&#xff0c;选择编辑项目文件&#xff08;Edit Project File&#xff09;。 …

Docker安装XXL-JOB分布式调度任务

一、持久化 1、下载 xxl-job 源码,找到持久化脚本 2、创建 xxl-job 数据库,将上述文件中的脚本在本库执行即可 create database xxl_job charset utf8mb4 collate utf8mb4_general_ci; 二、安装 1、下载 xxl-job 镜像 docker pull xuxueli/xxl-job-admin:2.4.1 2、创建挂…

Kafka 源码 KRaft 模式本地运行

KRaft&#xff08;Kafka Raft Metadata mode&#xff09;&#xff0c;从版本 2.8.0 开始作为测试特性引入&#xff0c;并在后续版本中持续得到改进和增强。 KRaft 模式是指 Kafka 使用 Raft 协议来管理集群元数据的一种运行模式&#xff0c;这标志着 Kafka 向去除对 ZooKeeper …

杨辉三角,洗牌算法

杨辉三角 给定一个非负整数numRows&#xff0c;生成杨辉三角的前numRows行。 在杨辉三角中&#xff0c;每个数是它的左上方和右上方的数的和。 public List<List<Integer>> generate(int numRows){List<List<Integer>> ret new ArrayList<>();…

计算机网络——HTTP篇

基础篇 IOS七层网络模型 TCP/IP四层模型&#xff1f; 应⽤层&#xff1a;位于传输层之上&#xff0c;主要提供两个终端设备上的应⽤程序之间的通信&#xff0c;它定义了信息交换的格式&#xff0c;消息会交给下⼀层传输层来传输。 传输层的主要任务就是负责向两台设备进程之间…

基于SpringBoot的Java教学支持系统开发指南

1系统概述 1.1 研究背景 随着计算机技术的发展以及计算机网络的逐渐普及&#xff0c;互联网成为人们查找信息的重要场所&#xff0c;二十一世纪是信息的时代&#xff0c;所以信息的管理显得特别重要。因此&#xff0c;使用计算机来管理教学辅助平台的相关信息成为必然。开发合适…

MySQL:表的增删改查(进阶)

表的增删改查&#xff08;进阶&#xff09;十分重要&#xff0c;也较有难度&#xff0c;需多花时间掌握。 一、NULL约束&#xff1a; 在加null约束之前&#xff0c;id可以插入null&#xff0c;在加上null约束之后&#xff0c;id不再可以插入null。 二、unique约束&#xff1a;…

Latex中给公式加边框

1、这里使用的不是 amsmath 的 \boxed 命令, 而是 empheq 的 empheq 环境以及 xcolor 的 \fcolorbox 命令, 下面是代码, 可以分别阅读这两个手册来获取更多的信息 \documentclass{article} \usepackage{xcolor} \usepackage{empheq} \usepackage{amsmath} \begin{document}\be…

VMware Workstation安装Centos系统

准备虚拟机和镜像文件 1. 安装虚拟机 安装虚拟机VMware Workstation&#xff0c;可以去官网下载自己需要的版本&#xff0c;如果已经安装可继续看后续步骤。安装链接&#xff1a;https://vmware.710down.com/?bd_vid14012951182566760856 2.下载镜像文件 阿里云镜像地址&a…

简单又便宜的实现电脑远程开机唤醒方法

现有的远程开机方案 1&#xff09;使用向日葵开机棒 缺点是比较贵一点&#xff0c;开机棒要一百多&#xff0c;而且查了评论发现挺多差评说不稳定&#xff0c;会有断联和无法唤醒的情况&#xff0c;而且设置也麻烦&#xff0c;还需要网卡支持WOL 2&#xff09;使用远程开机卡 …

WordCloudStudio:AI生成模版为您的文字云创意赋能 !

在信息泛滥的时代&#xff0c;如何有效地将文字内容变成生动的视觉元素&#xff1f;WordCloudStudio为您提供了答案。无论您是市场营销专家、教育工作者、数据分析师&#xff0c;还是创意设计师&#xff0c;WordCloudStudio都能帮助您轻松创建引人注目的文字云。更重要的是&…

低压线路保护器在生产型企业配电系统中的应用

摘要 随着现代电力系统的发展&#xff0c;配电系统的可靠性和安全性要求日益提高。低压线路保护器在其中扮演着关键角色。本文将探讨低压线路保护器的工作原理及其在现代配电系统中的作用&#xff0c;重点介绍ALP系列低压线路保护器的功能与应用。 引言 低压线路保护器用于保…