java实现排序算法(上)
排序算法
冒泡排序
时间和空间复杂度
要点
- 每轮冒泡不断地比较比较相邻的两个元素,如果它们是逆序的,则需要交换它们的位置
- 下一轮冒泡,可以调整未排序的右边界,减少不必要比较
代码
public static int[] test(int[] array) {// 外层循环控制遍历次数for (int i = 0; i < array.length; i++) {// 内层循环控制每轮比较和交换for (int j = 0; j < array.length - i - 1; j++) {// 比较相邻两元素大小if (array[j] > array[j + 1]) {// 交换元素位置int temp = array[j + 1];array[j + 1] = array[j];array[j] = temp;}}}// 返回排序后的数组return array;
}
测试结果
public static void main(String[] args) {int[] array = {3,1,2,4,7,9};int[] ary = test(array);System.out.println(Arrays.toString(ary));}
选择排序
时间和空间复杂度
要点
- 每一轮选择,找出最大(最小)的元素,并把它交换到合适的位置
代码
public static int[] test(int[] array) {// 外循环遍历数组元素for (int i = 0; i < array.length; i++) {// 内循环从当前元素的下一个元素开始比较for (int j = i+1; j < array.length; j++) {// 如果前一个元素大于后一个元素,交换它们的位置if(array[i] > array[j]){int temp = array[j];array[j] = array[i];array[i] = temp;}}}// 返回排序后的数组return array;}
测试结果
public static void main(String[] args) {int[] array = {3,1,2,4,7,9};int[] ary = test(array);System.out.println(Arrays.toString(ary));}
堆排序
时间和空间复杂度
要点(如果这里看不懂的话,是需要去了解大顶堆这个数据结构的)
- 建立大顶堆
- 每次将堆顶元素最大值,交换到末尾,调整堆顶元素,让它重新符合大顶堆特性
代码
import java.util.Arrays;public class Heap {int[] array; // 存储堆元素的数组int size; // 堆的大小public Heap(int capacity) {this.array = new int[capacity];}public Heap(int[] array){this.array = array;this.size = array.length;heapify(); // 调用堆化方法,构建堆}/*** 建立堆*/private void heapify() {// 建立堆的过程实际上是找到最后一个非叶子节点for (int i = size/2-1; i >=0 ; i--) {// 接下来的循环中,i 是当前非叶子节点的索引down(i); // 对当前非叶子节点进行下潜操作,保证满足堆的性质}}// 下潜操作private void down(int i) {int left = i * 2 + 1; // 左子节点索引int right = left + 1; // 右子节点索引int max = i; // 初始化最大值索引为当前节点// 判断左子节点是否存在且大于当前节点if (left < size && array[left] > array[max]) {max = left;}// 判断右子节点是否存在且大于当前节点if (right < size && array[right] > array[max]) {max = right;}if (max != i) {// 交换当前节点与最大值节点swap(max, i);// 递归调用下潜操作,保证交换后的子树仍然满足堆的性质down(max);}}// 交换数组中两个位置的元素private void swap(int a, int b) {int temp = array[a];array[a] = array[b];array[b] = temp;}
}public static void main(String[] args) {int[] array = {1,2,3,4,5,6,7};Heap heap = new Heap(array);// 堆排序while (heap.size > 1) {// 将堆顶元素与堆尾元素交换heap.swap(0, heap.size - 1);// 堆大小减一heap.size--;// 对交换后的堆顶元素进行下潜操作,保证仍然满足堆的性质heap.down(0);}System.out.println(Arrays.toString(heap.array));
}
测试结果
插入排序
时间和空间复杂度
要点
- 将数组分为两部分[0----low-1][low----a.length-1]
- 左边[0-----low-1]是已排序部分
- 右边[low------a.length-1]是未排序部分
- 每次从未排序区域取出low位置的元素,插入到已排序区域
代码
public static int[] test(int[] array) {// 外层循环,从数组第二个元素开始for (int low = 1; low < array.length; low++) {// 记录当前元素值int t = array[low];// 从当前元素的前一个位置开始向前查找插入位置int i = low - 1;while (i >= 0 && t < array[i]) {// 如果当前元素小于已排序元素,将已排序元素后移一位array[i + 1] = array[i];i--;}// 找到插入位置,将当前元素插入if (i != low - 1) {array[i + 1] = t;}}// 返回排序后的数组return array;}
测试结果
public static void main(String[] args) {int[] array = {3,1,2,4,7,9};int[] ary = test(array);System.out.println(Arrays.toString(ary));}
希尔排序
时间和空间复杂度
要点
- 简单来说,就是分组实现插入,魅族元素间隙称为hap
- 每轮排序之后gap逐渐变小,直到gap为1完成排序
- 对插入排序的优化,让元素更快地交换到最终位置
代码
public static int[] test(int[] array) {// 此时的gap就是间隙for (int gap = array.length >> 1; gap >= 1 ; gap = gap >> 1) {for (int low = gap; low < array.length ; low++) {// 记录当前位置的元素值int t = array[low];// 初始化比较位置为当前位置的前一个位置int i = low - gap;// 当比较位置合法且当前元素值小于比较位置的元素值时进行插入排序while (i >= 0 && t < array[i]){// 将比较位置的元素往后移动gap个位置array[i + gap] = array[i];// 更新比较位置为前一个gap位置i -= gap;}// 如果实际插入位置不是当前位置的前一个gap位置,则进行插入操作if (i != low - gap){array[i + gap] = t;}}}// 返回排序后的数组return array;}
测试结果
public static void main(String[] args) {int[] array = {3,1,2,4,7,9};int[] ary = test(array);System.out.println(Arrays.toString(ary));}
相关文章:
java实现排序算法(上)
排序算法 冒泡排序 时间和空间复杂度 要点 每轮冒泡不断地比较比较相邻的两个元素,如果它们是逆序的,则需要交换它们的位置下一轮冒泡,可以调整未排序的右边界,减少不必要比较 代码 public static int[] test(int[] array) {// 外层循环控制遍历次数for (int i 0; i <…...
「算法」滑动窗口
前言 算法需要多刷题积累经验,所以我行文重心在于分析解题思路,理论知识部分会相对简略一些 正文 滑动窗口属于双指针,这两个指针是同向前行,它们所夹的区间就称为“窗口” 啥时候用滑动窗口? 题目涉及到“子序列…...
Windows11(非WSL)安装Installing llama-cpp-python with GPU Support
直接安装,只支持CPU。想支持GPU,麻烦一些。 1. 安装CUDA Toolkit (NVIDIA CUDA Toolkit (available at https://developer.nvidia.com/cuda-downloads) 2. 安装如下物件: gitpythoncmakeVisual Studio Community (make sure you install t…...
rtt设备io框架面向对象学习-脉冲编码器设备
目录 1.脉冲编码器设备基类2.脉冲编码器设备基类的子类3.初始化/构造流程3.1设备驱动层3.2 设备驱动框架层3.3 设备io管理层 4.总结5.使用 1.脉冲编码器设备基类 此层处于设备驱动框架层。也是抽象类。 在/ components / drivers / include / drivers 下的pulse_encoder.h定义…...
华为OD机试真题- 攀登者2-2024年OD统一考试(C卷)
题目描述: 攀登者喜欢寻找各种地图,并且尝试攀登到最高的山峰。地图表示为一维数组,数组的索引代表水平位置,数组的高度代表相对海拔高度。其中数组元素0代表地面。例如[0,1,4,3,1,0,0,1,2,3,1,2,1,0], 代表如下图所示的地图,地图中有两个山脉位置分别为 1,2,3,4,5和8,9,1…...
19.Qt 组合框的实现和应用
目录 前言: 技能: 内容: 1. 界面 2.槽 3.样式表 参考: 前言: 学习QCombox控件的使用 技能: 简单实现组合框效果 内容: 1. 界面 在ui编辑界面找到input widget里面的comboBoxÿ…...
【Linux】进程地址空间的理解
进程地址空间的理解 一,什么是程序地址空间二,页表和虚拟地址空间三,为什么要有进程地址空间 一,什么是程序地址空间 在我们写程序时,都会有这样下面的内存结构,来存放变量和代码等数据。 一个进程要执行…...
【Jvm】类加载机制(Class Loading Mechanism)原理及应用场景
文章目录 Jvm基本组成一.什么是JVM类的加载二.类的生命周期阶段1:加载阶段2:验证阶段3:准备阶段4:解析阶段5:初始化 三.类初始化时机四.类加载器1.引导类加载器(Bootstrap Class Loader)2.拓展类…...
Spring AOP的实现方式
AOP基本概念 Spring框架的两大核心:IoC和AOP AOP:Aspect Oriented Programming(面向切面编程) AOP是一种思想,是对某一类事情的集中处理 面向切面编程:切面就是指某一类特定的问题,所以AOP可…...
Linux------环境变量
目录 前言 一、环境变量 二、添加PATH环境变量 三、HOME环境变量 四、查看所有环境变量 1.指令获取 2.代码获取 2.1 getenv 2.2main函数的第三个参数 2.3 全局变量environ 五、环境变量存放地点 六、添加自命名环境变量 七、系统环境变量具有全局属性 八、环境变…...
计算机视觉所需要的数学基础
计算机视觉领域中使用的数学知识广泛而深入,以下是一些关键知识点及其在计算机视觉中的应用: 线性代数: - 矩阵运算:用于图像的表示和处理,如图像旋转、缩放、裁剪等。 - 向量空间:用于描述图像中的…...
ChatGPT魔法1: 背后的原理
1. AI的三个阶段 1) 上世纪50~60年代,计算机刚刚产生 2) Machine learning 3) Deep learning, 有神经网络, 最有代表性的是ChatGPT, GPT(Generative Pre-Trained Transformer) 2. 深度神经网络 llya Suts…...
【c/c++】获取时间
在一些应用的编写中我们有时候需要用到时间,或者需要一个“锚点”来确定一些数的值。在c/c中有两个用来确定时间的函数:time/gettimeofday 一、time time_t time(time_t *timer);time 函数返回当前时间的时间戳(自 1970 年 1 月 1 日以来经…...
uniapp富文本文字长按选中(用于复制,兼容H5、APP、小程序三端)
方案:使用u-parse的selectable属性 <u-parse :selectable"true" :html"content"></u-parse> 注意:u-parse直接使用是不兼容小程序的,需要对u-parse进行改造: 1. 查看u-parse源码发现小程序走到以…...
常见的几种Web安全问题测试简介
Web项目比较常见的安全问题 1.XSS(CrossSite Script)跨站脚本攻击 XSS(CrossSite Script)跨站脚本攻击。它指的是恶意攻击者往Web 页面里插入恶意html代码,当用户浏览该页之时,嵌入其中Web 里面的html 代码会被执行,从而达到恶意用户的特殊…...
linux信号机制[一]
目录 信号量 时序问题 原子性 什么是信号 信号如何产生 引入 信号的处理方法 常见信号 如何理解组合键变成信号呢? 如何理解信号被进程保存以及信号发送的本质? 为什么要有信号 信号怎么用? 样例代码 core文件有什么用呢&#…...
elementui 中el-date-picker 选择年后输出的是Wed Jan 01 2025 00:00:00 GMT+0800 (中国标准时间)
文章目录 问题分析 问题 在使用 el-date-picker 做只选择年份的控制器时,出现如下问题:el-date-picker选择年后输出的是Wed Jan 01 2025 00:00:00 GMT0800 (中国标准时间),输出了两次如下 分析 在 el-date-picker 中,我们使用…...
Redis 集群(Cluster)
集群概念 Redis 的哨兵模式,提高了系统的可用性,但是正在用来存储数据的还是 master 和 slave 节点,所有的数据都需要存储在单个 master 和 salve 节点中。 如果数据量很大,接近超出了 master / slave 所在机器的物理内存&#…...
260.【华为OD机试真题】信道分配(贪心算法-JavaPythonC++JS实现)
🚀点击这里可直接跳转到本专栏,可查阅顶置最新的华为OD机试宝典~ 本专栏所有题目均包含优质解题思路,高质量解题代码(Java&Python&C++&JS分别实现),详细代码讲解,助你深入学习,深度掌握! 文章目录 一. 题目-信道分配二.解题思路三.题解代码Python题解代码…...
Python打发无聊时光:3.实现简单电路的仿真
看到这个标题肯定有人会问:好好的multisim、 proteus之类的专门电路仿真软件不用,非要写一个简陋的python程序来弄,是不是精神失常了。实际上,我也不知道为什么要这么干,前两篇文章是我实际项目中的一些探索࿰…...
MyBatis-Plus:通用分页实体封装
分页查询实体:PageQuery package com.example.demo.demos.model.query;import com.baomidou.mybatisplus.core.metadata.OrderItem; import com.baomidou.mybatisplus.extension.plugins.pagination.Page; import lombok.Data; import org.springframework.util.St…...
MVC 、DDD(domain-driven design,软件主动学习业务)、中台、Java SPI(Service Provider Interface)
文章目录 引言I 单体架构DDD实现版本1.1 核心概念1.2 DDD四层架构规范1.3 案例1.4 请求转发流程II 领域服务调用2.1 菱形对称架构2.2 中台III Java SPI3.1 概念3.2 实现原理3.3 例子:本地SPI找服务see alsojava -cp<...
添加环境变量
目录 一、前言二、目的三、添加环境变量的步骤四、检查环境变量是否配置成功 一、前言 在很多地方在下载完软件后都需要添加环境变量方可使用。这里以要在终端使用MySQL为例来说一下,在安装好MySQL8.0版本的前提下,如何添加环境变量。 二、目的 添加环…...
学习Android的第十六天
目录 Android 自定义 Adapter Adapter 接口 SpinnerAdapter ListAdapter BaseAdapter 自定义 BaseAdapter 参考文档 Android ListView 列表控件 ListView 的属性和方法 表头表尾分割线的设置 列表从底部开始显示 android:stackFromBottom 设置点击颜色 cacheColorH…...
若依项目改造
ctrlalt l 格式化项目 alt f6 修改包和import包名 替换com.ruoyi 为 com.cj 替换若依版本为自己的版本 将ruoyi改成自己项目的英文名 修改中文名字 修改文件包名 修改有ruoyi的类名 : 验证码生成器包名修改:...
相机图像质量研究(34)常见问题总结:图像处理对成像的影响--拖影
系列文章目录 相机图像质量研究(1)Camera成像流程介绍 相机图像质量研究(2)ISP专用平台调优介绍 相机图像质量研究(3)图像质量测试介绍 相机图像质量研究(4)常见问题总结:光学结构对成像的影响--焦距 相机图像质量研究(5)常见问题总结:光学结构对成…...
算法学习系列(三十五):贪心(杂)
目录 引言一、合并果子(Huffman树)二、排队打水(排序不等式)三、货仓选址(绝对值不等式)四、耍杂技的牛(推公式) 引言 上一篇文章也说过了这个贪心问题没有一个规范的套路和模板&am…...
嵌入式面试:瑞芯微
文章目录 一、2024 秋招1.1 IIC的速率范围 :1.2 linux驱动子系统汇总 :1.3 linux关抢占情况汇总 :1.4 操作或者读写一个文件时,从用户态到内核态再到物理介质的流程(考点:虚拟文件系统) : 一、2024 秋招 1…...
【性能测试】分布式压测之locust和Jmeter的使用
受限于单台机器的配置问题,我们在单台机器上达不到一个很高的压测并发数,那这个时候就需要引入分布式压测 分布式压测原理: 一般通过局域网把不同测试计算机链接到一起,达到测试共享、分散操作、集中管理的目的。 选择一台作为…...
ABC341A-D题解
文章目录 A题目AC Code: B题目AC Code: C题目AC Code: D题目你以为这就完了? 时间复杂度分析:AC Code: E A 题目 这个没什么好说的,就先输出一个 1,再输出 n n n 个 01就大功告成…...
计算机网络——07协议层次及服务模型
协议层次及服务模型 协议层次 网络是一个复杂的系统 网络功能复杂:数字信号的物理信号承载、点到点、路由、rdt、进程区分、应用等现实来看,网络的许多构成元素和设备: 主机路由器各种媒体的链路应用协议硬件,软件 问题是&am…...
Netty Review - NIO空轮询及Netty的解决方案源码分析
文章目录 Pre问题说明NIO CodeNetty是如何解决的?源码分析入口源码分析selectCntselectRebuildSelector Pre Netty Review - ServerBootstrap源码解析 Netty Review - NioServerSocketChannel源码分析 Netty Review - 服务端channel注册流程源码解析 问题说明 N…...
PAM | 账户安全 | 管理
PAM PAM(Pluggable Authentication Modules,可插入式身份验证模块)是一个灵活的身份验证系统,允许我们通过配置和组合各种模块来实现不同的身份验证策略。 在 Linux 或类 Unix 系统中,常见的 PAM 模块包括以下几种类…...
Leetcode 16-20题
最接近的三数之和 给定整数数组和目标值target,从数组中选出三个整数,使得和与target最接近,并返回三数之和。保证恰好存在一个解。 和上一题类似,我们先对整数数组排序,然后固定i,枚举j,找到满…...
【开源训练数据集1】神经语言程式(NLP)项目的15 个开源训练数据集
一个聊天机器人需要大量的训练数据,以便在无需人工干预的情况下快速解决用户的询问。然而,聊天机器人开发的主要瓶颈是获取现实的、面向任务的对话数据来训练这些基于机器学习的系统。 我们整理了训练聊天机器人所需的对话数据集,包括问答数据、客户支持数据、对话数据和多…...
【AIGC】Stable Diffusion的ControlNet参数入门
Stable Diffusion 中的 ControlNet 是一种用于控制图像生成过程的技术,它可以指导模型生成特定风格、内容或属性的图像。下面是关于 ControlNet 的界面参数的详细解释: 低显存模式 是一种在深度学习任务中用于处理显存受限设备的技术。在这种模式下&am…...
静态curl库编译与使用(c++)
静态curl库编译与使用 静态curl库编译与使用:mingw https://curl.se/windows/ // 测试:设置URL地址 // curl_easy_setopt(curlHandle, CURLOPT_URL, “https://ipinfo.io/json”); // curl_easy_setopt(curlHandle, CURLOPT_SSL_VERIFYPEER, 0L); // c…...
element 表单提交图片(表单上传图片)
文章目录 使用场景页面效果前端代码 使用场景 vue2 element 表单提交图片 1.点击【上传图片】按钮择本地图片(只能选择一张图片)后。 2.点击图片,支持放大查看。 3.点击【保存】按钮,提交表单。 页面效果 前端代码…...
Android 15 第一个开发者预览版
点击查看:first-developer-preview-android15 点击查看:Get Android 15 2024年2月16日,谷歌发布 Android 15 第一个开发者预览版 翻译 由工程副总裁戴夫伯克发布 今天,我们发布了Android 15的首个开发者预览版,这样我们的开发者就…...
anomalib1.0学习纪实-续1:增加新算法
0、基本信息 现在我要增加一个新算法:DDAD 他的代码,可以在github中找到:GitHub - arimousa/DDAD 一、基础操作: 1、修改anomalib\src\anomalib\models\__init__.py 我增加的第33行和61行, 2、 增加ddad文件夹和文…...
Java+Vue+MySQL,国产动漫网站全栈升级
✍✍计算机编程指导师 ⭐⭐个人介绍:自己非常喜欢研究技术问题!专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目:有源码或者技术上的问题欢迎在评论区一起讨论交流! ⚡⚡ Java实战 |…...
机器人常用传感器分类及一般性要求
机器人传感器的分类 传感技术是先进机器人的三大要素(感知、决策和动作)之一。根据用途不同,机器人传感器可以分为两大类:用于检测机器人自身状态的内部传感器和用于检测机器人相关环境参数的外部传感器。 内部传感器 内部传感…...
C++-opencv的imread、imshow、waitkey、namedWindow
在C中使用OpenCV时,imread和imshow是两个非常基础且常用的函数,用于读取图像和显示图像。以下是这两个函数的简要说明和如何一起使用它们的示例。 imread函数 imread用于从指定的文件路径读取图像。它将图像读入为cv::Mat对象,这是OpenCV中…...
开源语音识别faster-whisper部署教程
1. 资源下载 源码地址 模型下载地址: large-v3模型:https://huggingface.co/Systran/faster-whisper-large-v3/tree/main large-v2模型:https://huggingface.co/guillaumekln/faster-whisper-large-v2/tree/main large-v2模型:…...
使用IntelliJ IDEA配置Maven (入门)
在使用IntelliJ IDEA进行Java开发时,配置Maven是至关重要的一步,因为它可以帮助你管理项目的依赖和构建过程。以下是我在使用IntelliJ IDEA配置Maven的实践过程,以及一些技术笔记和职场感悟。 工作实践与项目复盘 下载Maven: 访问…...
汽车金融市场研究:预计2029年将达到482亿美元
汽车金融公司作为汽车流通产业链的重要一环,认真贯彻落实国家有关政策,采取多种措施助力汽车产业发展,为促进推动汽车消费、助力畅通汽车产业链、支持稳定宏观经济大盘发挥了积极作用。 益于国内疫情得到有效控制,我国经济持续稳定…...
关于举办第十五届蓝桥杯大赛电子赛5G全网规划与建设赛项的通知
关于举办第十五届蓝桥杯大赛电子赛 5G全网规划与建设赛项的通知 各相关院校: 第十五届蓝桥杯大赛通知已于2023年9月27日在蓝桥杯大赛官网发布,现就电子赛5G全网规划与建设赛项报名事宜,公布如下: 一、赛项概述 5G全网规划与建设…...
Vue3快速上手(七) ref和reactive对比
一、ref和reactive对比 表格形式更加直观吧: 项目refreactive是否支持基本类型支持不支持是否支持对象类型支持支持对象类型是否支持属性直接赋值不支持,需要.value支持是否支持直接重新分配对象支持,因为操作的.value不支持,需…...
8、内网安全-横向移动RDPKerberos攻击SPN扫描WinRMWinRS
用途:个人学习笔记,有所借鉴,欢迎指正 目录 一、域横向移动-RDP-明文&NTLM 1.探针服务: 2.探针连接: 3.连接执行: 二、域横向移动-WinRM&WinRS-明文&NTLM 1.探针可用: 2.连接…...
《数据结构与算法之美》读书笔记
《数据结构与算法之美》读书笔记 写在前面 这本书的大部分内容比较浅显,因此只挑DSAA课程上没有涉及或没有深入讨论的点总结 第二章 数组相关 提高传统数组插入/删除数据效率的方法: 如果插入的数据不要求有序,可以直接把某位的原数据替换…...