【数据结构】交换排序
⭐ 作者:小胡_不糊涂
🌱 作者主页:小胡_不糊涂的个人主页
📀 收录专栏:浅谈数据结构
💖 持续更文,关注博主少走弯路,谢谢大家支持 💖
冒泡、快速排序
- 1. 冒泡排序
- 2. 快速排序
1. 冒泡排序
交换排序基本思想:所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。
代码实现:
/**冒泡排序*1.时间复杂度:O(N^2)*2.空间复杂度:O(1)*3.稳定性:稳定* @param array*/public static void bubbleSort(int[] array){//i:记录躺数//j<array.length-i-1: -1 为了防止越界for(int i=0;i<array.length;i++){for(int j=0;j<array.length-i-1;j++){if(array[j+1]<array[j]){int tmp=array[j+1];array[j+1]=array[j];array[j]=tmp;}}}}
2. 快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其**基本思想为:**任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。
代码实现:
/*** 快速排序-》* 时间复杂度:* 最好的情况下:O(N*logN)* 最坏情况下:O(N^2) 逆序/有序* 空间复杂度:* 最好的情况下:O(logN)* 最坏情况下:O(N) 逆序/有序* 稳定性:不稳定* @param array*/
// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int[] array, int left, int right)
{if(right - left <= 1)return;// 按照基准值对array数组的 [left, right)区间中的元素进行划分int div = partion(array, left, right);// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)// 递归排[left, div)QuickSort(array, left, div);// 递归排[div+1, right)QuickSort(array, div+1, right);
}
private static void swap(int[] array,int i,int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;
}
上述为快速排序递归实现的主框架,发现与二叉树前序遍历规则非常像,在写递归框架时可想想二叉树前序遍历规则即可快速写出来,后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
将区间按照基准值划分为左右两半部分的常见方式有:
1. Hosre版
/*** @param array* @param left* @param right* @return*/public static int partion(int[] array,int left,int right){int i=left;int privot=array[left];//基准元素while(left<right){//大于privot的放在右边,小于的放在左边while(left<right&&array[right]>=privot){right--;}while(left<right && array[left]<=privot){left++;}swap(array,right,left);//right<privot<left}swap(array,i,left);//将基准元素放回return left;}
2. 挖坑法
先将一个数据存放在临时变量key中,形成一个空缺位。一般选取第一个元素。
/*** 挖坑法* @param array* @param left* @param right* @return*/public static int partion(int[] array,int left,int right){int privot=array[left];while(left<right){//从右边开始while(left<right&&array[right]>=privot){right--;}array[left]=array[right];while(left<right&&array[left]<=privot){left++;}array[right]=array[left];}array[left]=privot;//将基准元素填入空位return left;}
3. 前后指针法
初始时,设置两个指针。prev指向序列开头,cur指针指向prev的后一个位置
/*** 前后指针法:* @param array* @param left* @param right* @return*/public static int partion(int[] array,int left,int right){int prev=left;int cur=left+1;while(cur<=right){while(array[cur]<array[left] &&array[cur]!=array[++prev]){swap(array,prev,cur);}cur++;}swap(array,prev,left);return prev;}
以上3种方式,每次划分之后的前后顺序有可能是不一样的
相关文章:
【数据结构】交换排序
⭐ 作者:小胡_不糊涂 🌱 作者主页:小胡_不糊涂的个人主页 📀 收录专栏:浅谈数据结构 💖 持续更文,关注博主少走弯路,谢谢大家支持 💖 冒泡、快速排序 1. 冒泡排序2. 快速…...
腾讯云2023年双11服务器优惠活动及价格表
腾讯云2023年双11大促活动正在火热进行中,腾讯云推出了一系列服务器优惠活动,云服务器首年1.8折起,买1年送3个月!境外云服务器15元/月起,买更多省更多!下面给大家分享腾讯云双11服务器优惠活动及价格表&…...
PointNet++复现、论文和代码研读
文章目录 复现1.创建虚拟环境并进入2.安装pytorch3.分割模型的训练和测试3.1.下载数据处理数据3.2.训练分割模型3.3分割模型的测试 4.分类模型的训练和测试 论文研读制作自己的数据集流程分割模型数据集准备 复现 https://github.com/yanx27/Pointnet_Pointnet2_pytorch 1.创…...
轨迹规划 | 图解路径跟踪PID算法(附ROS C++/Python/Matlab仿真)
目录 0 专栏介绍1 PID控制基本原理2 基于PID的路径跟踪3 仿真实现3.1 ROS C实现3.2 Python实现3.3 Matlab实现 0 专栏介绍 🔥附C/Python/Matlab全套代码🔥课程设计、毕业设计、创新竞赛必备!详细介绍全局规划(图搜索、采样法、智能算法等)&a…...
吴恩达《机器学习》1-3:监督学习
一、监督学习 例如房屋价格的数据集。在监督学习中,我们将已知的房价作为"正确答案",并将这些价格与房屋的特征数据一起提供给学习算法。学习算法使用这些已知答案的数据来学习模式和关系,以便在未知情况下预测其他房屋的价格。这就…...
Flutter PopupMenuButton下拉菜单
下拉菜单是移动应用交互中一种常见的交互方式,可以使用下拉列表来展示多个内容标签,实现页面引导的作用。在Flutter开发中,实现下拉弹框主要有两种方式,一种是继承Dialog组件使用自定义布局的方式实现,另一种则是使用官方的PopupMenuButton组件进行实现。 如果没有特殊的…...
国家数据局正式揭牌,数据专业融合型人才迎来发展良机【文末送书五本】
国家数据局正式揭牌,数据专业融合型人才迎来发展良机 国家数据局正式揭牌,数据专业融合型人才迎来发展良机 摘要书籍简介数据要素安全流通Python数据挖掘:入门、进阶与实用案例分析数据保护:工作负载的可恢复性Data Mesh权威指南分…...
H5游戏源码分享-像素小鸟游戏(类似深海潜艇)
H5游戏源码分享-像素小鸟游戏(类似深海潜艇) 点击屏幕控制小鸟的飞行高度 整个小游戏就用JS完成 项目地址:https://download.csdn.net/download/Highning0007/88483228 <!DOCTYPE HTML> <html><head><meta http-equiv…...
Vue 3 响应式对象:ref 和 reactive 的使用和区别
🎉🎉欢迎来到我的CSDN主页!🎉🎉 🏅我是尘缘,一个在CSDN分享笔记的博主。📚📚 👉点击这里,就可以查看我的主页啦!👇&#x…...
H5游戏源码分享-密室逃脱小游戏(考验反应能力)
H5游戏源码分享-密室逃脱小游戏(考验反应能力) 预判安全位置,这个需要快速的反应能力 源码 <!DOCTYPE html> <html> <head> <meta http-equiv"Content-Type" content"text/html; charsetutf-8" /&…...
【LeetCode刷题-哈希】--706.设计哈希映射
706.设计哈希映射 class MyHashMap {private class Pair{private int key;private int value;public Pair(int key ,int value){this.key key;this.value value;}public int getKey(){return key;}public int getValue(){return value;}public void setValue(int value){this…...
前端 : 用HTML ,CSS ,JS 做一个点名器
1.HTML: <body><div id "content"><div id"top"><div id "name">XAiot2302班点名器</div></div><div id "center"><div id "word">你准备好了吗?</di…...
css:button实现el-radio效果
先看最终效果: 思路: 一、 首先准备好按钮内容:const a [one,two,three] 将按钮循环展示出来,并设置一些样式,将按钮背景透明: <button v-for"(item,index) in a" :key"in…...
算法工程师-机器学习-数据科学家面试准备4-ML系统设计
https://github.com/LongxingTan/Machine-learning-interview 算法工程师-机器学习-数据科学家面试准备1- 概述 外企和国外公司、春招、秋招算法工程师-机器学习-数据科学家面试准备2- Leetcode 300算法工程师-机器学习-数据科学家面试准备3-系统设计算法工程师-机器学习-数据…...
git重装后如何连接以前项目
git重装后如何连接以前项目 1、配置秘钥 点击 Git Bash Here,进入命令操作窗口 生成本地git仓库秘钥: 1、填写自己邮箱 2、一直回车 ssh-keygen -t rsa -C “xxxxxqq.com”3、使用cat查看生成的秘钥,粘贴并设置到gitee上 cat ~/.ssh/id_r…...
【java学习—十】TreeSet集合(5)
文章目录 1. TreeSet1.1. 自然排序1.2. 定制排序 1. TreeSet TreeSet 是 SortedSet 接口的实现类, TreeSet 可以确保集合元素处于排序状态。 TreeSet 支持两种排序方法:自然排序和定制排序。默认情况下, TreeSet 采用自然排序。 1.1.…...
JMeter的使用,傻瓜式学习【上】
目录 前言 1、JMeter元件及基本使用作用域(简述) 1.1、基本元件 1.2、作用域的原则 1.3、元件执行顺序 3、JMeter三个重要组件 3.1、线程组 案例: 3.2、HTTP请求 3.3、查看结果树 响应体中,中文乱码解决方案࿱…...
主定理(一般式)
主定理(Master Theorem)是用于分析递归算法时间复杂度的一个重要工具。它适用于形式化定义的一类递归关系,通常采用分治策略解决问题的情况。 目录 主定理简化版的局限主定理一般形式情况1: n l o g b a n^{log_{b}{a}} nlogba …...
WLAN的组网架构和工作原理
目录 WLAN的组网架构 FAT AP架构 AC FIT AP架构 敏捷分布式AP 下一代园区网络:智简园区(大中型园区网络) WLAN工作原理 WLAN工作流程 1.AP上线 (1)AP获取IP地址; (2)AP发…...
使用OBS Browser+访问华为云OBS存储【Windows】
背景 项目中使用华为云 S3 存储,java 代码中通过华为云 OBS 提供的esdk-obs-java 来访问文件。 但是,通过 JAVA SDK 方式不太方便运维,所以我们需要一款可视化的客户端软件。 华为云 OBS 自身也提供了一款客户端软件,名为 OBS Browser+。 OBS Browser+简介 OBS Browse…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...
1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
Pinocchio 库详解及其在足式机器人上的应用
Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库,专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性,并提供了一个通用的框架&…...

