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

选择排序的简单理解

详细描述

选择排序的工作原理是:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾,以此类推,直到全部待排序的数据元素的个数为零。

选择排序详细的执行步骤如下:

  1. 初始状态:无序区为 R[1..n],有序区为空;
  2. 第 i 趟排序 (i=1,2,3…n-1) 开始时,当前有序区和无序区分别为 R[1...i-1] 和 R[i...n]。该趟排序从当前无序区中选出关键字最小的记录 R[k],将它与无序区的第 1 个记录 R 交换,使 R[1...i] 和 R[i+1...n] 分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区;
  3. 经过 n-1 趟,无序序列就有序化了。

算法图解

问题解疑

为什么选择排序是不稳定的?

虽然原理上存在有序区和无序区的区分,但是选择排序算法为了提高空间的使用率,使用的是原地交换方式。

与冒泡排序两两比较交换不同,选择排序算法是最小的元素与固定位置的元素进行交换,当这个固定位置的元素被交换到另一个位置之后,也就有可能导致相等的数字次序变化。

选择排序的时间复杂度是多少?

无论原序列是有序还是无序,选择排序都需要对序列做完整的遍历,即最好情况时间复杂度和最坏情况时间复杂度都是 O(n2);平均时间复杂度是 O(n2)。

代码实现

排序接口

 
package cn.fatedeity.algorithm.sort;
/**
* 排序接口
*/
public interface Sort {
int[] sort(int[] numbers);
}

排序抽象类

 
package cn.fatedeity.algorithm.sort;
/**
* 排序抽象类
*/
public abstract class AbstractSort implements Sort {
protected void swap(int[] numbers, int src, int target) {
int temp = numbers[src];
numbers[src] = numbers[target];
numbers[target] = temp;
}
}

选择排序类

 
package cn.fatedeity.algorithm.sort;
/**
* 选择排序类
*/
public class SelectionSort extends AbstractSort {
@Override
public int[] sort(int[] numbers) {
if (numbers.length <= 1) {
return numbers;
}
for (int i = 0; i < numbers.length - 1; i++) {
for (int j = i + 1; j < numbers.length; j++) {
// 选取到小的值做交换
if (numbers[i] <= numbers[j]) {
continue;
}
this.swap(numbers, i, j);
}
}
return numbers;
}
}

 详细描述

选择排序的工作原理是:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾,以此类推,直到全部待排序的数据元素的个数为零。

选择排序详细的执行步骤如下:

  1. 初始状态:无序区为 R[1..n],有序区为空;
  2. 第 i 趟排序 (i=1,2,3…n-1) 开始时,当前有序区和无序区分别为 R[1...i-1] 和 R[i...n]。该趟排序从当前无序区中选出关键字最小的记录 R[k],将它与无序区的第 1 个记录 R 交换,使 R[1...i] 和 R[i+1...n] 分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区;
  3. 经过 n-1 趟,无序序列就有序化了。

算法图解

问题解疑

为什么选择排序是不稳定的?

虽然原理上存在有序区和无序区的区分,但是选择排序算法为了提高空间的使用率,使用的是原地交换方式。

与冒泡排序两两比较交换不同,选择排序算法是最小的元素与固定位置的元素进行交换,当这个固定位置的元素被交换到另一个位置之后,也就有可能导致相等的数字次序变化。

选择排序的时间复杂度是多少?

无论原序列是有序还是无序,选择排序都需要对序列做完整的遍历,即最好情况时间复杂度和最坏情况时间复杂度都是 O(n2);平均时间复杂度是 O(n2)。

代码实现

排序接口

 
package cn.fatedeity.algorithm.sort;
/**
* 排序接口
*/
public interface Sort {
int[] sort(int[] numbers);
}

排序抽象类

 
package cn.fatedeity.algorithm.sort;
/**
* 排序抽象类
*/
public abstract class AbstractSort implements Sort {
protected void swap(int[] numbers, int src, int target) {
int temp = numbers[src];
numbers[src] = numbers[target];
numbers[target] = temp;
}
}

选择排序类

 
package cn.fatedeity.algorithm.sort;
/**
* 选择排序类
*/
public class SelectionSort extends AbstractSort {
@Override
public int[] sort(int[] numbers) {
if (numbers.length <= 1) {
return numbers;
}
for (int i = 0; i < numbers.length - 1; i++) {
for (int j = i + 1; j < numbers.length; j++) {
// 选取到小的值做交换
if (numbers[i] <= numbers[j]) {
continue;
}
this.swap(numbers, i, j);
}
}
return numbers;
}
}

相关文章:

选择排序的简单理解

详细描述 选择排序的工作原理是&#xff1a;首先在未排序序列中找到最小&#xff08;大&#xff09;元素&#xff0c;存放到排序序列的起始位置&#xff0c;然后再从剩余未排序元素中继续寻找最小&#xff08;大&#xff09;元素&#xff0c;然后放到已排序序列的末尾&#xf…...

使用js封装一个循环链表

直接不说废话&#xff0c;直接上代码&#xff0c;这里继承了单向链表的类LinkList &#xff0c;可以查看之前的文章&#xff0c;点这里 class Node {constructor(element) {this.element element;this.next null;} }class CirularLinkedList extends LinkList {constructor(…...

NumPy 秘籍中文第二版:二、高级索引和数组概念

原文&#xff1a;NumPy Cookbook - Second Edition 协议&#xff1a;CC BY-NC-SA 4.0 译者&#xff1a;飞龙 在本章中&#xff0c;我们将介绍以下秘籍&#xff1a; 安装 SciPy安装 PIL调整图像大小比较视图和副本翻转 Lena花式索引位置列表索引布尔值索引数独的步幅技巧广播数…...

新品-图灵超频工作站GT430M介绍

曾经历史 UltraLAB GTxxxM系列是西安坤隆公司专注于超频高速计算应用的图形工作站。 2008年 获取排名第一、二的中国象棋软件均采用该机型。 2019年 推出采用Intel 超频Xeon&#xff08;28核4.8GHz&#xff09;显著提升电磁仿真频域算法求解、第一个解决8K视频解码与渲染。 今…...

js时间格式化精确到毫秒

/*** 数字前置补零* param value 值* param length 位数* returns {string}*/ export function digit(value, length 2) {if (typeof value "undefined" ||value null ||String(value).length > length) {return value;}return (Array(length).join("0&qu…...

QT样式表详解

本文详细介绍qt的样式表&#xff0c;包含样式表如何使用&#xff0c;常见语句和选择器。 背景说明 样式表用于设置外观&#xff0c;他是设置控件外观的方式之一。其他方式如下&#xff1a; 控件的成员函数&#xff0c;如QWidget::setBackground样式表调色板 优先级依次提高…...

最值得入手的好物有哪些,推荐几款实用的数码好物

随着科技的进步&#xff0c;越来越多的数码产品不断的出现在我们的生活中&#xff0c;这其中也不乏一些实用的数码产品&#xff0c;让我们可以享受更舒适的生活&#xff0c;提高我们的工作效率。下面就给大家分享几款我最近使用过的一些数码产品&#xff0c;它们不仅功能强大而…...

【20230407】NVIDIA显卡算力、Jetson比较

1 基本概念 1.1 算力单位 TOPS&#xff1a;指的是每秒钟可以执行的整数运算次数&#xff0c;它代表着计算机在处理图像、音频等任务时的处理能力。TOPS的单位是万亿次每秒&#xff08;trillion operations per second&#xff09;。一般是指整数运算能力INT8。 TFLOPS&#…...

dsl语法

查询 1.查询所有&#xff08;默认有分页查询&#xff09; #查询所有 GET /hotel/_search {"query": {"match_all": {}} } 2.match查询&#xff08;条件查询&#xff09;-----包含四川和外滩的信息&#xff0c;信息匹配度越高越靠前&#xff0c;两者存在一…...

不让CPU偷懒

文章资料摘自——《程序员的自我修养》 为了防止cpu执行完该程序后需要等待程序员手动加入下一个程序&#xff0c;才可以继续运行&#xff0c;这里大大浪费了cpu的效率&#xff0c;要知道cpu是十分昂贵的。 多道程序 在计算机发展的早期&#xff0c;CPU使用十分不方便&#x…...

动力节点王鹤SpringBoot3笔记——第七章 视图技术Thymeleaf

目录 第七章 视图技术Thymeleaf 前言 7.1 表达式 7.2 if-for 第七章 视图技术Thymeleaf 前言 Thymeleaf 是一个表现层的模板引擎&#xff0c; 一般被使用在 Web 环境中&#xff0c;它可以处理 HTML, XML、 JS 等文档&#xff0c;简单来说&#xff0c;它可以将 JSP 作…...

从比特保存和信息保存看数字资源长期保存

引用IBM以色列海法实验室的观点&#xff0c;数字资源长期保存包含两个层面含义&#xff0c;即比特保存与信息保存。也就是说&#xff0c;要实现数字资源的长期保存&#xff0c;必须同时做到比特保存和信息保存。 一 ​概念 01 比特保存&#xff0c;也叫物理保存&#xff0c;主…...

兰伯特光照模型(Lambert Lighting)和半兰伯特光照模型(Half-Lanbert)

关于漫反射 光打到凹凸不平的平面上&#xff0c;光线会被反射到四面八方&#xff0c;被称为漫反射 关于这种模型&#xff0c;由于光线由于分散&#xff0c;所以进入人眼的光线强度和观察角度没有区别 在A点和B点接收到的光线强度是一样的 在漫反射下&#xff0c;光线强度只和光…...

Python 进阶指南(编程轻松进阶):二、环境配置和命令行

原文&#xff1a;http://inventwithpython.com/beyond/chapter2.html 环境配置是配置你的计算机环境&#xff0c;以便你写代码的过程。这包括安装任何必要的工具&#xff0c;配置它们&#xff0c;以及处理安装过程中的任何问题。没有一键配置这种傻瓜式操作过程&#xff0c;因为…...

求职半年,三月成功拿到阿里offer,分享一波面经...

前言 不论是校招还是社招都避免不了各种⾯试、笔试&#xff0c;如何去准备这些东⻄就显得格外重要。不论是笔试还是⾯试都是有章可循的&#xff0c;我这个“有章可循”说的意思只是说应对技术⾯试是可以提前准备&#xff0c;所谓不打无准备的仗就是这个道理。 以下为大家&…...

餐饮店的运营需要考虑哪些方面

餐饮店的运营需要多方面的考虑和规划&#xff0c;以下是传递宝APP上一些常用的餐饮店运营方法&#xff1a; 1.定位&#xff1a;明确餐饮店的定位和目标客户群体&#xff0c;针对不同的客户需求&#xff0c;提供个性化的服务和产品&#xff0c;比如是附近的上班族&#xff0c;还…...

Multi-modal Alignment using Representation Codebook

Multi-modal Alignment using Representation Codebook 题目Multi-modal Alignment using Representation Codebook译题使用表示代码集的多模态对齐期刊/会议CVPR 摘要&#xff1a;对齐来自不同模态的信号是视觉语言表征学习&#xff08;representation learning&#xff09;的…...

关于vector的emplace_back和push_back的区别

实验代码&#xff1a; class A { public:A(int x) {x x;cout << "construct A" << endl;}A(const A& a) {x a.x;cout << "copy construct A" << endl;}A(const A&& a) {cout << "Move construct A"…...

Vue——表单输入绑定

目录 基本用法​ 文本 多行文本 复选框​ 选择器​ 值绑定​ 复选框 单选按钮 选择器选项 修饰符​ .lazy​ .number​ .trim​ 组件上的 v-model​ 在前端处理表单时&#xff0c;我们常常需要将表单输入框的内容同步给 JavaScript 中相应的变量。手动连接值绑定…...

MySQL性能优化(二)索引

文章目录优化手段准备案例索引的本质索引的数据结构不同存储引擎中索引的实践MyIsam &#xff08;索引没有主次之分、都存放在MYI文件&#xff09;主键索引其他索引InnoDB&#xff08;数据即索引、索引即数据&#xff09;主键索引——聚集索引聚集索引其他索引没有主键的情况&a…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

MinIO Docker 部署:仅开放一个端口

MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...

通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器

拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件&#xff1a; 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...

华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)

题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...