【数据结构】交换排序
⭐ 作者:小胡_不糊涂
🌱 作者主页:小胡_不糊涂的个人主页
📀 收录专栏:浅谈数据结构
💖 持续更文,关注博主少走弯路,谢谢大家支持 💖
冒泡、快速排序
- 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…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...
新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...
【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
iview框架主题色的应用
1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题,无需引入,直接可…...
LLaMA-Factory 微调 Qwen2-VL 进行人脸情感识别(二)
在上一篇文章中,我们详细介绍了如何使用LLaMA-Factory框架对Qwen2-VL大模型进行微调,以实现人脸情感识别的功能。本篇文章将聚焦于微调完成后,如何调用这个模型进行人脸情感识别的具体代码实现,包括详细的步骤和注释。 模型调用步骤 环境准备:确保安装了必要的Python库。…...
AD学习(3)
1 PCB封装元素组成及简单的PCB封装创建 封装的组成部分: (1)PCB焊盘:表层的铜 ,top层的铜 (2)管脚序号:用来关联原理图中的管脚的序号,原理图的序号需要和PCB封装一一…...

