排序算法之选择排序

embedded/2025/1/16 0:56:11/

目录

  • 一、简介
  • 二、代码实现
  • 三、应用场景


一、简介

算法平均时间复杂度最好时间复杂度最坏时间复杂度空间复杂度排序方式稳定性
选择排序O(n^2 )O(n^2)O(n^2)O(1)In-place不稳定

稳定:如果A原本在B前面,而A=B,排序之后A仍然在B的前面;
不稳定:如果A原本在B的前面,而A=B,排序之后A可能会出现在B的后面;
时间复杂度: 描述一个算法执行所耗费的时间;
空间复杂度:描述一个算法执行所需内存的大小;
n:数据规模;
k:“桶”的个数;
In-place:占用常数内存,不占用额外内存;
Out-place:占用额外内存。

在这里插入图片描述

算法步驟:

首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置;
再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾;
重复第2步,直到所有元素均排序完毕。


二、代码实现

java">public class SelectionSort {public static void selectionSort(int[] arr) {int len = arr.length;for (int i = 0; i < len - 1; i++) {int minVal = i;for (int j = i + 1; j < len; j++) {if (arr[minVal] > arr[j]) {minVal = j;}}if (minVal != i) {int tmp = arr[i];arr[i] = arr[minVal];arr[minVal] = tmp;}}}public static void selectionSort2(int[] arr) {int len = arr.length;for (int i = 0; i < len - 1; i++) {int maxVal = i;for (int j = i + 1; j < len; j++) {if (arr[maxVal] < arr[j]) {maxVal = j;}}if (maxVal != i) {int tmp = arr[i];arr[i] = arr[maxVal];arr[maxVal] = tmp;}}}public static void main(String[] args) {int[] arr = {12, 11, 15, 50, 7, 65, 3, 99};System.out.println("---排序前:  " + Arrays.toString(arr));selectionSort(arr);System.out.println("选择排序从小到大:  " + Arrays.toString(arr));selectionSort2(arr);System.out.println("选择排序从大到小:  " + Arrays.toString(arr));}}

在这里插入图片描述

三、应用场景

和冒泡排序一致,相比其它算法>排序算法,这也是一个相对较高的时间复杂度,一般情况不推荐使用。
但是我们还是要掌握冒泡排序的思想及实现,这对于我们的算法思维是有很大帮助的

参考链接:
十大经典算法>排序算法(Java实现)


http://www.ppmy.cn/embedded/2168.html

相关文章

36. UE5 RPG在激活技能时使用蒙太奇动画

在上一篇文章里面&#xff0c;我们实现了一个简单的火球术&#xff0c;创建了火球术的火球&#xff0c;以及能发射它的技能。很简陋&#xff0c;在技能触发的时候&#xff0c;直接在武器的位置生成火球发射出去。在一篇文章里&#xff0c;我们要实现使用技能时&#xff0c;角色…

Spring Boot 经典面试题(八)

1.SpringBoot微服务中如何实现 session 共享 在Spring Boot微服务中实现session共享可以通过不同的方式&#xff0c;取决于你的微服务架构和需求。下面列出了一些常见的方法&#xff1a; 使用Spring Session和Redis&#xff1a; 配置Spring Session来将session数据存储在Redis…

4.Godot图片素材的获取和编辑

游戏开发中经常遇到图片素材的需求 1. 图片素材的准备 术语&#xff1a;Sprite 精灵&#xff0c;游戏开发中指一张图片来源不明的图片&#xff0c;切勿在商业用途使用&#xff0c;以免引起版权风险。 1. 在学习阶段&#xff0c;可以百度或者从一些资源网站获取&#xff0c;这…

计算机视觉——DiffYOLO 改进YOLO与扩散模型的抗噪声目标检测

概述 物体检测技术在图像处理和计算机视觉中发挥着重要作用。其中&#xff0c;YOLO 系列等型号因其高性能和高效率而备受关注。然而&#xff0c;在现实生活中&#xff0c;并非所有数据都是高质量的。在低质量数据集中&#xff0c;更难准确检测物体。为了解决这个问题&#xff…

LeetCode-2923. 找到冠军 I【数组 矩阵】

LeetCode-2923. 找到冠军 I【数组 矩阵】 题目描述&#xff1a;解题思路一&#xff1a;找到没有1存在的列即可。解题思路二&#xff1a;找到和等于n-1的行。解题思路三&#xff1a;打擂台【时间复杂度&#xff1a;O(n)】 题目描述&#xff1a; 一场比赛中共有 n 支队伍&#x…

MS7336MA高清 HD/全高清 FHD 可选择视频运放与视频同轴线控解码

产品简述 MS7336MA 是一颗集成单通道视频放大器与视频同轴线控解 码为一体的芯片&#xff0c;它内部集成 6dB 增益轨到轨输出驱动器以及 10 阶滤波器&#xff0c;允许同一个输入信号在 -3dB 带宽 35MHz 和 55MHz 之间进行选择控制。视频同轴线控解码内部集成一颗高…

【我的代码生成器】React的FrmUser类源码

FrmUser 类的源码中&#xff1a;FrmUser btnSaveClick 等命名方式都是参考VB.Net的写法。 import React, { forwardRef, useImperativeHandle, useState, useEffect, } from "react"; import { makeStyles, TextField, Grid, Paper, Button, ButtonGroup, } from &q…

黑洞路由、 DDoS 攻击 、 环路

黑洞路由 DDoS 攻击 DDoS 攻击是一种针对服务器、服务或网络的恶意行为。DDoS 攻击通过向目标发送大量流量&#xff0c;使其不堪重负&#xff0c;导致资源和带宽被耗尽。因此&#xff0c;目标可能会变慢或崩溃&#xff0c;无法正常处理合法的流量。DDoS 攻击通常是由僵尸网络…