排序-快排算法对数组进行排序

目录

一、问题描述

二、解题思路

1.初始化

2.将右侧小于基准元素移到左边

3.将左侧大于基准元素移到右边

4.重复执行上面的操作

5.对分好的左、右分区再次执行分区操作

6.最终排序结果

三、代码实现

四、刷题链接


一、问题描述

二、解题思路

快排算法实现数组排序:快排的核心步骤是分区操作。

下面详细图解一次分区过程:

1.初始化

2.将右侧小于基准元素移到左边

赋值后相当于下面的情形:

3.将左侧大于基准元素移到右边

然后开始比较arr[low]和pivot的大小:(和上图作对比)

赋值后的数组为:

4.重复执行上面的操作

再次修改high(左移--),移动元素,再次修改low(右移++),移动元素;当low==high时停止,完成一次分区操作

5.对分好的左、右分区再次执行分区操作

分区返回的是中间元素位置,我们要对左、右两个子分区再次执行分区操作,每次分区都会确定一个中间位置(后序不会再变),当分区内元素都为1的时候,快排结束。

6.最终排序结果

三、代码实现

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** 将给定数组排序* @param arr int整型一维数组 待排序的数组* @return int整型一维数组*/public int[] MySort (int[] arr) {// 使用快排排序QuickSort(arr,0,arr.length-1);return arr;}public int partition(int[] arr,int low,int high){int pivot=arr[low];//分界元素//System.out.println("low:"+low+",high:"+high);while(low<high){while(arr[high]>=pivot){//右侧元素大于pivot不移动if(low==high){break;}high--;}arr[low]=arr[high];//现在的arr[high]已经没有元素了while(arr[low]<=pivot){//左侧元素小于等于pivot不移动if(low==high){break;}low++;}arr[high]=arr[low];}//此时low位置就是初始的分界元素应该在的位置arr[low]=pivot;return low;}public void QuickSort(int[] arr,int low,int high){int pivotIndex=partition(arr,low,high);if(low<pivotIndex-1){QuickSort(arr,low,pivotIndex-1);}if(high>pivotIndex+1){QuickSort(arr,pivotIndex+1,high);}}
}

快排算法里面要注意边界条件,这个好好思考一下。

如果考研的话可以写伪代码,边界条件可以考虑的少一点

排序算法相关代码-CSDN博客文章浏览阅读108次。【代码】排序算法相关代码。https://blog.csdn.net/hehe_soft_engineer/article/details/134235961下面是之前写的排序算法的C++实现,属于伪代码,应试的话可以参考一下:

四、刷题链接

排序_牛客题霸_牛客网

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

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

相关文章

【Spring EL<二>✈️✈️ 】SL 表达式结合 AOP 注解实现鉴权

目录 &#x1f37b;前言 &#x1f378;一、鉴权&#xff08;Authorization&#xff09; &#x1f37a;二、功能实现 2.1 环境准备 2.2 代码实现 2.3 测试接口 &#x1f379;三、测试功能 3.1 传递 admin 请求 ​ 3.2 传递普通 user 请求 &#x1f37b;四、章末 &a…

【智能算法应用】基于混合粒子群-蚁群算法的多机器人多点送餐路径规划问题

目录 1.算法原理2.数学模型3.结果展示4.参考文献5.代码获取 1.算法原理 【智能算法】粒子群算法&#xff08;PSO&#xff09;原理及实现 配餐顺序&#xff1a; 采用混合粒子群算法 || 路径规划&#xff1a; 采用蚁群算法 2.数学模型 餐厅送餐多机器人多点配送路径规划&…

美创科技入选“2024网络安全提供商创新排行榜”

近日&#xff0c;DBC德本咨询公布了“2024网络安全提供商创新排行榜”&#xff0c;美创科技凭借近20年的数据安全创新耕耘&#xff0c;荣誉上榜。 此次&#xff0c;与360、华为、腾讯等互联网、网络安全头部厂商并肩上榜&#xff0c;是行业对美创的再次认可。 数据安全的发展离…

景芯SoC A72的时钟树分析

innovus的ctslog中的Clock DAG信息可以报出来CTS主要运行步骤的关键信息&#xff0c;比如clustering&#xff0c;balancing做完后的clock tree的长度&#xff0c;clock tree上所用的buffer、inverter&#xff0c;icg cell数量&#xff0c;clock skew等信息。我们以景芯SoC A72 …

搜维尔科技:Movella旗下的Xsens在人形机器人开发中得到广泛应用

人形机器人的发展正在全球范围内受到广泛关注。作为机器人领域的重要分支&#xff0c;人形机器人因其具备高度仿真的外观和动作&#xff0c;以及更贴近人类的行为模式&#xff0c;有望逐渐成为人们日常生活和工业生产中的得力助手。在中国&#xff0c;这一领域的发展尤为引人注…

解密Spring Boot:深入理解条件装配与条件注解

文章目录 一、条件装配概述1.1 条件装配的基本原理1.2 条件装配的作用 二、常用注解2.1 ConditionalOnClass2.2 ConditionalOnBean2.3 ConditionalOnProperty2.4 ConditionalOnExpression2.5 ConditionalOnMissingBean 三、条件装配的实现原理四、实际案例 一、条件装配概述 1…

C++进阶:继承

文章目录 继承的概念继承的定义方式继承关系和访问限定符基类和派生类对象的赋值转换继承中的作用域派生类中的默认成员函数构造函数拷贝构造函数赋值拷贝函数析构函数 总结 继承的概念 继承(inheritance)机制是面向对象程序设计使代码可以复用的最重要的手段&#xff0c;它允…

【全开源】Java无人共享棋牌室茶室台球室系统JAVA版本支持微信小程序+微信公众号

无人共享棋牌室系统——棋牌娱乐新体验 &#x1f3b2;引言 随着科技的不断发展&#xff0c;传统棋牌室正逐渐迈向智能化、无人化。今天&#xff0c;我要为大家介绍的就是这款引领潮流的“无人共享棋牌室系统”。它不仅为棋牌爱好者提供了全新的娱乐体验&#xff0c;更在便捷性…

【Python】数据处理:SQLite操作

使用 Python 与 SQLite 进行交互非常方便。SQLite 是一个轻量级的关系数据库&#xff0c;Python 标准库中包含一个名为 sqlite3 的模块&#xff0c;可以直接使用。 import sqlite3数据库连接和管理 连接到 SQLite 数据库。如果数据库文件不存在&#xff0c;则创建一个新数据库…

Conda安装

conda可以做到不同项目就用不同虚拟环境,这样就能做到每个项目的依赖包都是相互独立 一、windows Download Success | Anaconda 环境变量 二、nano 本次安装Archiconda的外部python版本为python3.7.1

Vue基础知识:异步DOM更新是什么?$nextTick是什么?到底应该如何使用。什么是同步?什么是异步?

要先了解异步dom更新是什么就必须先了解&#xff0c;什么是同步&#xff1f;什么是异步&#xff1f; 1.什么是同步&#xff1f;什么是异步&#xff1f; 同步&#xff08;Synchronous&#xff09;&#xff1a; 同步操作是按照代码的顺序执行的&#xff0c;每个操作都必须等待上…

【数学建模】MATLAB入门教程:插值与拟合(下)

前言 插值与拟合在数据处理和科学计算中扮演着非常重要的角色&#xff0c;它们用于估算未知数据点的值&#xff0c;帮助我们理解和预测数据趋势 一、一维插值 1、一维插值定义 已知n1个节点(,)(j0,1,...,n,其中互不相同&#xff0c;不妨设a<<...<b),求任一插值点(…

swift5 在当前控制器先dismiss后pop

如下图需要在present当前控制器时用全局变量firmwareUpgradePresentingVC先引用上一个控制器&#xff08;下面的代码亲测有效&#xff09; func dismissAndPop() {self.dismiss(animated: false) {firmwareUpgradePresentingVC.navigationController!.popViewController(animat…

Java基础面试重点-3

41. 简述线程生命周期(状态) 其它参考《多线程重点》中的说法。三种阻塞&#xff1a; 等待阻塞&#xff1a; 运行的线程执行o.wait()方法&#xff08;该线程已经持有锁&#xff09;&#xff0c;JVM会把该线程放入等待队列中。同步阻塞&#xff1a; 运行的线程在获取对象的同步…

Stable Diffusion 如何写出更优雅的 Prompt

在看了前面的课程后&#xff0c; 相信很多人都会有一个困惑&#xff0c;这个 prompt 咋写… 为什么我写的时候只能憋出来了一个 a girl, a boy, beautify … 再也想不到其他的了&#xff0c; 总感觉是吃了没文化的亏&#xff1f; 这一节课我们就来讲一讲 如何写好 prompt …

跟着AI学AI_08 NumPy 介绍

NumPy&#xff08;Numerical Python&#xff09;是一个用于科学计算的基础库&#xff0c;它为 Python 提供了支持大规模多维数组和矩阵 NumPy 介绍 NumPy&#xff08;Numerical Python&#xff09;是一个用于科学计算的基础库&#xff0c;它为 Python 提供了支持大规模多维数…

如何快速搭建自己的进销存系统?

什么是进销存系统&#xff1f; 进销存&#xff0c;是指企业管理过程中采购&#xff08;进&#xff09;—入库&#xff08;存&#xff09;—销售&#xff08;销&#xff09;的动态管理过程。进&#xff1a;指询价、采购到入库与付款的过程。进销存管理系统是对企业生产经营中物…

【Python】已完美解决:(Python键盘中断报错问题) KeyboardInterrupt

文章目录 一、问题背景二、可能出错的原因三、错误代码示例四、正确代码示例&#xff08;结合实战场景&#xff09;五、注意事项 已解决&#xff1a;Python中处理KeyboardInterrupt&#xff08;键盘中断&#xff09;报错问题 一、问题背景 在Python编程中&#xff0c;当我们运…

css系列:音频播放效果-波纹律动

介绍 语音播放的律动效果&#xff0c;通俗来说就是一个带动画的特殊样式的进度条&#xff0c;播放的部分带有上下律动的动画&#xff0c;未播放的部分是普通的灰色竖状条。 实现中夹带了less变量、继承和循环遍历&#xff0c;可以顺带学习一下。 结果展示 大致效果如图所示…

继承深度剖析

前言 从继承开始就开始C进阶了&#xff0c; 这一块需要好好学习&#xff0c;这块知识很重要&#xff0c; 坑有点多&#xff0c;所以是面试笔试的常客。 基本概念 继承(inheritance)机制是面向对象程序设计使代码可以复用的最重要的手段&#xff0c; 它允许程序员在保持原有…