选择排序:简单高效的选择
大家好,今天我们来聊聊选择排序(Selection Sort)算法。这是一个非常简单的排序算法,适合用来学习排序的基本思路和操作。选择排序在许多排序算法中以其直观和易于实现的特点著称,虽然它的效率不如其他高效算法(如快速排序和归并排序),但它仍然是学习和理解排序算法的一个很好的起点。
一、什么是选择排序?
选择排序是一种简单的排序算法,其基本思想是每次从未排序的部分中选出最小的元素,将它与未排序部分的第一个元素交换位置。这样,每一轮选择都会将一个最小元素放到数组的前面,直到整个数组排序完成。
选择排序的步骤:
- 从数组的第一个元素开始,假设当前元素为最小值。
- 从剩余的未排序部分中,找到最小的元素。
- 如果找到的最小元素小于当前元素,交换它们的位置。
- 将未排序部分的最小元素交换到当前元素的位置。
- 继续对剩余部分进行选择排序,直到整个数组有序。
二、选择排序的工作原理
假设我们有一个数组 [64, 34, 25, 12, 22, 11, 90],我们来演示一下选择排序的过程:
-
第一轮选择:
- 假设
64是最小的元素,遍历数组的剩余部分,找到最小值11,与64交换,得到[11, 34, 25, 12, 22, 64, 90]。
- 假设
-
第二轮选择:
- 假设
34是最小的元素,遍历剩余部分,找到最小值12,与34交换,得到[11, 12, 25, 34, 22, 64, 90]。
- 假设
-
第三轮选择:
- 假设
25是最小的元素,遍历剩余部分,找到最小值22,与25交换,得到[11, 12, 22, 34, 25, 64, 90]。
- 假设
-
第四轮选择:
- 假设
34是最小的元素,遍历剩余部分,找到最小值25,与34交换,得到[11, 12, 22, 25, 34, 64, 90]。
- 假设
-
第五轮选择:
- 假设
34是最小的元素,遍历剩余部分,找到最小值34,不需要交换,得到[11, 12, 22, 25, 34, 64, 90]。
- 假设
-
第六轮选择:
- 假设
64是最小的元素,遍历剩余部分,找到最小值64,不需要交换,得到[11, 12, 22, 25, 34, 64, 90]。
- 假设
-
第七轮选择:
- 最后剩下的元素是
90,它已经排到最后,不需要交换。
- 最后剩下的元素是
最终排序后的数组为 [11, 12, 22, 25, 34, 64, 90]。
三、选择排序的时间复杂度
选择排序的时间复杂度是 O(n²),其中 n 是数组的元素数量。原因如下:
- 每一轮需要遍历未排序部分的所有元素,找到最小的元素并交换它。第一轮遍历需要
n-1次比较,第二轮需要n-2次比较,依此类推,总共需要n(n-1)/2次比较。 - 由于这是一种双重循环结构,因此其时间复杂度为 O(n²)。
最好情况:
- 即使数组已经有序,选择排序仍然会进行完整的遍历,时间复杂度仍然是 O(n²)。
最坏情况:
- 当数组是逆序时,选择排序依然需要进行完整的遍历,时间复杂度为 O(n²)。
四、选择排序的空间复杂度
选择排序是原地排序算法,它只需要常数级的额外空间来存储临时变量(用于交换元素)。因此,它的空间复杂度为 O(1)。
下面是一个用 Java 实现的选择排序代码:
public static void selectsort(int[] arr) {int index = 0;int max = arr[index];for (int j = 0; j < arr.length - 1; j++) {//循环一次选择一个最大值for (int i = 1; i < arr.length - j; i++) {index = arr[i] > max ? i : index;max = arr[index];}//交换最大值与未排序元素的最后一个swap(arr, index, arr.length - j - 1);//注意重置最大值与索引index = 0;max = arr[index];}}public static void swap(int[] arr, int a, int b) {int temp = arr[a];arr[a] = arr[b];arr[b] = temp;}
输入数组 {64, 34, 25, 12, 22, 11, 90},程序的输出是:
11 12 22 25 34 64 90
相关文章:
选择排序:简单高效的选择
大家好,今天我们来聊聊选择排序(Selection Sort)算法。这是一个非常简单的排序算法,适合用来学习排序的基本思路和操作。选择排序在许多排序算法中以其直观和易于实现的特点著称,虽然它的效率不如其他高效算法…...
考研/保研复试英语问答题库(华工建院)
华南理工大学建筑学院保研/考研 英语复试题库,由华工保研er和学硕笔试第一同学一起整理,覆盖面广,助力考研/保研上岸!需要👇载可到文章末尾见小🍠。 以下是主要内容: Part0 复试英语的方法论 Pa…...
ARM Cortex-M处理器中的MSP和PSP
在ARM Cortex-M系列处理器中,MSP(主堆栈指针)和PSP(进程堆栈指针)是两种不同的堆栈指针,主要用于实现堆栈隔离和提升系统可靠性。以下是它们的核心区别和应用场景: 1. 基本定义 MSP(…...
《Keras 3 使用 NeRF 进行 3D 体积渲染》:此文为AI自动翻译
《Keras 3 使用 NeRF 进行 3D 体积渲染》 作者: Aritra Roy Gosthipaty, Ritwik Raha 创建日期: 2021/08/09 最后修改时间: 2023/11/13 描述: 体积渲染的最小实现,如 NeRF 中所示。 (i) 此示例使用 Keras 3 在 Colab 中查看 GitHub 源 介绍 在此示例中,我们展示了…...
Pytorch实现之浑浊水下图像增强
简介 简介:这也是一篇非常适合GAN小白们上手的架构文章!提出了一种基于GAN的水下图像增强网络。这种网络与其他架构类似,生成器是卷积+激活函数+归一化+残差结构的组成,鉴别器是卷积+激活函数+归一化以及全连接层。损失函数是常用的均方误差、感知损失和对抗损失三部分。 …...
【redis】数据类型之Bitfields
Redis的Bitfields(位域)与Bitmaps一样,在Redis中并不是一种独立的数据类型,而是一种基于字符串的数据结构,用于处理位级别的操作。允许用户将一个Redis字符串视作由一系列二进制位组成的数组,并对这些位进行…...
Python入门 — 类
面向对象编程中,编写表示现实世界中的事物和情景的类(class),并基于这些类来创建对象(object)。根据类来创建对象称为实例化,这样就可以使用类的实例(instance) 一、创建…...
R-INLA实现绿地与狐狸寄生虫数据空间建模:含BYM、SPDE模型及PC先验应用可视化...
全文链接:https://tecdat.cn/?p40720 本论文旨在为对空间建模感兴趣的研究人员客户提供使用R-INLA进行空间数据建模的基础教程。通过对区域数据和地统计(标记点)数据的分析,介绍了如何拟合简单模型、构建和运行更复杂的空间模型&…...
Linux云计算SRE-第十五周
1.总结Dockerfile的指令和Docker的网络模式 一、Dockerfile 核心指令详解 1、基础构建指令 指令 功能描述 关键特性 FROM 指定基础镜像(必须为首条指令) - 支持多阶段构建:FROM node AS builder - scratch 表示空镜像 RUN 在镜像构建…...
2014年下半年试题一:论软件需求管理
论文库链接:系统架构设计师论文 论文题目 软件需求管理是一个对系统需求变更了解和控制的过程。需求管理过程与需求开发过程相互关联,初始需求导出的同时就要形成需求管理规划,一旦启动了软件开发过程需求管理活动就紧密相伴。 需求管理过程中…...
podman加速器配置,harbor镜像仓库部署
Docker加速器 registries加速器 [rootlocalhost ~]# cat /etc/redhat-release CentOS Stream release 8 [rootlocalhost ~]# cd /etc/containers/ [rootlocalhost containers]# ls certs.d policy.json registries.conf.d storage.conf oci registries.conf re…...
信息学奥赛一本通 1522:网络 | OpenJudge 百练 1144:Network
【题目链接】 ybt 1522:网络 OpenJudge 百练 1144:Network 【题目考点】 1. 图论:割点 【解题思路】 每个交换机是一个顶点,如果两地点之间有电话线连接,那么两顶点之间有一条无向边,该图是无向图。 初始时任何地…...
本地部署DeepSeek的硬件配置建议
本地部署DeepSeek的硬件配置需求因模型参数规模和部署工具不同而有所差异,以下是综合多个来源的详细要求: 1. 基础配置(适用于7B参数模型) 内存:最低8GB,推荐16GB及以上;若使用Ollama工具&…...
Redis面试题----Redis 的持久化机制是什么?各自的优缺点?
Redis 提供了两种主要的持久化机制,分别是 RDB(Redis Database)和 AOF(Append Only File),下面将详细介绍它们的原理、优缺点。 RDB(Redis Database) 原理 RDB 持久化是将 Redis 在某个时间点上的数据集快照以二进制文件的形式保存到磁盘上。可以通过手动执行 SAVE …...
C#实现本地AI聊天功能(Deepseek R1及其他模型)。
前言 1、C#实现本地AI聊天功能 WPFOllamaSharpe实现本地聊天功能,可以选择使用Deepseek 及其他模型。 2、此程序默认你已经安装好了Ollama。 在运行前需要线安装好Ollama,如何安装请自行搜索 Ollama下载地址: https://ollama.org.cn Ollama模型下载地址…...
Metal 学习笔记四:顶点函数
到目前为止,您已经完成了 3D 模型和图形管道。现在,是时候看看 Metal 中两个可编程阶段中的第一个阶段,即顶点阶段,更具体地说,是顶点函数。 着色器函数 定义着色器函数时,可以为其指定一个属性。您将在本…...
C# string转unicode字符
在 C# 中,将字符串转换为 Unicode 字符(即每个字符的 Unicode 码点)可以通过遍历字符串中的每个字符并获取其 Unicode 值来实现。Unicode 值是一个整数,表示字符在 Unicode 标准中的唯一编号。 以下是实现方法: 1. 获…...
HITCON2017SSRFME-学习复盘
代码审计 192.168.122.15 <?phpif (isset($_SERVER[HTTP_X_FORWARDED_FOR])) {$http_x_headers explode(,, $_SERVER[HTTP_X_FORWARDED_FOR]);//用逗号分割多个IP$_SERVER[REMOTE_ADDR] $http_x_headers[0];}echo $_SERVER["REMOTE_ADDR"];//给第一个IP发送请…...
【Http和Https区别】
概念: 一、Http协议 HTTP(超文本传输协议)是一种用于传输超媒体文档(如HTML)的应用层协议,主要用于Web浏览器和服务器之间的通信。http也是客户端和服务器之间请求与响应的标准协议,客户端通常…...
2025数学建模竞赛汇总,错过再等一年
01、2025第十届数维杯大学生数学建模挑战赛(小国赛) 竞赛介绍:数学建模行业内仅次于国赛和美赛的的第三赛事,被多所高校认定为国家级二类竞赛。赛题类型是国内唯一和高教社杯国赛题型风格完全一致的全国性数学建模竞赛࿰…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
push [特殊字符] present
push 🆚 present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中,push 和 present 是两种不同的视图控制器切换方式,它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...
Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...
uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)
UniApp 集成腾讯云 IM 富媒体消息全攻略(地理位置/文件) 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型,核心实现方式: 标准消息类型:直接使用 SDK 内置类型(文件、图片等)自…...
6.9-QT模拟计算器
源码: 头文件: widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QMouseEvent>QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic:Widget(QWidget *parent nullptr);…...
边缘计算网关提升水产养殖尾水处理的远程运维效率
一、项目背景 随着水产养殖行业的快速发展,养殖尾水的处理成为了一个亟待解决的环保问题。传统的尾水处理方式不仅效率低下,而且难以实现精准监控和管理。为了提升尾水处理的效果和效率,同时降低人力成本,某大型水产养殖企业决定…...
Java多线程实现之Runnable接口深度解析
Java多线程实现之Runnable接口深度解析 一、Runnable接口概述1.1 接口定义1.2 与Thread类的关系1.3 使用Runnable接口的优势 二、Runnable接口的基本实现方式2.1 传统方式实现Runnable接口2.2 使用匿名内部类实现Runnable接口2.3 使用Lambda表达式实现Runnable接口 三、Runnabl…...
