【排序算法】选择排序

文章目录

  • 一:基本介绍
    • 1.1 概念
    • 1.2 算法思想
    • 1.3 思路分析图
    • 1.4 思路分析
    • 1.5 总结
      • 1.5.1 选择排序一共有数组大小-1轮排序
      • 1.5.2 每一轮排序,又是一个循环,循环的规则如下(在代码中实现):
  • 二:代码实现
    • 2.1 源码
    • 2.2 执行结果
    • 2.3 测试八万条数据
  • 三:算法性能分析
    • 3.1 时间复杂度
    • 3.2 空间复杂度
    • 3.3 稳定性

一:基本介绍

1.1 概念

选择排序(select sorting)属于内部排序法,是从待排序的数据中,按指定的规则选出某一元素,再按照规定交换位置后达到排序的目的。

1.2 算法思想

第一次从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次,得到一个按排序码从小到大排列的有序序列。

每一次从待排序的数据元素中选出最小(或最大)的一个元素,将元素存放在序列的起始位置(即与待排序列的第一个元素的位置进行交换)。然后再从剩余的未排序元素中寻找最小(或最大)的元素,然后存放在已排序序列的末尾。以此类推,直到将待排序的元素全部排完。

1.3 思路分析图

在这里插入图片描述

1.4 思路分析

原始数组:[86, 21, 156, 6]

第一次排序: 从4个元素里面找到最小的,与第1个元素进行交换,将最小元素存放在起始位置

排序后为:6,21 , 156, 86

第二趟排序: 从剩下的3个元素里面找到最小的,与待排序列的第1个元素进行交换,将最小元素存放在已经排好序的序列尾部。

排序后为:6,21 , 156, 86

第三趟排序: 从剩下的2个元素里面找最小的,与待排序列的第1个元素进行交换

排序后为:6,21 , 86,156

1.5 总结

1.5.1 选择排序一共有数组大小-1轮排序

1.5.2 每一轮排序,又是一个循环,循环的规则如下(在代码中实现):

  • 先假定当前这个数是最小数
  • 和后面的每个数进行比较,如果发现有比它更小的数,就重新确定最小数,并得到下标
  • 当遍历完数组之后,就会得到本轮最小数及其下标
  • 进行交换

二:代码实现

2.1 源码

import java.util.Arrays;/*** 选择排序*/
public class SelectSort {public static void main(String[] args) {int[] array = new int[8];for (int i = 0; i < array.length; i++) {//Math.random() * 80000生成0到100的随机数array[i] = (int) (Math.random() * 100);}System.out.println("排序前:" + Arrays.toString(array));selectSort(array);System.out.println("排序后:" + Arrays.toString(array));}/*** 选择排序** @param array 需要排序的数组*/public static void selectSort(int[] array) {//使用逐步推倒的方式来讲解选择排序//第一轮//原始的数组:101,34,119,1//第一轮排序:1,34,101,119//算法先简单-->后复杂。可以将复杂算法简单化for (int i = 0; i < array.length - 1; i++) {//第一轮//假定最小处的索引就是0int minIndex = i;//最小处的数值则为int min = array[minIndex];for (int j = i + 1; j < array.length; j++) {if (min > array[j]) {//如果此条件成立,说明假定的最小值就不成立//此时我们需要重置最小值minIndex = j;min = array[minIndex];}}//交换之前需要进行判断if (minIndex != i) {//for循环结束后则最小值就已经找到了,此时我们需要将下标为0处的数重新替换为最小值//将原本最小值的位置替换为array[0]array[minIndex] = array[i];//将最小值放在array[0],即交换array[i] = min;}System.out.println("第" + i + "轮过后排序为:" + Arrays.toString(array));}}
}

2.2 执行结果

在这里插入图片描述

2.3 测试八万条数据

在这里插入图片描述
八万个数据的排序时间是1536毫秒,很明显是比冒泡排序短很多的!

三:算法性能分析

3.1 时间复杂度

最优时间复杂度、最坏时间复杂度、平均时间复杂度都是O(n^2),因为无论你是否完全有序,还是完全逆序,都需要找出后边的最小值进行替换。

相比较冒泡排序,每次比较后,只更新最小值的下标,每轮循环值最多只做一次值交换。时间上得到了很大的提升。但是也是使用了双层循环,时间复杂度和冒泡排序的一样。

3.2 空间复杂度

空间复杂度为O(1)

3.3 稳定性

选择排序是不稳定的排序算法。

举个例子:

例如数组:[ 5 , 8 , 5 , 2 ]

使用选择排序算法第一次找到的最小元素是2,与第一个位置的元素5进行交换,那此时第一个5和中间的5顺序就发生了变化,因此不稳定。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/154418.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

VueRouter与expres/koa中间件的关联

ueRouter: runQueue 路由守卫都是有三个参数to,from,next。其中next就是下方的fn执行时候传入的第二个参数(回调函数)&#xff0c;只有该回调执行后才会挨个遍历queue内的守卫。 中间件的作用 隔离基础设施与业务逻辑之间的细节。详细的内容位于《深入浅出Node.js》P210 另外一…

CSS设置鼠标样式和添加视频样式

鼠标的样式 <div style"cursor: default">默认鼠标的样式</div><div style"cursor: pointer">小手样式</div><div style"cursor: move">移动样式</div><div style"cursor: text">文本样式&…

Twitter优化秘籍:置顶、列表、受众增长

在 Twitter 上&#xff0c;将你的一条推送文置顶到个人数据顶部是提高可见性和吸引关注者的绝佳方式。无论你是个人用户还是企业&#xff0c;此功能都可以让你的重要信息常驻在众人眼前&#xff0c;即使你发布了新的推文。接下来&#xff0c;我们将分享一些优化建议&#xff0c…

防雷排插的防雷应用以及解决方案

防雷排插是一种能够有效防止雷电对电器设备造成损坏的电源插座。防雷排插的应用&#xff0c;原理和作用如下&#xff1a; 地凯科技防雷排插的应用&#xff1a;防雷排插主要用于保护电脑&#xff0c;电视&#xff0c;音响等电子设备免受雷击或者电网过压的影响。防雷排插通常有…

随着 ChatGPT 凭借 GPT-4V(ision) 获得关注,多模态 AI 不断发展

原创 | 文 BFT机器人 在不断努力让人工智能更像人类的过程中&#xff0c;OpenAI的GPT模型不断突破界限GPT-4现在能够接受文本和图像的提示。 生成式人工智能中的多模态表示模型根据输入生成文本、图像或音频等各种输出的能力。这些模型经过特定数据的训练&#xff0c;学习底层模…

学生台灯买什么样的好?双十一学生台灯推荐

不得不说光线会孩子的影响还是蛮大的&#xff0c;不仅会影响学习的效率&#xff0c;还会影响视力健康。很多家长认为孩子近视的主要原因是玩电子产品或者不良的坐姿、用眼习惯导致的&#xff0c;其实这些并不全是造成近视的因素&#xff0c;最主要的原因还是长时间的用眼导致的…

HTML5使用html2canvas转化为图片,然后再转为base64.

介绍 场景&#xff1a;今天同事提了个协助&#xff0c;将HTML5文件中的元素转为图片&#xff0c;并且最终转为base64格式传给后端。感觉还挺有意思就记录下。&#xff08;试例如下&#xff09; 步骤一&#xff1a;引入html2canvas 的js源码 html2canvas.min.js 下载地址 htt…

【密码学】Java实现DH函数时出现“Unsupported secret key algorithm: AES“错误

问题描述 jdk版本&#xff1a;8 使用DH和AES算法&#xff0c;实现密钥的交换和加密&#xff0c;测试时报错 java.security.NoSuchAlgorithmException: Unsupported secret key algorithm: AESat com.sun.crypto.provider.DHKeyAgreement.engineGenerateSecret(DHKeyAgreement…

vue 项目打包性能分析插件 webpack-bundle-analyzer

webpack-bundle-analyzer 是 webpack 的插件&#xff0c;需要配合 webpack 和 webpack-cli 一起使用。这个插件可以读取输出文件夹&#xff08;通常是 dist&#xff09;中的 stats.json 文件&#xff0c;把该文件可视化展现&#xff0c;生成代码分析报告&#xff0c;可以直观地…

高效数据传输:Java通过绑定快速将数据导出至Excel

摘要&#xff1a;本文由葡萄城技术团队原创并首发。转载请注明出处&#xff1a;葡萄城官网&#xff0c;葡萄城为开发者提供专业的开发工具、解决方案和服务&#xff0c;赋能开发者。 前言 把数据导出至 Excel 是很常见的需求&#xff0c;而数据的持久化&#xff0c;往往又放在…

2023年入职/转行网络安全,该如何规划?

前言 前段时间&#xff0c;知名机构麦可思研究院发布了 《2022年中国本科生就业报告》&#xff0c;其中详细列出近五年的本科绿牌专业&#xff0c;其中&#xff0c;信息安全位列第一。 网络安全前景 对于网络安全的发展与就业前景&#xff0c;想必无需我多言&#xff0c;作为…

SQL sever中的视图

目录 一、视图概述&#xff1a; 二、视图好处 三、创建视图 法一&#xff1a; 法二&#xff1a; 四、查看视图信息 五、视图插入数据 六、视图修改数据 七、视图删除数据 八、删除视图 法一&#xff1a; 法二&#xff1a; 一、视图概述&#xff1a; 视图是一种常用…

亚马逊测评工作室应该如何开展,需要准备哪些?

亚马逊测评自养号项目需要用到哪些资源呢&#xff1f;1. 防火墙独立的环境 纯净IP注册资料收货地址支付卡邮箱及手机号 想做好这个项目以上的资源缺一不可 我们先来说说养号的环境&#xff0c;养号的环境在以前的文章里也提到过&#xff0c;有很多种方案&#xff0c;我们曾经…

JUC并发编程:Monitor和对象结构

JUC并发编程&#xff1a;Monitor和对象结构 1. Monitor1.1 对象的结构1.1.1 MarkWord1.1.2 Klass Word1.1.3 数组长度1.1.4 &#x1f330; 1. Monitor Monitor官方文档 我们可以把Monitor理解为一个同步工具&#xff0c;也可以认为是一种同步机制。它通常被描述为一个对象&…

软考高级架构师下篇-18大数据架构理论设计与实践

目录 1. 引言2. 传统数据处理系统的问题1.传统数据库的数据过载问题2.大数据的特点3.大数据利用过程4.大数据处理系统架构分析3.典型的大数据架构1. Lambda架构2.Kappa架构3. Lambda架构与Kappa架构的对比4.大数据架构的实践1.大规模视频网络2.广告平台3.公司智能决策大数据系统…

Android系统修改AOSP输入法默认输入语言

Android系统中的Android键盘(AOSP)有个语言设置选项,里面默认的是“使用系统语言”,现在客户要求关闭默认“使用系统语言”,打开美式英语。即默认如下图: 网上很多方法都是设置输入法的Settings.Secure.SELECTED_INPUT_METHOD_SUBTYPE属性为 -921088104。实际测试在Andr…

黑盒测试方法:原理+实战

目录 一、如何设计测试用例 二、黑盒测试常用方法 1、基于需求进行测试用例的设计 2、等价类 3、边界值 4、判定表分析法&#xff08;因果分析法&#xff09; 5、正交表 6、场景设计法 三、案例补充 1、使用Fiddler模拟弱网 2、针对一个接口该如何测试 一、如何设计测试…

算法——动态规划

一、 53. 最大子数组和 - 力扣&#xff08;LeetCode&#xff09; 最大子数组和&#xff0c;可以建立一个dp表&#xff0c;来存放当前的位置的累加的最大和 int maxSubArray(vector<int>& nums) {int nnums.size();if(n1)return nums[0];vector<int> dp(n);int…

【办公自动化】在Excel中按条件筛选数据并存入新的表2.0(文末送书)

&#x1f935;‍♂️ 个人主页&#xff1a;艾派森的个人主页 ✍&#x1f3fb;作者简介&#xff1a;Python学习者 &#x1f40b; 希望大家多多支持&#xff0c;我们一起进步&#xff01;&#x1f604; 如果文章对你有帮助的话&#xff0c; 欢迎评论 &#x1f4ac;点赞&#x1f4…

利达卓越:绿色金融助推经济高质量发展

随着环境问题的日益突出和可持续发展的需求增加,绿色金融将成为金融发展的重要方向之一。政府、金融机构、企业和公众都将加大对绿色金融的支持和关注,绿色金融也将更加成熟和规范。利达卓越积极推动绿色金融的快速发展,为实现可持续发展目标提供了重要支持。绿色金融将成为金融…