排序算法之选择排序详细解读(附带Java代码解读)

news/2024/9/18 12:44:01/ 标签: 排序算法, 算法

选择排序(Selection Sort)是一种简单且直观的算法>排序算法。它的基本思想是:每一轮从未排序的部分中选出最小(或最大)的元素,放到已排序部分的末尾。通过不断地选择最小(或最大)元素,最终使整个数组有序。

算法思想

  1. 初始化:将数组分为已排序部分和未排序部分。开始时,已排序部分为空,未排序部分是整个数组。
  2. 选择最小元素:在未排序部分中找到最小的元素,并将其与未排序部分的第一个元素交换。这样,最小元素就被放到了已排序部分的末尾。
  3. 重复步骤2:不断重复上述过程,直到未排序部分为空。此时,整个数组已经有序。

过程示例

假设有一个待排序的数组:[64, 25, 12, 22, 11]

初始状态:

数组:[64, 25, 12, 22, 11]

第1轮选择:
  1. 在未排序部分 [64, 25, 12, 22, 11] 中,找到最小的元素 11。
  2. 将 11 和未排序部分的第一个元素 64 交换。
  3. 数组变为:[11, 25, 12, 22, 64],其中 [11] 是已排序部分,[25, 12, 22, 64] 是未排序部分。
第2轮选择:
  1. 在未排序部分 [25, 12, 22, 64] 中,找到最小的元素 12。
  2. 将 12 和未排序部分的第一个元素 25 交换。
  3. 数组变为:[11, 12, 25, 22, 64],其中 [11, 12] 是已排序部分,[25, 22, 64] 是未排序部分。
第3轮选择:
  1. 在未排序部分 [25, 22, 64] 中,找到最小的元素 22。
  2. 将 22 和未排序部分的第一个元素 25 交换。
  3. 数组变为:[11, 12, 22, 25, 64],其中 [11, 12, 22] 是已排序部分,[25, 64] 是未排序部分。
第4轮选择:
  1. 在未排序部分 [25, 64] 中,找到最小的元素 25。
  2. 将 25 和未排序部分的第一个元素 25 交换(自身交换,数组不变)。
  3. 数组变为:[11, 12, 22, 25, 64],其中 [11, 12, 22, 25] 是已排序部分,[64] 是未排序部分。
第5轮选择:
  1. 最后一轮只有一个元素 64,已是最小,不需要交换。
  2. 数组最终变为:[11, 12, 22, 25, 64]。

经过上述5轮选择,数组已经完全有序。

算法复杂度

  • 时间复杂度:

    • 最坏情况: O(n^2)
    • 平均情况: O(n^2)
    • 最佳情况: O(n^2)

    选择排序在最优、最坏、和平均情况下的时间复杂度都是 O(n^2),因为无论数组是否已排序,算法都要遍历整个未排序部分来寻找最小元素。

  • 空间复杂度: O(1) 选择排序是原地算法>排序算法,不需要额外的存储空间,只有一些临时变量用于交换。

优点

  1. 简单直观:选择排序的思想容易理解,实现起来也很简单。
  2. 交换次数较少:相比于冒泡排序,选择排序在数据量较大时,交换次数相对较少。

缺点

  1. 时间复杂度较高:无论数组是否已经部分有序,选择排序都需要进行 n(n-1)/2 次比较,因此时间复杂度较高,效率低。
  2. 不稳定:选择排序是一个不稳定的算法>排序算法,如果两个相同的元素在数组中,他们在排序后可能会出现相对位置的变化。

选择排序的Java实现

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("排序前的数组:");for (int num : arr) {System.out.print(num + " ");}System.out.println();selectionSort(arr);System.out.println("排序后的数组:");for (int num : arr) {System.out.print(num + " ");}}
}

代码说明

  1. selectionSort方法:

    • 外层循环遍历数组,从第一个元素开始。
    • 假设当前位置的元素是最小值,记录它的索引 minIndex
    • 内层循环从当前位置的下一个元素开始,查找更小的元素,如果找到,则更新 minIndex
    • 内层循环结束后,交换 minIndex 对应的元素和当前元素的位置。
  2. main方法:

    • 创建一个待排序的数组 arr
    • 调用 selectionSort 方法对数组进行排序。
    • 输出排序前和排序后的数组。

http://www.ppmy.cn/news/1516487.html

相关文章

MybatisPlus:实现分页效果并解决错误:cant found IPage for args

我们在做开发使用mybatisplus 做分页查询的时候遇到了个问题&#xff1a; 继承 IPage拦截没有作用会默认分页&#xff0c;这个时候报了cant found IPage for args 错误~~~ 我们分析了下&#xff0c;其实这个问题很简单&#xff0c;是因为没有给默认值赋值&#xff0c;因为查询…

申报合肥市各区县高新技术企业认定奖励补助政策

&#xff08;一&#xff09;合肥市 对首次认定为国家高新技术企业给予10万元奖励&#xff0c;并落实国家各项税收优惠支持政策。对符合条件的入库国家科技型中小企业&#xff0c;按符合加计扣除条件的研发费用10%&#xff0c;给予10万元—50万元补贴。 &#xff08;政策来源&…

鸿蒙高级开发者认证题库(2)

20.项目需要为不同的设备形态(如手机、智能手表)提供定制化构建。请说明如何在DevEco studio中设置不同的构建配置&#xff0c;以生成针对不同设备的hap包? A.在工程级别build-profile.ison5定义多个 product&#xff0c;在每个product的config/deviceType中定义不同的设备类…

攻防世界 1000次点击

做题笔记。 下载解压 查壳。 32位ida打开。 查找字符串。 winmain函数写的&#xff0c;程序运行如下&#xff1a; 一开始思路是想着分析找到关键代码然后去od进行调试。 后来&#xff0c;额&#xff0c;不想看代码了。吐了。 尝试去字符串搜索flag样式&#xff0c;确实一发现…

数据结构(6_3_1)——图的广度优先遍历

树和图的广度优先遍历区别 树的广度优先遍历&#xff1a; 图的广度优先遍历&#xff1a; 代码&#xff1a; 注:以下代码只适合连通图 #include <stdio.h> #include <stdbool.h>#define MAX_VERTEX_NUM 100typedef struct ArcNode {int adjvex; // 该边所指向的顶…

链表(含代码)

好久没更新了&#xff0c;今天浅浅更新一下。 今天给大家主要分享一下链表的一些知识。 链表的首先方式主要有两种&#xff0c;一种是结构体加指针&#xff0c;另一种是拿数组模拟链表。 一、结构体加指针&#xff08;每次都要调用new Node&#xff08;&#xff09;函数&…

优化|计算合作博弈的成本分摊

原文&#xff1a; Caprara, A., & Letchford, A. N. (2010). New techniques for cost sharing in combinatorial optimization games. Mathematical programming, 124, 93-118. https://doi.org/10.1007/s10107-010-0357-7. 原文作者&#xff1a; Alberto Caprara, Adam N…

【功能实现】axios实现动态数据

1.安装axios npm i axios 2.axios调取数据 import { onMounted,ref } from "vue"const titleListref([])//获取数据库数据&#xff0c;将数据赋值给titleListconst getArticles async () > {const result await axios.get(http://127.0.0.1:3000/getAccount)t…

嵌入式Linux学习笔记

1.文件操作命令 2.VI编辑器的部分命令 3.Uboot命令设置环境变量 4. uboot 的顶层 Makefile的重点是“make xxx_defconfig”和“make”这两个命令 &#xff0c;分别如下&#xff1a; 5.在串口SecureCRT中利用uboot启动Linux内核的两种方式 6.Linux内核移植到开发板上也可以反…

C#/.NET/.NET Core技术前沿周刊 | 第 2 期(2024年8.19-8.25)

前言 C#/.NET/.NET Core技术前沿周刊&#xff0c;你的每周技术指南针&#xff01;记录、追踪C#/.NET/.NET Core领域、生态的每周最新、最实用、最有价值的技术文章、社区动态、优质项目和学习资源等。让你时刻站在技术前沿&#xff0c;助力技术成长与视野拓宽。 欢迎投稿&…

MFC之word操作

MFC对word操作 背景说明 当对程序的内容进行输出时&#xff0c;比如自定义对象属性描述或者注释&#xff08;详细设计&#xff09;生成文档时&#xff0c;如果采用手动输入会比较麻烦&#xff0c;并且当程序变动时&#xff0c;需要再一次修改对应文档&#xff0c;作为程序员做…

修复 502 Bad Gateway 错误的 6 种方法

通常&#xff0c;我们在使用网站时可能会遇到一系列错误。有些非常常见&#xff0c;例如 404&#xff0c;有些则不太常见&#xff0c;例如 101。这些被称为 HTTP 状态代码。其中&#xff0c;502 错误是某种服务器错误。那么&#xff0c;让我们先了解一下 Bad Gateway 502 的含义…

EazyDraw for Mac 矢量图绘制设计软件

Mac分享吧 文章目录 效果一、下载软件二、开始安装1、双击运行软件&#xff0c;将其从左侧拖入右侧文件夹中&#xff0c;等待安装完毕2、应用程序显示软件图标&#xff0c;表示安装成功 三、运行测试安装完成&#xff01;&#xff01;&#xff01; 效果 一、下载软件 下载软件…

SpringMvc 以配置类的形式代替xml文件

1、配置类 1.1、创建Mvc 项目之后创建 MyWebApplicationInitializer 类 实现接口 WebApplicationInitializer public class MyWebApplicationInitializer implements WebApplicationInitializer {Overridepublic void onStartup(ServletContext servletContext) throws Serv…

通过Spring Boot创建项目

目录 引言 一、创建新项目 二、通过spring boot创建顾客查询的项目 1.实体类: 2.mapper接口 3.service服务层接口 4.service服务层接口实现类 5.mapper映射文件 三、可能遇到的问题 引言 在通过之前ssm框架的学习后&#xff0c;你是否会感觉ssm的配置过多&#xff0c…

Redis 的 主从复制

目录 1 Redis 主从复制介绍 2 Redis主从复制原理 2.1 主从同步过程 3 Redis实现主从复制 3.1 环境配置 3.2 修改各节点的配置文件 3.2.1 MASTER 3.2.2 SLAVE 3.3.3 重启Redis 3.3 查看是否实现了主从复制 3.3.1 MASTER 3.3.2 SLAVE 3.3.3 Redis 常用操作 3.3.4 数据添加查看…

Yolo环境搭建(深度学习基础环境)

需要安装的东西 CUDAcuDnn魔法 一、CUDA安装(Windows10环境) 第一&#xff1a;下载驱动 第二&#xff1a;查看显卡支持的最高CUDA的版本&#xff0c;以便下载对应的CUDA安装包 第三&#xff1a;确定CUDA版本对应的cuDNN版本&#xff0c;这个其实不用太关注&#xff0c;因为…

【解析几何笔记】9. 向量的内积运算

9. 向量的内积运算 定义&#xff1a;有向量 α , β \pmb{\alpha},\pmb{\beta} α,β&#xff0c; α ⋅ β ∣ α ∣ ∣ β ∣ ⋅ cos ⁡ < α , β > \pmb{\alpha}\cdot\pmb{\beta}|\pmb{\alpha}||\pmb{\beta}|\cdot\cos<\pmb{\alpha},\pmb{\beta}> α⋅β∣α…

Qt编写贪吃蛇小游戏完整项目

文章目录 前言一、Qt环境准备二、编写思路三、编写代码1、开始游戏界面代码1.1、绘制界面1.2、界面基本配置 2、选择难度界面代码3、游戏房间界面制作3.1、界面基础配置3.2、提前配置类中的成员变量3.2.1、QRectF 3.3、检测游戏是否结束的方法3.4、蛇移动的实现3.4.1、蛇向上移…

【赵渝强老师】执行MySQL的冷备份与冷恢复

冷备份是指发生在数据库已经正常关闭的情况下进行的备份。由于此时数据库已经关闭&#xff0c;通过冷备份可以将数据库的关键性文件拷贝到另外存储位置。冷备份因为只是拷贝文件&#xff0c;因此备份的速度非常快。在执行恢复时&#xff0c;只需将文件再拷贝回去就可以很容易恢…