排序之快速排序

代码
class Solution {public int[] sortArray(int[] nums) {merge(nums, 0, nums.length - 1);return nums;}private void merge(int[] nums, int l, int r){if(l >= r) return;// 随机选取主元int i = new Random().nextInt(r - l + 1) + l;int temp = nums[i];nums[i] = nums[l];nums[l] = temp;int idx = sort(nums, l, r);merge(nums, l, idx - 1);merge(nums, idx + 1, r);}private int sort(int[] nums, int l, int r){int tmp = nums[l];int i = l;int j = r;while(i != j){while(nums[j] >= tmp && i < j){j--;}while(nums[i] <= tmp && i < j){i++;}if(i < j){int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}}nums[l] = nums[i];nums[i] = tmp;return i;}
}
过程

        先给出一个待排序的数组
请添加图片描述
        上述代码有两个主要方法,merge和sort方法,首先进入的是merge方法,进入merge方法,if条件,l为0,r为nums.length-1,不满足条件,暂时不用看随机主元选取的下面四行代码,之后进入了sort方法,l为0,r为nums.length - 1。sort方法,首先将首个元素4的值赋值给了tmp,i为首元素下标,j为末尾元素下标。进入i!=j,进入while循环,内层第一个while循环查找比tmp小的元素对应的下标,第二个while循环查找比tmp大的元素的下标,显然,经过第一个while后,j指向元素5的下标,i指向元素3的下标,之后进入if判断,i<j,满足条件,交换下标i和下标j的元素,得到如下图所示结果。
请添加图片描述
        第一次最外层while循环结束,此时,i指向3元素所在下标,j指向5元素所在下标,i!=j,继续。内层第一个while循环继续从5开始找比tmp(4)小的元素,j走到元素为1的下标位置,然后内层第二个while循环继续从3开始找比tmp(4)小的元素,走到下标1时,就停止了,原因在于while循环的第二个条件是i<j,此时i=j。走到if判断,i < j,显然i=j不满足条件。第二次外层循环结束,i=j,跳出最外层循环。此时,i和j都指向了元素1的下标。将nums[l]=nums[i],将元素为4修改为1,nums[i]=tmp,将元素为1修改为4。
        需要注意的是,内层两个循环不能调换顺序,如果调换顺序,就如上图所示,先从3开始找比tmp(4)大的元素,i会停在7的位置,之后从5开始找比tmp小的元素,但是由于要满足i<j,j也会停在7的位置,这就会导致跳出循环后,将元素4和元素7的位置进行调换,sort方法无法使得左侧序列都小于tmp,右侧序列都大于tmp。
请添加图片描述
        sort方法结束,返回元素4所在的下标,经过一次sort方法,得到了左侧小于4的序列,和右侧大于4的序列。sort方法的作用就是将数组首元素放到排序后数组的正确位置。之后分别递归左右两侧,即[1,2,3]和[7,6,5]继续使用sort方法,看右侧,将7排序到正确位置,并返回对应下标,显然[7, 6, 5]整个序列进入sort方法后,内层第一个while循环找比7小的元素,j指向了末尾元素5的位置,第二个while循环,找比7大的元素,i最终会走到元素5的下标,if条件也不会满足。将nums[l] = nums[i],nums[i]=tmp,得到序列[5, 6, 7],返回元素7下标,递归7左侧[5,6],和右侧[],显然右侧递归进入下一个merge方法因为l>r(l为5的下标,r为7的下标,递归返回7的下标,就是r,进入mergel和r分别传入7的下标+1,7的下标,l肯定大于r)而递归停止。左侧[5,6],进入sort方法,第一个while循环,j从6开始找比5小的元素,j就走到元素5所在的下标,第二个while循环,i<j不满足这个条件,也不满足if条件,i还是指向元素5,最后nums[l]=num[i],nums[i]=tmp,l和i下标其实是一样的,都指向了5。sort方法结束,返回5所在下标,5左侧[],右侧[6],继续递归merge方法,左侧因为l>r(l为5的下标,r为6的下标,返回5的下标,进入mergel和r分别传入5的下标,和5的下标-1,l肯定大于r),右侧因为l==r(l为5的下标,r为6的下标,返回5的下标,进入mergel和r分别传入5的下标+1,和6的下标,l等于r),而导致递归停止。
        在merge方法中,进入sort方法之前,有一个随机主元操作,如果没有该四行代码,sort默认将数组首元素作为主元,将数组排序成左侧小于数组首元素,右侧大于数组首元素。上述四行代码则是随机从数组中选取一个元素作为主元,而不是一直都是默认数组首元素。

实战
  • 排序数组

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

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

相关文章

【好用】推荐10套后端管理系统前端模板

后台管理系统前端模板是开发者在构建后台管理系统时使用的一种工具&#xff0c;它提供了预先设计好的界面和组件&#xff0c;以帮助开发者快速搭建出功能完善、用户体验良好的管理系统。以下是V哥整理的10款流行的后台管理系统前端模板&#xff0c;它们基于不同的技术栈和设计理…

第一部分 Vue讲解(代码版)

1.第一个vue实例 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content"widthdevice-w…

要申请开通融资融券账户,有那些条件?

1、什么是融资融券交易? 融资融券交易&#xff0c;又称信用交易&#xff0c;是指投资者向具有融资融券业务资格的证券公司提供担 保物&#xff0c;借入资金买入交易所上市证券&#xff08;融资交易&#xff09;或借入交易所上市证券并卖出&#xff08;融券交易&#xff09; 的…

【vue】v-model.lazy等(非实时渲染)

v-model&#xff1a;实时渲染v-model.lazy&#xff1a;失去焦点/按回车后&#xff0c;才渲染v-model.number&#xff1a;值转换为数字v-model.trim&#xff1a;去除首尾空格 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8&qu…

ansible的常见用法

目录 ##编辑hosts文件 ##copy模块##复制过去 ##fetch模块##拉取 ##shell模块 ##好用 ##command模块## ##file模块### ##cron模块### ##crontab 计划任务 ##下载好时间插件 ##script模块 ##yum模块## ##yum下载源配置文件 /etc/yum.repos.d/CentOS-Base.repo ##ser…

【Java】第十五届蓝桥杯JavaB组第一道填空题

&#xff03;【Java】第十五届蓝桥杯JavaB组第一道填空题 大家好 我是寸铁&#x1f44a; 总结了一篇【Java】第十五届蓝桥杯JavaB组第一道填空题文章 喜欢的小伙伴可以点点关注 &#x1f49d; Java B组 第一道填空题题解如下:

大数据实训进行时:数据标注项目

数据标注项目 培训目的 让同学们先熟悉理论知识&#xff0c;如&#xff1a;识别障碍物是否满足拉框的要求&#xff0c;如何进行拉框&#xff1b;熟悉标注操作&#xff0c;培养出能够进入正式项目的人员 培训地点 理论&#xff1a;学术报告厅、阶梯教室 实操&#xff1a;1实…

性能优化-01

当看到性能指标时&#xff0c;你会首先想到什么呢&#xff1f;我相信 “高并发” 和 “响应快” 一定是最先出现在你脑海里的两个词&#xff0c;而它们也正对应着性能优化的两个核心指标—— “吞吐” 和 “延时” 。这两个指标是从应用负载的视角来考察性能&#xff0c;直接影…

SRNIC、选择性重传、伸缩性、连接扩展性、RoCEv2优化(六)

参考论文SRDMA&#xff08;A Scalable Architecture for RDMA NICs &#xff09;&#xff1a;https://download.csdn.net/download/zz2633105/89101822 借此&#xff0c;对论文内容总结、加以思考和额外猜想&#xff0c;如有侵权&#xff0c;请联系删除。 如有描述不当之处&…

【软考】哈希表

目录 一、概念1.1 定义 二、哈希函数的构造方法2.1 说明2.2 特性 三、处理冲突的方法3.1 说明3.2 开放定址法3.2.1 说明3.2.2 线性探测 3.3 链地址法3.4 再哈希法3.5 建立公共溢出区 四、哈希表的查找4.1 查找过程4.2 查找特点4.3 装填因子 一、概念 1.1 定义 1.一般存储结构由…

【回溯】Leetcode 51. N 皇后【困难】

N 皇后 按照国际象棋的规则&#xff0c;皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 nn 的棋盘上&#xff0c;并且使皇后彼此之间不能相互攻击。 给你一个整数 n &#xff0c;返回所有不同的 n 皇后问题 的解决方案。…

android11 如何修改状态栏的背景

修改status_bar.xml &#xff1a; <LinearLayout android:id"id/status_bar_contents"android:background"#1ABC9C"android:layout_width"match_parent"android:layout_height"match_parent"android:paddingStart"dimen/statu…

chromium 协议栈 cronet ios 踩坑案例

1、请求未携带 Accept-Language http header 出现图片加载失败 现象&#xff1a; 访问 https://www.huawei.com/cn/?ic_mediumdirect&ic_sourcesurlent 时出现图片加载失败的问题 预期结果&#xff1a; 原因&#xff1a; 网络库删除了添加 Accept-Language header 的逻…

突破像素限制,尽显照片细腻之美——Topaz Gigapixel AI for Mac/Win

在这个数字化的时代&#xff0c;我们都热爱用照片记录生活中的美好瞬间。然而&#xff0c;有时候我们会发现&#xff0c;由于各种原因&#xff0c;照片的像素可能无法满足我们的需求。这时候&#xff0c;Topaz Gigapixel AI for Mac/Win 这款强大的照片放大工具应运而生。 Top…

智慧污水井物联网远程监控案例

智慧污水井物联网远程监控案例 在当今数字化转型的浪潮中&#xff0c;智慧水务已成为城市基础设施建设的重要组成部分。其中&#xff0c;基于物联网技术的智慧污水井远程监控系统以其高效、精准、实时的特性&#xff0c;在提升污水处理效能、保障城市水环境安全、实现精细化管…

matlab使用教程(42)—常见的二维图像绘制方法

这个博客用于演示如何在 MATLAB 中创建曲线图、条形图、阶梯图、误差条形图、极坐标图、针状图、散点图。 1.曲线图 plot 函数用来创建 x 和 y 值的简单线图。 x 0:0.05:5; y sin(x.^2); figure plot(x,y) 运行结果&#xff1a; 线图可显示多组 x 和 y 数据。 x 0:0.05:…

Swift Zulian Tiger

Swift Zulian Tiger 迅捷祖利安猛虎 16万金&#xff08;游戏币&#xff09; 1万金大概就能兑换460元~600元之间&#xff0c;6400元-9600元&#xff0c;汗颜 故事的一天刚打完BWL&#xff0c;才125金&#xff08;游戏币&#xff09; 本来想下线的结果他们说你太黑了&…

OV通配符证书:安全、便捷的网络认证新选择

OV通配符证书&#xff0c;即组织验证型通配符证书&#xff0c;其最大特点在于其通配符功能。这意味着&#xff0c;一个OV通配符证书可以覆盖同一主域名下的多个子域名&#xff0c;大大简化了证书管理和维护的复杂性。无论是大型企业还是个人网站&#xff0c;都可以通过OV通配符…

Java springmvc 参数名用is开头导致为null

因为最近在整理一些源码和编写规范&#xff0c;这里写一下只是记录几年前自己遇到的问题&#xff0c;好久都忘了&#xff0c;还是写下来比较好。 问题记录&#xff1a;由于变量使用了boolean&#xff0c;并且变量名是is开头的&#xff0c;由于java机制boolean默认是false&#…

水离子雾化壁炉与酒店会客厅的氛围搭配

水离子雾化壁炉与酒店会客厅的氛围搭配可以营造出舒适、温馨和现代化的氛围&#xff0c;以下是一些建议&#xff1a; 焦点装饰&#xff1a;将水离子雾化壁炉设计成会客厅的焦点装饰物&#xff0c;使其成为客人进入会客厅后第一眼的吸引点。选择设计独特、现代化的壁炉造型&…