快速选择排序

"你经过我每个灿烂时刻,我才真正学会如你般自由" 


         前些天有些无聊,想试试自己写的快排能否过leetcode上的排序算法题。结果是,不用截图可想而知,肯定是没过的,否则也不会有这篇文章的产出。

        这份快排算法代码在面对大量重复数的时候,时间复杂度会下降到O(n^2),这也是为什么leetcode显示最后会超时。所以如何解决呢?也许在此之前,可以先回顾回顾快排三步核心算法步骤。

——前言


快排的三个核心算法

● HOARE版

        这是最早的版本,也叫做左右指针法。不过这个算法需要值得注意的是一个地方。排升序时,一定是需要右指针先动,相反如果是排降序,则是左指针先动。        

int PartSort1(vector<int>& nums, int l, int r)
{// 左右指针法int key = nums[l];int left = l;int right = r;while (left < right){// 这里需要注意取等 // 如果不取等可能陷入死循环while (left < right && nums[right] >= key){right--;}while (left < right && nums[left] <= key){left++;}if (left < right) {swap(nums[left], nums[right]);}}// 处理keyiswap(nums[left], nums[l]);return left;
}

        我们对上述例子进行排序后的代码为:

● 挖坑法

        

int PartSort2(vector<int>& nums, int l, int r)
{int key = nums[l];int hole = l;int left = l, right = r;while (left < right){// 右边找小 填左坑while (left < right && nums[right] >= key){right--;}// 填坑swap(nums[right], nums[hole]);hole = right; // 新坑while (left < right && nums[left] <= key){left++;}swap(nums[left], nums[hole]);hole = left; // 新坑}// hole即为最终落脚点return hole;
}

        

● 前后指针法

        最后的前后指针法,也在前言中用到,这里不做多的解释。

int PartSort3(vector<int>& nums, int l, int r)
{int key = nums[l];int prev = l, cur = l + 1;while (cur <= r){// 找小if (nums[cur] < key && ++prev != cur){// prev指向的一定是比key大的数swap(nums[prev], nums[cur]);}cur++;}swap(nums[prev], nums[l]);return prev;
}

        


快速选择排序

        可是,你使用上述的不管哪种算法,都无法跑过leetcode上面的题,都会在重复数的情况下超时!这里我们可以用到归并分治的思想,如果将一个无序数组排序成有序数组,选定其中一个数作为key,可以将这个数组分为三部分:

    int getRandom(vector<int>& nums, int l, int r){int keyi = rand();return nums[keyi % (r-l+1) + l];} void qsort(vector<int>& nums, int l, int r){if(l < r){int key = getRandom(nums,l,r);// 数组分三块// 先让left、right指向非法区域int i = l,left = l-1,right = r+1;// [i,right]是未处理区域while(i < right){if(nums[i] < key) swap(nums[++left],nums[i++]);else if(nums[i] == key) i++;else swap(nums[--right],nums[i]);}// 递归处理其他区间qsort(nums,l,left);qsort(nums,right,r);}}

        我们终于是可以通过啦~


本篇到此结束,感谢你的阅读。

祝你好运,向阳而生~

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

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

相关文章

HCQ1-1300-D【高速输入】

因为我的PLC固件比较旧。所以有些限制。【比如&#xff1a;编译不报错&#xff0c;下载PLC程序就报故障】我的PLC的高速输入类型只能是【hsi_ref】 所以&#xff0c;程序添加的高速输入模块只能是【1.0.1.0】版本 如果固件版本低&#xff0c;看下固件能支持的类型。选错的话&am…

苹果曾考虑基于定位控制AirPods Pro自适应音频

在一次最近的采访中&#xff0c;苹果公司的高管Ron Huang和Eric Treski透露&#xff0c;他们在开发AirPods Pro自适应音频功能时&#xff0c;曾考虑使用GPS信号来控制音频级别。这个有趣的细节打破了我们对AirPods Pro的固有认知&#xff0c;让我们对苹果的创新思维有了更深的…

Python学习笔记之运算符的使用

Python学习笔记之运算符的使用 整型&#xff1a;二进制0b100十进制4、八进制0o100十进制64、十进制100、十六进制0x100十进制256浮点型&#xff1a;123.456&#xff0c;1.23456e2字符串型&#xff1a;‘Hello’&#xff0c;“Hello”布尔型&#xff1a;True、False复数型&…

电子计算机核心发展(继电器-真空管-晶体管)

目录 继电器 最大的机电计算机之一——哈弗Mark1号&#xff0c;IBM1944年 背景 组成 性能 核心——继电器 简介 缺点 速度 齿轮磨损 Bug的由来 真空管诞生 组成 控制开关电流 继电器对比 磨损 速度 缺点 影响 代表 第一个可编程计算机 第一个真正通用&am…

ssm+vue的图书馆书库管理系统(有报告)。Javaee项目,ssm vue前后端分离项目。

演示视频&#xff1a; ssmvue的图书馆书库管理系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;ssm vue前后端分离项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构…

OpenCV 基础图像处理

1、生成图像 cv2.imread是OpenCV库中的一个函数&#xff0c;用于读取图像文件。它接受一个参数&#xff0c;即要读取的图像文件的路径&#xff0c;返回一个多维数组&#xff0c; 表示图像的像素值。该函数的常用参数包括&#xff1a;flags&#xff1a;指定读取图像的方式&#…

python——Django框架

一、基本介绍 Django 是一个由 Python 编写的一个开放源代码的 Web 应用框架。 使用 Django&#xff0c;只要很少的代码&#xff0c;Python 的程序开发人员就可以轻松地完成一个正式网站所需要的大部分内容&#xff0c;并进一步开发出全功能的 Web 服务 Django 本身基于 MVC …

【已解决】opencv 交叉编译 ffmpeg选项始终为NO

一、opencv 交叉编译没有 ffmpeg &#xff0c;会导致视频打不开 在交叉编译时候&#xff0c;发现在 pc 端能用 opencv 打开的视频&#xff0c;但是在 rv1126 上打不开。在网上查了很久&#xff0c;原因可能是 交叉编译过程 ffmpeg 造成的。之前 ffmpeg 是直接用 apt 安装的&am…

asp.net core 远程调试

大概说下过程&#xff1a; 1、站点发布使用Debug模式 2、拷贝到远程服务器&#xff0c;以及iis创建站点。 3、本地的VS2022的安装目录&#xff1a;C:\Program Files\Microsoft Visual Studio\2022\Professional\Common7\IDE下找Remote Debugger 你的服务器是64位就拷贝x64的目…

【从入门到起飞】IO高级流(1)(缓冲流,转换流,序列化流,反序列化流)

&#x1f38a;专栏【JavaSE】 &#x1f354;喜欢的诗句&#xff1a;天行健&#xff0c;君子以自强不息。 &#x1f386;音乐分享【如愿】 &#x1f384;欢迎并且感谢大家指出小吉的问题&#x1f970; 文章目录 &#x1f384;缓冲流&#x1f354;字节缓冲流&#x1f6f8;一次读取…

【通意千问】大模型GitHub开源工程学习笔记(1)--依赖库

9月25日&#xff0c;阿里云开源通义千问140亿参数模型Qwen-14B及其对话模型Qwen-14B-Chat,免费可商用。 立马就到了GitHub去fork。 GitHub&#xff1a; GitHub - QwenLM/Qwen: The official repo of Qwen (通义千问) chat & pretrained large language model proposed b…

协议栈——收发数据(拼接网络包,自动重发,滑动窗口机制)

目录 协议栈何时发送数据&#xff5e; 数据长度 IP模块的分片功能 发送频率 网络包序号&#xff5e;利用syn拼接网络包ack确认网络包完整 确定偏移量 服务器ack确定收到数据总长度 序号作用 双端告知各自序号 协议栈自动重发机制 大致流程 ack等待时间如何调整 是…

Leetcode202. 快乐数

力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为&#xff1a; 对于一个正整数&#xff0c;每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1&#xff0…

【单片机】13-实时时钟DS1302

1.RTC的简介 1.什么是实时时钟&#xff08;RTC&#xff09; &#xff08;rtc for real time clock) &#xff08;1&#xff09;时间点和时间段的概念区分 &#xff08;2&#xff09;单片机为什么需要时间点【一定的时间点干什么事情】 &#xff08;3&#xff09;RTC如何存在于…

Redis中Hash类的操作

Redis中Hash类型是键值对的形式保存数据&#xff0c;其中键被称为字段&#xff08;field&#xff09;&#xff0c;值称为字段值&#xff08;value&#xff09;。在一个key中&#xff0c;字段不能重复&#xff0c;而值可以重复。无论是字段还是值都是无序的&#xff08;保存的次…

Java 大厂八股文面试专题-JVM相关面试题 垃圾回收算法 GC JVM调优

Java 大厂八股文面试专题-JVM相关面试题 类加载器_软工菜鸡的博客-CSDN博客 3 垃圾收回 3.1 简述Java垃圾回收机制&#xff1f;&#xff08;GC是什么&#xff1f;为什么要GC&#xff09; 难易程度&#xff1a;☆☆☆ 出现频率&#xff1a;☆☆☆ 为了让程序员更专注于代码的实现…

【Flink】

事件驱动型应用 核心目标&#xff1a;数据流上的有状态计算 Apache Flink是一个框架和分布式处理引擎&#xff0c;用于对无界或有界数据流进行有状态计算。 运行逻辑 状态 把流处理需要的额外数据保存成一个“状态”,然后针对这条数据进行处理,并且更新状态。这就是所谓的“…

MySQL explain SQL分析工具详解与最佳实践

目录 一、explain工具介绍二、添加示例表和数据用于后续演示三、explain中的列3.1、id列3.2、select_type列3.3、table列3.4、partitions列3.5、type列NULLsystemconsteq_refrefrangeindexALL 3.6、possible_keys列3.7、key列3.8、key_len列3.9、ref列3.10、rows列3.11、filter…

HDFS最基础使用

文章目录 一、简介1、定义2、HDFS优缺点3、HDFS组成架构4、HDFS文件块大小 二、HDFS的读写流程1、HDFS写数据流程2、HDFS读数据流程3、网络拓扑-节点距离计算4、机架感知&#xff08;副本存储节点选择&#xff09; 三、NameNode和SecondaryNameNode1、NN和2NN工作机制2、Fsimag…

Linux关于gittee的远端仓库的连接和git三板斧

目录 1.网页操作 2.Linux操作 查看Linux系统中是否安装git指令 安装git指令 链接远端仓库 设置 .gitignore文件 3.git三板斧 1.网页操作 首先我们要在gittee建立一个仓库 这是我自己的勾选方案&#xff0c;大家可以参考一下。 这个方案勾选最下面的三个选项才有&#x…