当前位置: 首页 > news >正文

【数据结构】交换排序

⭐ 作者:小胡_不糊涂
🌱 作者主页:小胡_不糊涂的个人主页
📀 收录专栏:浅谈数据结构
💖 持续更文,关注博主少走弯路,谢谢大家支持 💖

冒泡、快速排序

  • 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种方式,每次划分之后的前后顺序有可能是不一样的

相关文章:

【数据结构】交换排序

⭐ 作者&#xff1a;小胡_不糊涂 &#x1f331; 作者主页&#xff1a;小胡_不糊涂的个人主页 &#x1f4c0; 收录专栏&#xff1a;浅谈数据结构 &#x1f496; 持续更文&#xff0c;关注博主少走弯路&#xff0c;谢谢大家支持 &#x1f496; 冒泡、快速排序 1. 冒泡排序2. 快速…...

腾讯云2023年双11服务器优惠活动及价格表

腾讯云2023年双11大促活动正在火热进行中&#xff0c;腾讯云推出了一系列服务器优惠活动&#xff0c;云服务器首年1.8折起&#xff0c;买1年送3个月&#xff01;境外云服务器15元/月起&#xff0c;买更多省更多&#xff01;下面给大家分享腾讯云双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 专栏介绍 &#x1f525;附C/Python/Matlab全套代码&#x1f525;课程设计、毕业设计、创新竞赛必备&#xff01;详细介绍全局规划(图搜索、采样法、智能算法等)&a…...

吴恩达《机器学习》1-3:监督学习

一、监督学习 例如房屋价格的数据集。在监督学习中&#xff0c;我们将已知的房价作为"正确答案"&#xff0c;并将这些价格与房屋的特征数据一起提供给学习算法。学习算法使用这些已知答案的数据来学习模式和关系&#xff0c;以便在未知情况下预测其他房屋的价格。这就…...

Flutter PopupMenuButton下拉菜单

下拉菜单是移动应用交互中一种常见的交互方式,可以使用下拉列表来展示多个内容标签,实现页面引导的作用。在Flutter开发中,实现下拉弹框主要有两种方式,一种是继承Dialog组件使用自定义布局的方式实现,另一种则是使用官方的PopupMenuButton组件进行实现。 如果没有特殊的…...

国家数据局正式揭牌,数据专业融合型人才迎来发展良机【文末送书五本】

国家数据局正式揭牌&#xff0c;数据专业融合型人才迎来发展良机 国家数据局正式揭牌&#xff0c;数据专业融合型人才迎来发展良机 摘要书籍简介数据要素安全流通Python数据挖掘&#xff1a;入门、进阶与实用案例分析数据保护&#xff1a;工作负载的可恢复性Data Mesh权威指南分…...

H5游戏源码分享-像素小鸟游戏(类似深海潜艇)

H5游戏源码分享-像素小鸟游戏&#xff08;类似深海潜艇&#xff09; 点击屏幕控制小鸟的飞行高度 整个小游戏就用JS完成 项目地址&#xff1a;https://download.csdn.net/download/Highning0007/88483228 <!DOCTYPE HTML> <html><head><meta http-equiv…...

Vue 3 响应式对象:ref 和 reactive 的使用和区别

&#x1f389;&#x1f389;欢迎来到我的CSDN主页&#xff01;&#x1f389;&#x1f389; &#x1f3c5;我是尘缘&#xff0c;一个在CSDN分享笔记的博主。&#x1f4da;&#x1f4da; &#x1f449;点击这里&#xff0c;就可以查看我的主页啦&#xff01;&#x1f447;&#x…...

H5游戏源码分享-密室逃脱小游戏(考验反应能力)

H5游戏源码分享-密室逃脱小游戏&#xff08;考验反应能力&#xff09; 预判安全位置&#xff0c;这个需要快速的反应能力 源码 <!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&#xff1a; <body><div id "content"><div id"top"><div id "name">XAiot2302班点名器</div></div><div id "center"><div id "word">你准备好了吗?</di…...

css:button实现el-radio效果

先看最终效果&#xff1a; ​​​ 思路&#xff1a; 一、 首先准备好按钮内容&#xff1a;const a [one,two,three] 将按钮循环展示出来&#xff0c;并设置一些样式&#xff0c;将按钮背景透明&#xff1a; <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&#xff0c;进入命令操作窗口 生成本地git仓库秘钥&#xff1a; 1、填写自己邮箱 2、一直回车 ssh-keygen -t rsa -C “xxxxxqq.com”3、使用cat查看生成的秘钥&#xff0c;粘贴并设置到gitee上 cat ~/.ssh/id_r…...

【java学习—十】TreeSet集合(5)

文章目录 1. TreeSet1.1. 自然排序1.2. 定制排序 1. TreeSet TreeSet 是 SortedSet 接口的实现类&#xff0c; TreeSet 可以确保集合元素处于排序状态。     TreeSet 支持两种排序方法&#xff1a;自然排序和定制排序。默认情况下&#xff0c; TreeSet 采用自然排序。 1.1.…...

JMeter的使用,傻瓜式学习【上】

目录 前言 1、JMeter元件及基本使用作用域&#xff08;简述&#xff09; 1.1、基本元件 1.2、作用域的原则 1.3、元件执行顺序 3、JMeter三个重要组件 3.1、线程组 案例&#xff1a; 3.2、HTTP请求 3.3、查看结果树 响应体中&#xff0c;中文乱码解决方案&#xff1…...

主定理(一般式)

主定理&#xff08;Master Theorem&#xff09;是用于分析递归算法时间复杂度的一个重要工具。它适用于形式化定义的一类递归关系&#xff0c;通常采用分治策略解决问题的情况。 目录 主定理简化版的局限主定理一般形式情况1&#xff1a; n l o g b a n^{log_{b}{a}} nlogb​a …...

WLAN的组网架构和工作原理

目录 WLAN的组网架构 FAT AP架构 AC FIT AP架构 敏捷分布式AP 下一代园区网络&#xff1a;智简园区&#xff08;大中型园区网络&#xff09; WLAN工作原理 WLAN工作流程 1.AP上线 &#xff08;1&#xff09;AP获取IP地址&#xff1b; &#xff08;2&#xff09;AP发…...

使用OBS Browser+访问华为云OBS存储【Windows】

背景 项目中使用华为云 S3 存储,java 代码中通过华为云 OBS 提供的esdk-obs-java 来访问文件。 但是,通过 JAVA SDK 方式不太方便运维,所以我们需要一款可视化的客户端软件。 华为云 OBS 自身也提供了一款客户端软件,名为 OBS Browser+。 OBS Browser+简介 OBS Browse…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...

wpf在image控件上快速显示内存图像

wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像&#xff08;比如分辨率3000*3000的图像&#xff09;的办法&#xff0c;尤其是想把内存中的裸数据&#xff08;只有图像的数据&#xff0c;不包…...

LangFlow技术架构分析

&#x1f527; LangFlow 的可视化技术栈 前端节点编辑器 底层框架&#xff1a;基于 &#xff08;一个现代化的 React 节点绘图库&#xff09; 功能&#xff1a; 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...

SpringAI实战:ChatModel智能对话全解

一、引言&#xff1a;Spring AI 与 Chat Model 的核心价值 &#x1f680; 在 Java 生态中集成大模型能力&#xff0c;Spring AI 提供了高效的解决方案 &#x1f916;。其中 Chat Model 作为核心交互组件&#xff0c;通过标准化接口简化了与大语言模型&#xff08;LLM&#xff0…...