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

第 7 章 排序算法(3)(选择排序)

7.6选择排序

7.6.1基本介绍

选择式排序也属于内部排序法,是从欲排序的数据中,按指定的规则选出某一元素,再依规定交换位置后达到排序的目的。

7.6.2选择排序思想:

选择排序(select sorting)也是一种简单的排序方法。它的基本思想是:第一次从arr[0]arr[n-1]中选取最小值,与arr[0]交换,第二次从arr[1]arr[n-1]中选取最小值,与arr[1]交换,第三次从arr[2]arr[n-1]中选取最小值,与arr[2]交换,…,第i次从arr[i-1]arr[n-1]中选取最小值,与arr[i-1]交换,…, 第n-1次从arr[n-2]~arr[n-1]中选取最小值,与arr[n-2]交换,总共通过n-1次,得到一个按排序码从小到大排列的有序序列。

7.6.3选择排序思路分析图:

在这里插入图片描述
选择排序思路讲解
在这里插入图片描述

7.6.4选择排序应用实例:

有一群牛 , 颜值分别是 101, 34, 119, 1 请使用选择排序从低到高进行排序 [101, 34, 119, 1]
在这里插入图片描述
代码实现:

推导过程的代码:

import java.text.SimpleDateFormat;
import java.util.Date;/*** 选择排序*/
public class SelectSort {public static void main(String[] args) {int[] arr = {101, 34, 119, 1};System.out.println("排序前:");System.out.println(Arrays.toString(arr));selectSort(arr);}//选择排序public static void selectSort(int[] arr) {//使用逐步推导的方式来进行 选择排序//第1轮//原始的数组: 101,34,119,1//第一轮排序:  1,34,119,101//算法 先简单 --》做复杂,就是可以把一个复杂的算法,拆分成简单的问题 --》逐步解决//第1轮int minIndex = 0;int min = arr[0];for (int j = 0 + 1; j < arr.length; j++) {if (min > arr[j]) {//说明假定的最小值,并不是最小min = arr[j];//重置minminIndex = j;//重置minIndex}}if (minIndex != 0) {//将最小值,放在arr[0], 即交换arr[minIndex] = arr[0];arr[0] = min;}System.out.println("第1轮后~~");System.out.println(Arrays.toString(arr));//1, 34, 119, 101//第2轮minIndex = 1;min = arr[1];for (int j = 1 + 1; j < arr.length; j++) {if (min > arr[j]) {//说明假定的最小值,并不是最小min = arr[j];//重置minminIndex = j;//重置minIndex}}if (minIndex != 1) {//将最小值,放在arr[1], 即交换arr[minIndex] = arr[1];arr[1] = min;}System.out.println("第2轮后~~");System.out.println(Arrays.toString(arr));//1, 34, 119, 101//第3轮minIndex = 2;min = arr[2];for (int j = 2 + 1; j < arr.length; j++) {if (min > arr[j]) {//说明假定的最小值,并不是最小min = arr[j];//重置minminIndex = j;//重置minIndex}}if (minIndex != 2) {//将最小值,放在arr[2], 即交换arr[minIndex] = arr[2];arr[2] = min;}System.out.println("第3轮后~~");System.out.println(Arrays.toString(arr));//1, 34, 119, 101}
}

选择排序代码:

import java.text.SimpleDateFormat;
import java.util.Date;/*** 选择排序*/
public class SelectSort {public static void main(String[] args) {//int[] arr = {101, 34, 119, 1};int[] arr = {101, 34, 119, 1, 4, 2, 9};System.out.println("排序前:");System.out.println(Arrays.toString(arr));selectSort(arr);System.out.println("排序后:");System.out.println(Arrays.toString(arr));}public static void selectSort(int[] arr) {//在推导的过程,我们发现了规律,因此,可以使用for来解决//选择排序时间复杂度是 O(n^2)for (int i = 0; i < arr.length; i++) {int minIndex = i;int min = arr[i];for (int j = i + 1; j < arr.length; j++) {if (min > arr[j]) {//说明假定的最小值,并不是最小min = arr[j];//重置minminIndex = j;//重置minIndex}}if (minIndex != i) {//将最小值,放在arr[2], 即交换arr[minIndex] = arr[i];arr[i] = min;}}}
}

测试效率的数据 80000,看耗时:

import java.text.SimpleDateFormat;
import java.util.Date;/*** 选择排序*/
public class SelectSort {public static void main(String[] args) {//执行速度是2~3s,比冒泡快//测试一选择排序的速度O(n^2), 给80000个数据 测试int arr[] = new int[80000];for (int i = 0, size = arr.length; i < size; i++) {arr[i] = (int) (Math.random() * 80000);//生成一个【0,80000)数}long startTime = System.currentTimeMillis();selectSort(arr);long endTime = System.currentTimeMillis();SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");String start = dateFormat.format(new Date(startTime));String end = dateFormat.format(new Date(endTime));System.out.println("排序前时间:" + start);// 2023-08-20 13:57:43System.out.println("排序后时间:" + end);// 2023-08-20 13:57:45}public static void selectSort(int[] arr) {//在推导的过程,我们发现了规律,因此,可以使用for来解决//选择排序时间复杂度是 O(n^2)for (int i = 0; i < arr.length; i++) {int minIndex = i;int min = arr[i];for (int j = i + 1; j < arr.length; j++) {if (min > arr[j]) {//说明假定的最小值,并不是最小min = arr[j];//重置minminIndex = j;//重置minIndex}}if (minIndex != i) {//将最小值,放在arr[2], 即交换arr[minIndex] = arr[i];arr[i] = min;}}}
}

相关文章:

第 7 章 排序算法(3)(选择排序)

7.6选择排序 7.6.1基本介绍 选择式排序也属于内部排序法&#xff0c;是从欲排序的数据中&#xff0c;按指定的规则选出某一元素&#xff0c;再依规定交换位置后达到排序的目的。 7.6.2选择排序思想: 选择排序&#xff08;select sorting&#xff09;也是一种简单的排序方法…...

Less文件可以做哪些复杂操作

在Less文件中&#xff0c;你可以进行许多复杂的操作来增强样式表的功能和灵活性。以下是一些常见的操作&#xff1a; 变量&#xff08;Variables&#xff09;&#xff1a;使用符号定义和使用变量&#xff0c;可以在整个样式表中重复使用相同的值&#xff0c;以便轻松修改和维护…...

HTML5岗位技能实训室建设方案

一 、系统概述 HTML5岗位技能技术是计算机类专业重要的核心课程&#xff0c;课程所包含的教学内容多&#xff0c;实践性强&#xff0c;并且相关技术更新快。传统的课堂讲授模式以教师为中心&#xff0c;学生被动式接收&#xff0c;难以调动学生学习的积极性和主动性。混合式教学…...

【Linux】GNOME图形化界面安装

Linux下具有多种图形化界面&#xff0c;每种图形化界面具有不同的功能&#xff0c;在这里我们安装的是GNOME。 1、 挂载yum源 挂载之前首先确保使用ISO映像文件 2.挂载之前先在/mnt下面创建一个cdrom目录用来作为挂载点目录 挂载完成之后那么就要去修改yum源了 Vi /etc/yum.r…...

大数据课程J3——Scala的类定义

文章作者邮箱:yugongshiye@sina.cn 地址:广东惠州 ▲ 本章节目的 ⚪ 了解Scala的柯里化 Currying; ⚪ 掌握Scala的类定义; ⚪ 掌握Scala的样例类、option类; ⚪ 掌握Scala的隐式转换机制; 一、柯里化 Currying 柯里化(Currying)技术 Christopher St…...

Ribbon:使用Ribbon实现负载均衡

Ribbon实现的是实线走的 建立三个数据库 /* SQLyog Enterprise v12.09 (64 bit) MySQL - 5.7.25-log : Database - db01 ********************************************************************* *//*!40101 SET NAMES utf8 */;/*!40101 SET SQL_MODE*/;/*!40014 SET OLD_UNIQ…...

最新最全的~教你如何搭建高可用Lustre双机集群

1.搭建双机lustre高可用集群: 1.环境说明: 主机名系统挂载情况IP地址Lustre集群名内存mds001Centos7.9(共享磁盘)1个mgs,1个MDT,2个OST192.168.10.21/209.21global1Gmds002Centos7.9(共享磁盘)1个mgs,1个MDT,2个OST192.168.10.22/209.22global1GclientCentos7.9无19…...

深入浅出Pytorch函数——torch.nn.init.uniform_

分类目录&#xff1a;《深入浅出Pytorch函数》总目录 相关文章&#xff1a; 深入浅出Pytorch函数——torch.nn.init.calculate_gain 深入浅出Pytorch函数——torch.nn.init.uniform_ 深入浅出Pytorch函数——torch.nn.init.normal_ 深入浅出Pytorch函数——torch.nn.init.c…...

会员管理系统实战开发教程02-H5应用创建

低代码平台作为一个应用的快速生成工具&#xff0c;可以方便的进行一页多端的开发&#xff0c;可以在一个应用里生成三端的应用&#xff0c;也可以拆分成三个应用来制作。三端包括H5、小程序和PC管理后台。 上一篇我们介绍了PC管理后台的创建方法&#xff0c;本篇我们介绍一下…...

记一次由于整型参数错误导致的任意文件上传

当时误打误撞发现的&#xff0c;觉得挺奇葩的&#xff0c;记录下 一个正常的图片上传的点&#xff0c;文件类型白名单 但是比较巧的是当时刚对上面的id进行过注入测试&#xff0c;有一些遗留的测试 payload 没删&#xff0c;然后在测试上传的时候就发现.php的后缀可以上传了&a…...

spring之Spring Security - 实现身份验证与授权

Spring Security - 实现身份验证与授权 标题: Spring Security - 实现身份验证与授权摘要:引言:词汇解释:详细介绍:实现基本的身份验证与授权解释概念:代码示例:注意事项: 定制化认证与授权流程解释概念:代码示例:注意事项: 集成OAuth2认证解释概念:代码示例:注意事项: 总结:参…...

【Unity3D赛车游戏】【二】如何制作一个真实模拟的汽车

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 秩沅 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a;Uni…...

【Linux】线程篇Ⅱ:

线程Ⅱ &#x1f517;接上篇【线程篇Ⅰ】五、线程库 和 线程 id六、同步与互斥 &#x1f517;接上篇【线程篇Ⅰ】 &#x1f449;【Linux】线程篇Ⅰ&#xff1a;线程和task_struct 执行流的理解、相关接口命令、线程异常、线程的私有和共享 五、线程库 和 线程 id 对于 Linux …...

浅尝OpenResty

文章目录 1. 写在前面2. 下载安装openresty2.1 下载Openresty2.2 设置nginx启动 3. 嵌入lua脚本4. 实践5. 小结 1. 写在前面 当一个域名中衍生出多个服务的时候&#xff0c;如果想要保持对外服务始终是一个域名&#xff0c;则需要通过nginx反向代理来实现。如果在转发的时候需…...

MySQL分页查询慢怎么办

今天看到一个问题。 MySQL分页查询慢怎么办&#xff1f; 第一反应是用limit限制返回的条数。 比如 select * from table order by idlimit 10, 100;实际上我们限制的只是返回的条数是100&#xff0c;并不是查询时就从第10条开始获取数据。 所以实际上MySQL会从第0条开始查询&a…...

mongodb集群

端口192.168.115.3 192.168.115.4 1192.168.115.5 下载MongoDB软件包版本为4.2.14并安装 rpm -ih --force --nodeps *.rpm 2创建文件夹mkdir -p /opt/local/mongo-cluster/conf 3.在目录里创建配置文件cd /opt/local/mongo-cluster/conf …...

回归预测 | MATLAB实现WOA-BP鲸鱼优化算法优化BP神经网络多输入单输出回归预测(多指标,多图)

回归预测 | MATLAB实现WOA-BP鲸鱼优化算法优化BP神经网络多输入单输出回归预测&#xff08;多指标&#xff0c;多图&#xff09; 目录 回归预测 | MATLAB实现WOA-BP鲸鱼优化算法优化BP神经网络多输入单输出回归预测&#xff08;多指标&#xff0c;多图&#xff09;效果一览基本…...

【前端从0开始】JavaSript——循环控制语句

循环控制语句 while语句 While 循环会在指定条件为真时循环执行代码块。 While循环&#xff0c;先进行条件判断&#xff0c;再执行循环体的代码 while (条件表达式){循环体 }注意&#xff1a;当前循环中&#xff0c;如果不满足条件&#xff0c;一次都不会执行 var i 1; whi…...

【Elasticsearch】spring-boot-starter-data-elasticsearch的使用以及Elasticsearch集群的连接

更多有关博主写的往期Elasticsearch文章 标题地址【ElasticSearch 集群】Linux安装ElasticSearch集群&#xff08;图文解说详细版&#xff09;https://masiyi.blog.csdn.net/article/details/131109454基于SpringBootElasticSearch 的Java底层框架的实现https://masiyi.blog.c…...

Python学习笔记_进阶篇(四)_django知识(三)

本章内容&#xff1a; Django 发送邮件Django cookieDjango sessionDjango CSRF Django 发送邮件 我们常常会用到一些发送邮件的功能&#xff0c;比如有人提交了应聘的表单&#xff0c;可以向HR的邮箱发邮件&#xff0c;这样&#xff0c;HR不看网站就可以知道有人在网站上提…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)

UniApp 集成腾讯云 IM 富媒体消息全攻略&#xff08;地理位置/文件&#xff09; 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型&#xff0c;核心实现方式&#xff1a; 标准消息类型&#xff1a;直接使用 SDK 内置类型&#xff08;文件、图片等&#xff09;自…...

渗透实战PortSwigger靶场:lab13存储型DOM XSS详解

进来是需要留言的&#xff0c;先用做简单的 html 标签测试 发现面的</h1>不见了 数据包中找到了一个loadCommentsWithVulnerableEscapeHtml.js 他是把用户输入的<>进行 html 编码&#xff0c;输入的<>当成字符串处理回显到页面中&#xff0c;看来只是把用户输…...

API网关Kong的鉴权与限流:高并发场景下的核心实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中&#xff0c;API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关&#xff0c;Kong凭借其插件化架构…...