当前位置: 首页 > 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…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist

现象&#xff1a; android studio报错&#xff1a; [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决&#xff1a; 不要动CMakeLists.…...

Python训练营-Day26-函数专题1:函数定义与参数

题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一个名为 calculate_circle_area 的函数&#xff0c;该函数接收圆的半径 radius 作为参数&#xff0c;并返回圆的面积。圆的面积 π * radius (可以使用 math.pi 作为 π 的值)要求&#xff1a;函数接收一个位置参数 radi…...