【算法基础】选择排序算法 - JAVA
一、算法基础
1.1 什么是选择排序
选择排序是一种简单直观的排序算法,它的工作原理是:首先在未排序序列中找到最小(或最大)元素,存放到排序序列的起始位置,然后再从剩余未排序元素中继续寻找最小(或最大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
1.2 选择排序的基本思想
选择排序的核心思想是:
- 将输入数据分为已排序区域和未排序区域
- 不断从未排序区域选择最小元素,放入已排序区域的末尾
- 重复上述过程直到全部排序完成
1.3 时间复杂度
选择排序的时间复杂度分析如下:
- 最好情况时间复杂度:O(n²)
- 最坏情况时间复杂度:O(n²)
- 平均时间复杂度:O(n²)
无论输入数据是否已经部分排序,选择排序始终需要进行 n(n-1)/2 次比较,因此其时间复杂度总是 O(n²)。
1.4 空间复杂度
选择排序是一种原地排序算法,它只需要一个用于交换的临时变量,因此空间复杂度为 O(1)。
二、Java实现
2.1 基础实现
public class SelectionSort {public static void selectionSort(int[] arr) {int n = arr.length;// 外层循环控制已排序区域的边界for (int i = 0; i < n - 1; i++) {// 找出未排序区域中的最小值索引int minIndex = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}// 将找到的最小值与未排序区域的第一个元素交换if (minIndex != i) {int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}}// 测试代码public static void main(String[] args) {int[] arr = {64, 25, 12, 22, 11};selectionSort(arr);System.out.println("排序后的数组:");for (int i : arr) {System.out.print(i + " ");}}
}
2.2 算法步骤解析
- 初始状态:整个数组视为未排序区域
- 第一次迭代:
- 在整个数组中找到最小元素
- 将其与数组第一个元素交换位置
- 数组第一个元素现在位于正确位置
- 第二次迭代:
- 从第二个元素开始,在剩余未排序元素中找到最小值
- 将其与数组第二个元素交换位置
- 重复过程:继续执行,直到所有元素都排序完毕
三、选择排序的特点
3.1 优点
- 实现简单,易于理解和编码
- 交换次数少:每次内循环只需要进行一次交换操作,最多进行 n-1 次交换
- 原地排序:不需要额外的存储空间
- 稳定性可控:可以实现为稳定排序算法(通过特定实现方式)
3.2 缺点
- 时间效率低:无论输入如何,时间复杂度始终为 O(n²)
- 不适合大规模数据:当数据量大时,性能显著下降
- 不会提前终止:即使数组已经排序,算法仍会执行完所有步骤
四、算法优化方案
4.1 双向选择排序
双向选择排序在每次迭代中同时查找最小值和最大值,减少了循环次数:
public static void bidirectionalSelectionSort(int[] arr) {int left = 0;int right = arr.length - 1;while (left < right) {int minIndex = left;int maxIndex = left;// 找出最小值和最大值for (int i = left + 1; i <= right; i++) {if (arr[i] < arr[minIndex]) {minIndex = i;}if (arr[i] > arr[maxIndex]) {maxIndex = i;}}// 将最小值放到左边if (minIndex != left) {int temp = arr[left];arr[left] = arr[minIndex];arr[minIndex] = temp;// 如果最大值是left,那么交换后最大值位置变为minIndexif (maxIndex == left) {maxIndex = minIndex;}}// 将最大值放到右边if (maxIndex != right) {int temp = arr[right];arr[right] = arr[maxIndex];arr[maxIndex] = temp;}left++;right--;}
}
4.2 使用堆数据结构
可以使用最小堆来优化选择排序:
- 构建一个最小堆 O(n)
- 依次取出堆顶元素 O(log n)
这种方法实际上就是堆排序,时间复杂度降低到 O(n log n)。
五、实例分析
5.1 示例数组排序过程
以数组 [64, 25, 12, 22, 11]
为例:
- 第一次迭代:
- 找到最小值 11(索引 4)
- 交换11和64:
[11, 25, 12, 22, 64]
- 已排序:[11],未排序:[25, 12, 22, 64]
- 第二次迭代:
- 在剩余部分找到最小值 12(索引 2)
- 交换12和25:
[11, 12, 25, 22, 64]
- 已排序:[11, 12],未排序:[25, 22, 64]
- 第三次迭代:
- 在剩余部分找到最小值 22(索引 3)
- 交换22和25:
[11, 12, 22, 25, 64]
- 已排序:[11, 12, 22],未排序:[25, 64]
- 第四次迭代:
- 在剩余部分找到最小值 25(索引 3)
- 不需要交换(已在正确位置)
- 已排序:[11, 12, 22, 25],未排序:[64]
- 排序完成:
[11, 12, 22, 25, 64]
5.2 性能分析
对比不同输入规模的性能表现:
- 小规模数据(n ≤ 50):选择排序性能可接受
- 中等规模数据(50 < n ≤ 1000):性能明显下降
- 大规模数据(n > 1000):性能严重下降,不推荐使用
六、应用场景
6.1 适用场景
- 小规模数据排序:当数据量较小时,选择排序简单易实现
- 对交换操作敏感的场景:选择排序的交换次数最多为 n-1 次
- 辅助教学:作为排序算法的基础教学示例
- 内存受限的嵌入式系统:实现简单且空间复杂度低
6.2 不适用场景
- 大规模数据排序:性能太低,应选择更高效的算法
- 几乎已排序的数据:选择排序无法利用数据的部分有序性
七、总结
选择排序是一种简单直观的排序算法,核心思想是不断从未排序区域中选择最小元素放入已排序区域。
核心要点:
- 时间复杂度始终为 O(n²),无论输入如何
- 空间复杂度为 O(1),是一种原地排序算法
- 交换次数较少,最多进行 n-1 次交换
- 实现简单,代码易于理解和编写
- 对于大型数据集不推荐使用
选择排序虽然不是最高效的排序算法,但它的简单性和低空间复杂度使其在特定场景下仍有价值。对于编程初学者来说,理解选择排序有助于掌握排序算法的基本概念及其实现方法。
相关文章:
【算法基础】选择排序算法 - JAVA
一、算法基础 1.1 什么是选择排序 选择排序是一种简单直观的排序算法,它的工作原理是:首先在未排序序列中找到最小(或最大)元素,存放到排序序列的起始位置,然后再从剩余未排序元素中继续寻找最小…...
FastAPI 与数据库交互示例
目录 安装必要的包完整代码示例运行应用使用说明API 端点说明代码解析 下面将创建一个简单的 FastAPI 应用程序,演示如何与 SQLite 数据库进行交互。这个例子包括创建、读取、更新和删除(CRUD)操作。 安装必要的包 首先,需要安装…...
(六——下)RestAPI 毛子(Http resilience/Refit/游标分页)
文章目录 项目地址一、Refit1.1 安装需要的包1.2 创建接口IGitHubApi1.3 创建RefitGitHubService1. 实现接口2. 注册服务 1.4 修改使用方法 二、Http resilience2.1 安装所需要的包2.2 创建resilience pipeline简单版2.3 创建全局的resilience处理1. 创建清理全局ResilienceHan…...
Rust 学习笔记:关于枚举与模式匹配的练习题
Rust 学习笔记:关于枚举与模式匹配的练习题 Rust 学习笔记:关于枚举与模式匹配的练习题以下程序能否通过编译?若能,输出是什么?考虑这两种表示结果类型的方式,若计算成功,则包含值 T;…...
父子组件双向绑定
v-model 语法糖实现 vue中我们在input中可以直接使用v-model来完成双向绑定,这个时候 v-model 通常会帮我们完成两件事: v-bind:value的数据绑定@input的事件监听如果我们现在封装了一个组件,其他地方在使用这个组件时,是否也可以使用v-model来同时完成这两个功能呢? 当我…...
系统思考与第一性原理
最近一直有客户提到“第一性原理”,希望借此穿透纷繁复杂的现象,看清事情的本质。我第一反应是:这与系统思考中的冰山模型不谋而合。 冰山模型中提到:我们看到的只是表面事件,事件背后有趋势,趋势背后有结…...
基于Redis实现-UV统计
基于Redis实现-UV统计 本文将使用HyperLogLog来实现UV统计。 首先我们搞懂两个概念: UV:全称Unique Visitor,也叫独立访客量,是指通过互联网访问、浏览这个网页的自然人。1天内同一个用户多次访问该网站,只记录一次…...
【iOS】类与对象底层探索
类与对象底层探索 Clang探索对象本质objc_setProperty源码探索cls与类的关联原理isa的类型isa_t原理探索 类&类的结构什么是元类NSObject到底有几个isa走位&继承关系图objc_class&objc_object 类结构分析计算cache类中的内存大小获取bits属性列表(prope…...
2025年- H18-Lc126-54.螺旋矩阵(矩阵)---java版
1.题目描述 2.思路* 思路1: 补充2: directions[1][0] // 表示“下”这个方向的行增量(1) directions[1][1] // 表示“下”这个方向的列增量(0) int[][] directions {{0, 1}, {1, 0}, {0, -1}, {-…...
Paddle Serving|部署一个自己的OCR识别服务器
前言 之前使用C部署了自己的OCR识别服务器,Socket网络传输部分是自己写的,回过头来一看,自己犯傻了,PaddleOCR本来就有自己的OCR服务器项目,叫PaddleServing,这里记录一下部署过程。 1 下载依赖环境 1.1 …...
yolov5 本地训练
YOLOv5 | Kaggle 直接gitclone他的源码用Vscode看(也可以直接把jupyter下下来) 他要1.8,我的是2.7,他这个代码可能有点年头了 两年前了 他的环境 我的环境 我就是不懂为什么清华源的torch windows默认下出来是cpu版本 . 在终端…...
同城跑腿小程序帮取帮送接单抢单预约取件智能派单同城配送全开源运营版源码优创
一、源码描述 这是一套同城跑腿小程序,基于FastadminUniapp框架,全开源无加密,可私有化部署,包含用户端、骑手端和运营端(后端),支持帮取/帮送模式,支持一键接单/抢单,主…...
基于SpringBoot的药房药品销售管理系统
作者:计算机学姐 开发技术:SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等,“文末源码”。 专栏推荐:前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏:…...
机器学习中的学习率及其衰减方法全面解析
摘要: 本文深入解析机器学习中的学习率及其衰减方法,涵盖学习率的作用、常用衰减参数及七种主流衰减策略(分段常数、指数、自然指数、多项式、余弦、线性余弦、噪声线性余弦)。通过公式推导与图示对比,揭示不同衰减方式…...
硬件性能与能效比竞赛:解码 PC 硬件的 “速度与激情”
引言:当性能遇见能效,一场永不停歇的算力革命 在数字内容爆炸式增长的时代,无论是 4K/8K 游戏的极致画质追求,还是 AI 大模型的本地化部署需求,亦或是内容创作者对实时渲染的效率渴求,都在推动 PC 硬件走向…...
大模型在终末期肾脏病风险预测与临床方案制定中的应用研究
目录 一、引言 1.1 研究背景与意义 1.2 研究目的与创新点 1.3 研究方法与数据来源 二、终末期肾脏病概述 2.1 定义与诊断标准 2.2 发病机制与影响因素 2.3 现状与危害 三、大模型技术原理及应用现状 3.1 大模型基本原理 3.2 在医疗领域应用案例 3.3 在终末期肾脏病…...
【C++11】智能指针
📝前言: 这篇文章我们来讲讲C11——智能指针: 🎬个人简介:努力学习ing 📋个人专栏:C学习笔记 🎀CSDN主页 愚润求学 🌄其他专栏:C语言入门基础,pyt…...
华为云Astro轻应用利用自定义连接器调用第三方接口实际操作
样图 说明 华为云Astro轻应用通过自定义连接器调用第三方接口具有多方面的作用,主要体现在以下几点: 扩展功能与集成能力 调用第三方服务:通过配置自定义连接器,Astro轻应用可以调用第三方提供的Rest协议接口,实现第三方提供的业务功能,扩展应用的能力。 集成外部系统:…...
【中间件】brpc_基础_butex.h
butex.h 学习笔记 源码 1 概述 butex.h 提供了一种用户态同步原语 butex(类似 Linux 的 futex),专为 bthread 设计,用于高效协调线程的阻塞与唤醒。其核心是通过原子操作结合等待队列管理,减少内核态切换开销&#…...
数字智慧方案5876丨智慧交通枢纽智能化系统建设方案(56页PPT)(文末有下载方式)
篇幅所限,本文只提供部分资料内容,完整资料请看下面链接 https://download.csdn.net/download/2301_78256053/89575493 资料解读:智慧交通枢纽智能化系统建设方案 详细资料请看本解读文章的最后内容。 随着城市化进程的加速,交…...
深度学习笔记40_中文文本分类-Pytorch实现
🍨 本文为🔗365天深度学习训练营 中的学习记录博客🍖 原作者:K同学啊 | 接辅导、项目定制 一、我的环境 1.语言环境:Python 3.8 2.编译器:Pycharm 3.深度学习环境: torch1.12.1cu113torchvision…...
python设置word字体的方法
在Python中,可以使用python-docx库来设置Word文档的字体样式,以下为具体方法和示例代码: 一、设置段落中字体样式 使用python-docx库时,Word文档中的文本通常被组织成段落(Paragraph对象),而一…...
golang常用库之-标准库text/template
文章目录 golang常用库之-标准库text/template背景什么是text/templatetext/template库的使用 golang常用库之-标准库text/template 背景 在许多编程场景中,我们经常需要把数据按照某种格式进行输出,比如生成HTML页面,或者生成配置文件。这…...
【JAVA】如何快速阅读一个基于maven构建的springboot项目
一、摘要 在JAVA项目开发过程中,现在比较流行的是springboot机构,特别是在后端开发的项目中,springboot应用的非常普遍。springboot很好将大型的、复杂的项目进行分解,以模块或者服务的表现形式组成项目。那么当我们接手一个陌生的…...
Fedora升级Google Chrome出现GPG check FAILED问题解决办法
https://dl.google.com/linux/linux_signing_key.pub 的 GPG 公钥(0x7FAC5991)已安装 https://dl.google.com/linux/linux_signing_key.pub 的 GPG 公钥(0xD38B4796)已安装 仓库 "google-chrome" 的 GPG 公钥已安装,但是不适用于此软件包。 请检查此仓库的…...
深入解析MapReduce:大数据处理的经典范式
引言 在大数据时代,如何高效处理海量数据成为技术核心挑战之一。Hadoop生态中的MapReduce框架应运而生,以其“分而治之”的思想解决了大规模数据的并行计算问题。本文将从原理、核心组件到实战案例,带你全面理解这一经典计算模型。 一、MapR…...
JVM性能调优的基础知识 | JVM内部优化与运行时优化
目录 JVM内部的优化逻辑 JVM的执行引擎 解释执行器 即时编译器 JVM采用哪种方式? 即时编译器类型 JVM的分层编译5大级别: 分层编译级别: 热点代码: 如何找到热点代码? java两大计数器: OSR 编译…...
云计算-容器云-部署jumpserver 版本2
应用部署:堡垒机部署 # 使用提供的软件包配置Yum源,通过地址将jumpserver.tar.gz软件包下载至Jumpserver节点的/root目录下 [rootjumpserver ~]# tar -zxvf jumpserver.tar.gz -C /opt/ [rootjumpserver ~]# cp /opt/local.repo /etc/yum.repos.d/ [roo…...
MSP430G2553驱动0.96英寸OLED(硬件iic)
1.前言 最近需要用MSP430单片机做一个大作业,需要用到OLED模块,在这里记录一下 本篇文章主要讲解MSP430硬件iic的配置和OLED函数的调用,不会详细讲解OLED显示原理(其实就是江科大的OLED模块如何移植到msp430上).OLED显示原理以及底层函数讲解请参考其他…...
同质化的旅游内核
湘西凤凰古城、北京非常有文艺氛围的方家胡同都在被改造翻新为现代的其他城市范式式的样式。 什么意思呢?很多古城的老房子,从外面看,很古老、很漂亮,但是进去以后,完全不是那么回事,整座房子已经被完全掏…...
2025年五一数学建模A题【支路车流量推测】原创论文讲解(含完整python代码)
大家好呀,从发布赛题一直到现在,总算完成了2025年五一数学建模A题【支路车流量推测】完整的成品论文。 本论文可以保证原创,保证高质量。绝不是随便引用一大堆模型和代码复制粘贴进来完全没有应用糊弄人的垃圾半成品论文。 A题论文共104页&a…...
文章六:《循环神经网络(RNN)与自然语言处理》
文章6:循环神经网络(RNN)与自然语言处理——让AI学会"说人话" 引言:你的手机为什么能秒懂你? 当你说"我想看科幻片"时,AI助手能立刻推荐《星际穿越》,这背后是RNN在"…...
Redis总结及设置营业状态案例
Redis简介: rRedis服务开启与停止: 服务开启: 在Redis配置文件中输入cmd进入命令行输入redis-server redis-cli.exe -h -p:连接到redis服务 设置密码:在redis.windows.conf中找到requirepass 密码 服务停止: 在服务开启的界面按ctrlc Redis数据类…...
中科大:LLM几何推理数据生成
📖标题:Enhancing the Geometric Problem-Solving Ability of Multimodal LLMs via Symbolic-Neural Integration 🌐来源:arXiv, 2504.12773 🌟摘要 🔸多模态大语言模型(MLLM)的最…...
AimRT从入门到精通 - 04RPC客户端和服务器
一、ROS中的service通信机制 服务通信也是ROS中一种极其常用的通信模式,服务通信是基于请求响应模式的,是一种应答机制。也即:一个节点A向另一个节点B发送请求,B接收处理请求并产生响应结果返回给A。比如如下场景: 机器…...
【Android】Intent
目录 一、什么是Intent 二、显式Intent 三、隐式Intent 四、复杂数据传递 五、跨应用权限管理 六、常见问题 一、什么是Intent 1. 跨组件通信桥梁 实现组件间通信(Activity/Service/BroadcastReceiver)封装操作指令与数据传输逻辑 目标组件启动…...
从0开始建立Github个人博客(hugoPaperMod)
从0开始建立Github个人博客(hugo&PaperMod) github提供给每个用户一个网址,用户可以建立自己的静态网站。 一、Hugo hugo是一个快速搭建网站的工具,由go语言编写。 1.安装hugo 到hugo的github标签页Tags gohugoio/hugo选择一个版本,…...
Python集合全解析:从基础到高阶应用实战
一、集合核心特性与创建方法 1.1 集合的本质特征 Python集合(Set)是一种无序且元素唯一的容器类型,基于哈希表实现,具有以下核心特性: 唯一性:自动过滤重复元素无序性ÿ…...
Matlab自学笔记
一、我下载的是Matlab R2016a软件,打开界面如下: 二、如何调整字体大小,路径为:“主页”->“预设”->“字体”。 三、命令行窗口是直接进行交互式的,如下输入“3 5”,回车,就得到结果“…...
Python爬虫实战:获取好大夫在线各专业全国医院排行榜数据并分析,为患者就医做参考
一、引言 在当今医疗资源丰富但分布不均的背景下,患者在选择合适的心血管内科医院时面临诸多困难。好大夫在线提供的医院排行榜数据包含了医院排名、线上服务得分、患者评价得分等重要信息,对患者选择医院具有重要的参考价值。本研究通过爬取该排行榜数据,并进行深入分析,…...
多模态人工智能研究:视觉语言模型的过去、现在与未来
多模态人工智能研究:视觉语言模型的过去、现在与未来 1. 引言:定义多模态图景 多模态人工智能指的是旨在处理和整合来自多种数据类型或“模态”信息的人工智能系统,这些模态包括文本、图像、音频和视频等。与通常侧重于单一模态(…...
DeepSeek+Excel:解锁办公效率新高度
目录 一、引言:Excel 遇上 DeepSeek二、认识 DeepSeek:大模型中的得力助手2.1 DeepSeek 的技术架构与原理2.2 DeepSeek 在办公场景中的独特优势 三、DeepSeek 与 Excel 结合的准备工作3.1 获取 DeepSeek API Key3.2 配置 Excel 环境 四、DeepSeekExcel 实…...
3033. 修改矩阵
题目来源: leetcode题目:3033. 修改矩阵 - 力扣(LeetCode) 解题思路: 获取每列的最大值后将-1替换即可。 解题代码: #python3 class Solution:def getMaxRow(matrix:List[List[int]])->List[int]:r…...
Android面试总结之jet pack模块化组件篇
一、ViewModel 深入问题 1. ViewModel 如何实现跨 Fragment 共享数据?其作用域是基于 Activity 还是 Fragment? 问题解析: ViewModel 的作用域由 ViewModelStoreOwner 决定。当 Activity 和其内部 Fragment 共享同一个 ViewModelStoreOwner…...
【无需docker】mac本地部署dify
环境安装准备 #安装 postgresql13 brew install postgresql13 #使用zsh的在全局添加postgresql命令集 echo export PATH"/usr/local/opt/postgresql13/bin:$PATH" >> ~/.zshrc # 使得zsh的配置修改生效 source ~/.zshrc # 启动postgresql brew services star…...
清洗数据集
将label在图片上画出来 按照第一行的属性分类 import os import cv2 import multiprocessing as mp from tqdm import tqdm# ---------- 路径配置 ---------- # IMAGE_DIR = r"C:\Users\31919\Desktop\datasets\13k_100drive_raw_with_hand\images\test" LABEL_DIR =…...
支持向量机(SVM)详解
引言 支持向量机(Support Vector Machine, SVM)是一种强大的监督学习算法,主要用于分类和回归任务。其核心思想是找到一个最优的决策边界(超平面),最大化不同类别之间的间隔(Margin)…...
MIT XV6 - 1.2 Lab: Xv6 and Unix utilities - pingpong
接上文 MIT XV6 - 1.1 Lab: Xv6 and Unix utilities - user/_sleep 是什么?做什么? pingpong 不务正业了那么久(然而并没有,虽然还在探索sleep,但是教材我已经看完了前三章了),让我们赶紧继续下去 在进行本实验之前请务…...
“淘宝闪购”提前4天全量,意味着什么?
4月30日推出,首日上线50个城市,既定5月6日推广至全国的“淘宝闪购”,突然在5月2日早上官宣,提前4天面向全国消费者全量开放。 这一系列节奏,剑指一个字“快”! 是业务发展远超预期的“快”。 4月30日&am…...
Servlet 解决了什么问题?
Servlet 主要解决了以下几个核心问题: 性能问题 (Performance): CGI 的问题: 传统的 CGI 技术为每个Web 请求都启动一个新的进程。进程的创建和销毁涉及大量的系统资源开销(内存分配、CPU 时间、进程上下文切换等)。在高并发场景下…...