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

java算法:选择排序

文章标题

  • 概述与基本实现
  • 优缺点
  • 尝试优化

概述与基本实现

选择排序(Selection Sort)是一种简单直观的排序算法。它的基本思想是每次从待排序的元素中选择最小(或最大)的元素,放置在已排序的部分的末尾,直到所有元素都排序完成。

实现步骤:

  • 遍历数组,将当前位置作为最小值的索引(假设为minIndex)。
  • 在未排序部分中遍历数组,从当前位置开始,找到最小值的索引。
  • 将最小值与当前位置的元素交换位置。这样,最小值将会被放置在已排序部分的末尾。
  • 重复步骤2和3,直到整个数组排序完成。
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;}}// 将最小值与当前位置的元素交换位置int temp = arr[minIndex];arr[minIndex] = arr[i];arr[i] = temp;}}public static void main(String[] args) {int[] arr = {64, 25, 12, 22, 11};System.out.println("原始数组: " + Arrays.toString(arr));selectionSort(arr);System.out.println("排序后数组: " + Arrays.toString(arr));}
}

通过选择排序算法,数组按升序进行了排序。在每次循环中,选择排序会找到未排序部分的最小值,并将其放置在已排序部分的末尾,直到整个数组排序完成。选择排序的时间复杂度为O(n^2),其中n是数组的大小。

优缺点

优点:

  • 简单直观:选择排序算法的实现相对简单,容易理解和实现。
  • 不占用额外空间:选择排序算法是在原地进行排序的,不需要额外的辅助空间。
  • 稳定性:选择排序是一种稳定的排序算法,不会改变相等元素的相对顺序。

缺点:

  • 时间复杂度:选择排序的时间复杂度为O(n^2),其中n是数组的大小。在最坏情况下,无论输入数据的顺序如何,都需要进行n*(n-1)/2次比较和n次交换操作。
  • 不适用于大规模数据:由于选择排序的时间复杂度较高,它在处理大规模数据时效率较低,不如其他高效的排序算法(如快速排序、归并排序等)。
  • 不稳定的选择性:尽管选择排序是一种稳定的排序算法,但在选择最小值的过程中,交换操作可能会打破相等元素的相对顺序,导致不稳定性。

选择排序算法在简单性和稳定性方面具有一些优点,但在时间复杂度和适用性上存在一些缺点。对于小规模的数据或者对稳定性要求较高的场景,选择排序可能是一个合适的选择。然而,对于大规模数据或对性能有较高要求的情况,其他更高效的排序算法通常更合适。

尝试优化

选择排序算法在简单性和稳定性方面具有一些优点,但在时间复杂度和适用性上存在一些缺点。对于小规模的数据或者对稳定性要求较高的场景,选择排序可能是一个合适的选择。然而,对于大规模数据或对性能有较高要求的情况,其他更高效的排序算法通常更合适。

优化选择排序的方法:

  • 最小值和最大值同时查找:传统的选择排序算法会先找到最小值的索引,然后进行交换。但实际上,在同一次遍历中,可以同时找到最小值和最大值的索引,然后进行两个位置的交换。这样可以减少一半的比较次数。
  • 减少交换次数:传统的选择排序算法在找到最小值或最大值后会立即进行交换。但可以优化为先记录最小值(或最大值)的索引,然后在一次遍历结束后再进行交换。这样可以减少交换的次数。

示例代码:

public class SelectionSort {public static void selectionSort(int[] arr) {int n = arr.length;for (int i = 0; i < n - 1; i++) {int minIndex = i;int maxIndex = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;} else if (arr[j] > arr[maxIndex]) {maxIndex = j;}}// 将最小值交换到已排序部分的开头if (minIndex != i) {int temp = arr[minIndex];arr[minIndex] = arr[i];arr[i] = temp;}// 如果最大值的索引发生了交换,重新调整最大值的索引if (maxIndex == i) {maxIndex = minIndex;}// 将最大值交换到已排序部分的末尾if (maxIndex != n - 1) {int temp = arr[maxIndex];arr[maxIndex] = arr[n - 1];arr[n - 1] = temp;}n--; // 已排序部分增加一个元素,未排序部分减少一个元素}}public static void main(String[] args) {int[] arr = {64, 25, 12, 22, 11};System.out.println("原始数组: " + Arrays.toString(arr));selectionSort(arr);System.out.println("排序后数组: " + Arrays.toString(arr));}
}

通过同时查找最小值和最大值的索引,并在一次遍历结束后进行交换,可以减少比较和交换的次数。这样的优化可以稍微提高选择排序的性能。

需要注意的是,尽管选择排序经过优化,但其时间复杂度仍然是O(n^2),并不适用于大规模数据。对于更高效的排序算法,如快速排序、归并排序等,可以考虑使用它们来取代选择排序。

相关文章:

java算法:选择排序

文章标题 概述与基本实现优缺点尝试优化 概述与基本实现 选择排序&#xff08;Selection Sort&#xff09;是一种简单直观的排序算法。它的基本思想是每次从待排序的元素中选择最小&#xff08;或最大&#xff09;的元素&#xff0c;放置在已排序的部分的末尾&#xff0c;直到…...

helm升级部署时出现升级挂起状态处理

问题 在使用helm 升级命令时&#xff0c;升级命令如下&#xff1a; helm upgrade -i -f ./values-prod.yaml myapp ./ -n myns --create-namespace中途因为网络原因&#xff0c;再次运行上面升级命令时出现&#xff0c;如下错误&#xff1a; Error: UPGRADE FAILED: another …...

16、架构-可观测性-事件日志详细解析

事件日志 事件日志是记录系统运行期间发生的离散事件的关键工具。它们在系统的可观测性中起着至关重要的作用&#xff0c;帮助开发者和运维人员追踪、分析和解决系统问题。以下是对事件日志处理各个方面的详细解析&#xff0c;并结合具体的数据案例和技术支撑。 输出 日志输出…...

Java数据结构与算法(买卖股票的最佳时机二贪心算法)

前言 买卖股票最佳时机二&#xff0c;此时不限次数的买卖的要求获得的利益最大化。暴力算法依旧可行&#xff0c;可以参考之前的练习。 . - 力扣&#xff08;LeetCode&#xff09; 贪心算法原理参考:Java数据结构与算法(盛水的容器贪心算法)-CSDN博客 实现原理 1.定义最大…...

t265 坑

Streaming T265 video over USB 2.1 is unreliable, please use USB 3 or only stream poses 试着用windows 打开也是默认是USB2打开&#xff0c; 英伟达orin nx jetpack 也一样 不知道为啥。并且一旦打开飞控 microxrceagent &#xff0c; t265 的位置就飞。 配置ros2 的lau…...

【LLM之RAG】Adaptive-RAG论文阅读笔记

研究背景 文章介绍了大型语言模型&#xff08;LLMs&#xff09;在处理各种复杂查询时的挑战&#xff0c;特别是在不同复杂性的查询处理上可能导致不必要的计算开销或处理不足的问题。为了解决这一问题&#xff0c;文章提出了一种自适应的查询处理框架&#xff0c;动态选择最合…...

介绍react

什么是React React是一个用于构建用户界面的JavaScript库。 传统构建页面的方式 <script>document.getElementById(app).addEventListener(click, () > {console.log()});const div docuemnt.createElement(div)// ... </script> 早期&#xff0c;用JavaSc…...

网络爬虫概述

自学python如何成为大佬(目录):https://blog.csdn.net/weixin_67859959/article/details/139049996?spm1001.2014.3001.5501 网络爬虫&#xff08;又被称为网络蜘蛛、网络机器人&#xff0c;在某社区中经常被称为网页追逐者&#xff09;&#xff0c;可以按照指定的规则&#…...

取证工作: SysTools SQL Log Analyzer, 完整的 SQL Server 日志取证分析

天津鸿萌科贸发展有限公司是 Systools 系列软件的授权代理商。 SysTools SQL Log Analyzer 是 Systools 取证工具系列之一&#xff0c;用于调查 SQL Server 事务日志&#xff0c;以对数据库篡改进行取证分析。 什么是 SQL Server 事务日志&#xff1f; 在深入研究 SQL 事务日…...

蓝牙耳机怎么连接电脑?轻松实现无线连接

蓝牙耳机已经成为许多人生活中不可或缺的一部分&#xff0c;不仅可以方便地连接手机&#xff0c;还能轻松连接电脑&#xff0c;让我们在工作和娱乐时享受无线的自由。然而&#xff0c;对于一些用户来说&#xff0c;将蓝牙耳机与电脑连接可能会遇到一些问题。本文将介绍蓝牙耳机…...

4.音视频 AAC SSAASS

目录 AAC 1.什么是ADIF和ADTS&#xff1f; 2.ADTS的数据结构是怎样的&#xff1f; SSA/ASS 1.SSA/ASS的基本结构 AAC AAC(Advanced Audio Coding&#xff0c;高级音频编码)是一种声音数据的文件压缩格式。AAC分为ADIF和ADTS两种文件格式。 1.什么是ADIF和ADTS&#xff…...

每日5题Day24 - LeetCode 116 - 120

每一步向前都是向自己的梦想更近一步&#xff0c;坚持不懈&#xff0c;勇往直前&#xff01; 第一题&#xff1a;116. 填充每个节点的下一个右侧节点指针 - 力扣&#xff08;LeetCode&#xff09; /* // Definition for a Node. class Node {public int val;public Node left;…...

在笔记本电脑上使用 LLMs 的 5 种方法

在网上使用 ChatGPT 很简单&#xff0c;只需有网络连接和好的浏览器即可。但这样做可能会泄露您的隐私和数据。OpenAI 存储了您的提示和其他元数据以重新训练模型。对于一些人来说可能不成问题&#xff0c;但注重隐私的人可能更愿意在本地使用这些模型&#xff0c;不受外部跟踪…...

Linux内存从0到1学习笔记(8.15 MMU/IOMMU/SMMU概览)

一, 什么是MMU? MMU(Memory Management Unit 内存管理单元),即内存管理单元,是计算机硬件中的一个重要组件,主要负责处理中央处理器(CPU)的内存访问请求。 其工作原理如下: 当程序发出内存访问请求,包括读取或写入操作以及逻辑地址(虚拟地址)。然后,MMU根据页表…...

Intellij IDEA中怎么配置Maven?

在IntelliJ IDEA中配置Maven非常简单&#xff0c;以下是详细步骤&#xff1a; 步骤1&#xff1a;安装Maven 首先确保你的计算机上已经安装了Maven。如果没有安装&#xff0c;你可以从Apache Maven官网下载并安装&#xff1a;https://maven.apache.org/download.cgi 步骤2&am…...

操作系统-内存管理

虚拟内存 操作系统会提供⼀种机制&#xff0c;将不同进程的虚拟地址和不同内存的物理地址映射起来。 两个概念&#xff1a; 程序所使⽤的内存地址叫做虚拟内存地址&#xff08;Virtual Memory Address&#xff09;实际存在硬件⾥⾯的空间地址叫物理内存地址&#xff08;Physi…...

C++中的解释器模式

目录 解释器模式&#xff08;Interpreter Pattern&#xff09; 实际应用 算术表达式解释器 布尔表达式解释器 总结 解释器模式&#xff08;Interpreter Pattern&#xff09; 解释器模式是一种行为设计模式&#xff0c;它定义了一种语言的文法表示&#xff0c;并使用解释器…...

用 C 语言实现求补码的运算

缘起 前两天程序中需要求一堆参数的补码&#xff0c;一时犯懒&#xff0c;想从CSDN上搜一个勉强能用的代码借鉴一下&#xff0c;结果几乎没有搜到一个靠谱的&#xff01;这种求补码的操作&#xff0c;用脚趾头想想也应该知道要用C或者C的位运算来实现呀。结果搜到的一些实现方…...

python下载文件

import urllib.request url "http://****/storage/x4MigEhU6BGAuTqjrRfIBky0S2aMmkyGl4UzTqUb.png"#下载地址 path "ddad.png"#保存路径&#xff0c;保存项目路径 urllib.request.urlretrieve(url, path)...

JMU 数科 数据库与数据仓库期末总结(1)

本章根据老师给出的知识点作进一步相对生动一点的解释。 不保证完全正确。 先给出总的知识点&#xff0c;再给出生动解释。 知识点 数据模型通常由三部分组成&#xff1a;数据结构、数据操作和完整性约束。关系模式中主码的取值必须唯一且非空&#xff0c;这是实体完整性的…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

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

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

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

怎么让Comfyui导出的图像不包含工作流信息,

为了数据安全&#xff0c;让Comfyui导出的图像不包含工作流信息&#xff0c;导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo&#xff08;推荐&#xff09;​​ 在 save_images 方法中&#xff0c;​​删除或注释掉所有与 metadata …...

作为测试我们应该关注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;不包…...

LLaMA-Factory 微调 Qwen2-VL 进行人脸情感识别(二)

在上一篇文章中,我们详细介绍了如何使用LLaMA-Factory框架对Qwen2-VL大模型进行微调,以实现人脸情感识别的功能。本篇文章将聚焦于微调完成后,如何调用这个模型进行人脸情感识别的具体代码实现,包括详细的步骤和注释。 模型调用步骤 环境准备:确保安装了必要的Python库。…...