快速排序算法

快排版本1:最差O(n^2) 划分值很偏

总拿最后一个数做划分,划分好最后一个数和大于区的第一个数做交换,然后在小于等于5区域和大于5区域继续往复循环操作,都取各自的最后一个数作为基准数。

快排版本2:最差O(n^2) 划分值很偏

每次排序都能搞定一堆等于5的区域。只要最后一个数和大于区的第一个数做交换

然后左右侧以最后一个数作为基准数,继续做递归。

快排 【最好情况 几乎在中点】O(n*logn)

L到R随机选个数和最后位置做交换,拿最后位置做划分。

举例

L和R的索引分别是10和15

partition后就返回12和13,表示的是划分值区域的左边界和右边界

public int[] sortArray(int[] nums) {if(nums == null || nums.length < 2){return nums;}quickSort(nums,0,nums.length - 1);return nums;}//交换位置public void swap(int[] nums,int L,int R){int temp = 0;temp = nums[L];nums[L] = nums[R];nums[R] = temp;}// 快排public void quickSort(int[] arr,int L,int R){if(L < R){// *精华!随机数和最后一个数做交换  随机数:0 <= r < 1swap(arr,L + (int)(Math.random() * (R - L + 1)),R);// 拿L和R范围上 以及我选出来的最后一个位置上 做partition// 返回数组长度一定是2,中间排好序的左边界和右边界int[] p = partition(arr,L,R);// p[0]是等于区域的左边界,p[0]-1就是小于区域右边界quickSort(arr,L,p[0]-1);// p[1]是等于区域的右边界,p[1]+1就是大于区域左边界quickSort(arr,p[1]+1,R);}}public int[] partition(int[] arr,int L,int R){// <区右边界int less = L - 1; // <区左边界int more = R;// arr[L]表示当前数的位置 还没碰上右边界的第一个数 排序while(L < more){if(arr[L] < arr[R]){swap(arr,++less,L++);}else if(arr[L] > arr[R]){// >区左扩swap(arr,--more,L);}else{L++;}}// 都做完后,最后一个数和大于区第一个做交换swap(arr,more,R);// 返回中间排好序的左边界和右边界return new int[] {less + 1,more};}

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

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

相关文章

牛牛的凑数游戏 --- 题解

目录 牛牛的凑数游戏&#xff1a; 题目大意&#xff1a; 思路解析&#xff1a; 代码实现&#xff1a; 牛牛的凑数游戏&#xff1a; 题目大意&#xff1a; 思路解析&#xff1a; 我们可以很容易一个区间是否会存在1&#xff0c;那么我们想如果存在1&#xff0c;且有3个1&…

Clickhouse表引擎介绍

作者&#xff1a;俊达 1 引擎分类 ClickHouse表引擎一共分为四个系列&#xff0c;分别是Log、MergeTree、Integration、Special。其中包含了两种特殊的表引擎Replicated、Distributed&#xff0c;功能上与其他表引擎正交&#xff0c;根据场景组合使用。 2 Log系列 Log系列…

Spring基础——使用注解开发SpringMVC

目录 配置SpringMVC的初始化信息配置ServletWebApplicationContext配置RootWebApplicationContext配置ServletContext 创建Controller控制器配置Controller响应路径接收用户传递参数接收JSON数据接收简单类型对象封装参数 接收数组类型 Restful 文章源码仓库&#xff1a;Spring…

2024年云服务器ECS价格表出炉——阿里云

2024年阿里云服务器租用费用&#xff0c;云服务器ECS经济型e实例2核2G、3M固定带宽99元一年&#xff0c;轻量应用服务器2核2G3M带宽轻量服务器一年61元&#xff0c;ECS u1服务器2核4G5M固定带宽199元一年&#xff0c;2核4G4M带宽轻量服务器一年165元12个月&#xff0c;2核4G服务…

Python Web开发记录 Day9:Django part3 用户管理

名人说&#xff1a;莫道桑榆晚&#xff0c;为霞尚满天。——刘禹锡&#xff08;刘梦得&#xff0c;诗豪&#xff09; 创作者&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 目录 1、数据库准备2、用户列表3、新建用户4、编辑用…

钡铼技术R40路由器隧道通风控制及环境监测系统集成方案

一、背景介绍 随着城市化进程的加快&#xff0c;地下交通建设越来越重要。地下隧道作为城市交通的重要组成部分&#xff0c;其安全运行和环境质量直接关系到人们的出行体验和生活质量。为了保障隧道内空气的流通和质量&#xff0c;钡铼技术R40路由器通风控制及环境监测系统应运…

【SpringCloud微服务实战08】RabbitMQ 消息队列

MQ异步通信优缺点: 优点: 吞吐量提升:无需等待订阅者处理完成,响应更快速 故障隔离:服务没有直接调用,不存在级联失败问题 调用间没有阻塞,不会造成无效的资源占用 耦合度极低,每个服务都可以灵活插拔,可替换 流量削峰:不管发布事件的流量波动多大,都由Broker接收,…

如何利用百度SEO优化技巧将排到首页

拥有一个成功的网站对于企业和个人来说是至关重要的&#xff0c;在当今数字化的时代。在互联网上获得高流量和优质的访问者可能并不是一件容易的事情&#xff0c;然而。一个成功的SEO战略可以帮助你实现这一目标。需要一些特定的技巧和策略、但要在百度搜索引擎中获得较高排名。…

Selenium 自动化 —— 入门和 Hello World 实例

Selenium 是什么 Selenium 是一个用于自动化网页浏览器操作的工具&#xff0c;它支持多种浏览器和多种操作系统。主要用于测试 web 应用程序的功能&#xff0c;也可用于执行一些基本的浏览器操作任务&#xff0c;例如自动化表单填写、网页导航等。 Selenium 是一个开源项目&a…

天地图全国幼儿园数据下载与处理分析

概述 在看天地图服务资源的时候看到有个“幼儿园”的数据&#xff0c;好奇点开看了下&#xff0c;下载下来数据差看了下&#xff0c;数据质量还不错。本篇文章给大家分享一下这个数据的处理以及一些简单的统计分析结果。 数据下载 通过地址https://service.tianditu.gov.cn/…

WPF —— Grid网格布局

1 &#xff1a;Grid网格布局简介 Grid为WPF中最常用的布局容器, 作为View中的主要组成部分, 负责框架中整体的页面布局。 2&#xff1a;网格标签Grid.ColumnDef Grid.ColumnDefinitions自定义列 只能设置宽度 不能设置高度ColumnDefinition 每一个列可以设置宽度&#xff0c;…

机试:蛇形矩阵

问题描述: 代码示例: //蛇形矩阵 #include <bits/stdc.h> using namespace std;int main(){int n;cout << "输入样例" << endl; cin >> n;int k 1; for(int i 0; i < n; i){if( i %2 0){//单数行for(int j 0; j < n; j){ cout &…

Apache Paimon 的 CDC Ingestion 概述

CDC Ingestion 1&#xff09;概述 Paimon支持schema evolution将数据插入到Paimon表中&#xff0c;添加的列将实时同步到Paimon表&#xff0c;并且无需重启同步作业。 目前支持的同步方式如下&#xff1a; MySQL Synchronizing Table: 将MySQL中的一个或多个表同步到一个Pa…

网络原理(网络协议初识)

目录 1.网络通信基础 1.1IP地址 1.2端口号 1.3认识协议 1.4五元组 1.5 协议分层 2.TCP/IP五层&#xff08;或四层&#xff09;模型 2.1网络设备所在分层 2.2网络分层对应 3.封装和分用 1.网络通信基础 网络互连的目的是进行网络通信&#xff0c;也即是网络数据传输&#…

数据仓库为什么要分层建设?每一层的作用是什么?

在数字化时代&#xff0c;数据已成为企业最宝贵的资产之一。为了更好地管理和利用这些数据&#xff0c;许多企业都建立了数据仓库。然而&#xff0c;数据仓库并非简单的数据存储工具&#xff0c;而是一个复杂的数据处理和分析系统。其中&#xff0c;分层建设是数据仓库设计的重…

【OpenCV实战】基于OpenCV中DNN(深度神经网络)使用OpenPose模型实现手势识别详解

一、手部关键点检测 如图所示,为我们的手部关键点所在位置。第一步,我们需要检测手部21个关键点。我们使用深度神经网络DNN模块来完成这件事。通过使用DNN模块可以检测出手部21个关键点作为结果输出,具体请看源码。 二,openpose手势识别模型 OpenPose的原理基于卷积神经网…

【计算机图形学】End-to-End Affordance Learning for Robotic Manipulation

对RLAfford&#xff1a;End-to-End Affordance Learning for Robotic Manipulation的简单理解 1. 为什么要做这件事 在交互环境中学习如何操纵3D物体是RL中的挑战性问题。很难去训练出一个能够泛化到具有不同语义类别、不同几何形状和不同功能物体上的策略。 Visual Afforda…

粒子群算法对pi控制器进行参数优化,随时优化pi参数以控制直流无刷电机转速。

粒子群算法对pi控制器进行参数优化&#xff0c;随时优化pi参数以取得设定直流无刷电机转速。 PSO优化PID&#xff0c;用于BLDC速度控制 仿真平台为&#xff1a;MATLAB 采用的是Simulinkm程序相配合 仿真结果以及程序示例&#xff1a;

Armv8状态寄存器

Processor state AArch64没有与ARMv7当前程序状态寄存器直接对应的寄存器(CPSR)。在AArch64中&#xff0c;传统CPSR的组件以字段的形式提供可独立访问。这些统称为处理器状态(PSTATE)。 在AArch64中&#xff0c;通过执行ERET指令从异常中返回&#xff0c;这会导致要拷贝到PSTAT…

IEEE802.11v协议介绍

IEEE802.11v协议简介 协议全称:无线网络管理(Wireless Network Management) 批准日期:2011年2月 协议状态:并入802.11-2012 协议别名:BSS过渡管理 主要功能 支持AP和STA间交换:关于RF环境和拓扑状态的信息,以协助STA进行漫游决策支持STA之间交换:关于RF环境状态的信…