一文带你了解Java选择排序的原理与实现
作者:指北君 发布时间:2022-05-13 21:01:31
选择排序:(Selection sort)是一种简单直观的排序算法,也是一种不稳定的排序方法。
选择排序的原理
一组无序待排数组,做升序排序,我们先假定第一个位置上的数据就是最小的,我们用一个参数记录这个最小的数,然后依次把后面的每个位置的数据和这个最小的比较,如果比这个数小就替换两个位置数据,等到第一轮比较完成就能确定最小的数据排在第一位了,然后第二轮从第二个位置开始,相同的方式比较,每次都能找到本轮最小的值,直至全部待排元素个数为0的时候,数组就排好顺序了。
选择排序流程图
我们来进行详细解析看看
首先我们给个无序数组[4,6,15,9,12,3,32]进行升序排序,因为需要确定每个数组的长度,所以需要比较数组长度-1轮,当前面的元素都排好了之后,那么数组最后一个元素自然就确定了位置。
我们定义两个值,minIndex,minNum用来分别表示每一轮的找到的最小值的下标和值,后面未排序的值都和minNum比较,从而找出每一轮的最小值。
第一轮我们以下标为1的第一位作为标志位(也就是把第一个值当做最小值),那么此时minIndex=0,minNum=4,经过和 minNum 比较发现后面只有3比4小,那么3和4交换位置,minIndex=5,minNum=3,把4换到下标为5的位置,如下图所示:
第一轮我们得到的结果是[3,6,15,9,12,4,32],本轮最小数是:3,所以3放到本轮标志位,也就是第一位
第二轮:拿到第一轮排序的值作为初始值[3,6,15,9,12,4,32],同第一轮一样,此时6作为标志位minNum=6,minNum和其他比较,只有4比6小,需要交换位置,如下图所示
第二轮排序结果[3,4,15,9,12,6,32],本轮最小数是:4
第三轮:初始值[3,4,15,9,12,6,32],这次标志位15,minNum=15,minIndex=2,minNum先比和9比较,发现9比15小,minNum=9,minIndex=3,然后minNum和12比较,不需要替换minNum,再和6比较,minNum=6,minIndex=5,后面再比较已经没有比6小了,那么本轮就是初始标志位15和下标为5,值为6的数据换位置。
第三轮排序结果[3,4,6,9,12,15,32],本轮最小数是:6
第四、五、六轮:初始值[3,4,6,9,12,15,32],经过前面的比较我们可以看到数组已经排序完成,但是程序并不知道,会继续比较下去,把下标为4、5、6位置都作为标志位比较一次,发现都不需要变动位置,那么最终执行完成之后就能排序完成
第四、五、六轮排序结果[3,4,6,9,12,15,32]
到这,我们已经清楚了每个步骤做了什么,那么接下来上代码验证一下:
Java代码实现
public class selectionSort {
public static void main(String[] args){
int[] arr = new int[]{4,6,15,9,12,3,32};
for(int i=0;i<arr.length-1;i++){//每次循环都会找出最小的数
//记录最小数的下标
int minIndex = i;
//记录最小数
int minNum = arr[i];
//每次循环都会找出最小的数
for(int j=i+1;j<arr.length;j++){
if(arr[j]<minNum){//如果当前数比最小数小,则更新最小数
minNum = arr[j];//更新最小数
minIndex = j;//更新最小数的下标
}
}
//将最开始假定的小的数移动到真实最小的位置
arr[minIndex]=arr[i];
arr[i]=minNum;//将标志位放到最小数原来所在的位置
//打印结果,方便查看
System.out.print("第"+(i+1)+"轮[");
for(int a=0;a<arr.length;a++){
System.out.print(arr[a]+"\t");
}
System.out.println ("],本轮最小数是:"+minNum);
}
System.out.print("最终结果[");
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+"\t");
}
System.out.println("]");
}
}
输出结果
第1轮[3 6 15 9 12 4 32 ],本轮最小数是:3
第2轮[3 4 15 9 12 6 32 ],本轮最小数是:4
第3轮[3 4 6 9 12 15 32 ],本轮最小数是:6
第4轮[3 4 6 9 12 15 32 ],本轮最小数是:9
第5轮[3 4 6 9 12 15 32 ],本轮最小数是:12
第6轮[3 4 6 9 12 15 32 ],本轮最小数是:15
最终结果[3 4 6 9 12 15 32 ]
时间复杂度
我们通过上面的细节拆分发现,无论是否是已经排好的还是没排好的情况,我们都需要每个数字都比较到,那么就出现N个元素的数组,第一轮是n次比较,第二轮是从第二个位置开始,那么就是n-1,第三轮就是n-2次... 最后是1,那么就出现了n+(n-1)+(n-2)+(n-3)...1,这是一个等差数列,求和为一个二次型多项式,因为等差数列求和会出现二次型;我们取最高阶就是n^2,所以时间复杂度就是O(n^2),而且最好和最坏的情况时间复杂度都是O(n^2)
来源:https://mp.weixin.qq.com/s/QdvJW32ANKJO8SBJ3GvxVA
猜你喜欢
- 简单的理解,MyBatis逆向工程,就是通过相应插件,自动生成MyBatis数据库连接的一些文件。mybatis需要编写sql语句,myba
- 一:什么是SparkSQL?(一)SparkSQL简介Spark SQL是Spark的一个模块,用于处理结构化的数据,它提供了一个数据抽象D
- 基于jsr303 通过自定义注解实现,实现思路:存在一些瑕疵,后续补充完善。加入依赖部分版本已不默认自动引入该依赖,选择手动引入<de
- 在intellij中忽略提交文件,分两种情况,文件没有纳入版本管理第一种方法文件还没有纳入版本管理,这种通过 svn的ignore配置ver
- Mapper 就是“映射”的意思,Mapper 文件时 Mybatis 中的 SQL 语句的配置文件
- 了解YMP框架YMP于2014年10月25日正式发布1.0版本,在此之前就已在实际项目中得到广泛使用,从最初仅限团队内部使用,到合作伙伴的开
- 先上图:新建好springboot项目之后这里没生成pom.xml文件我开始试了一下网上的方法,在新建的时候修改choose spring
- 本地仓库主要是一种缓存,当你使用远程仓库中下载组件后,它下一次会优先从本地进行加载,一般位于USER_HOME/.m2目录下,我们自己也可以
- 1. 前言Spring的核心技术IOC(Intorol of Converse控制反转)的实现途径是DI(dependency Insert
- 一、案例场景遇到过这样的场景,在定义一个static修饰的Map时,使用了大量的put()方法赋值,就类似这样——public static
- FileOutPutStream:子类,写出数据的通道步骤:1.获取目标文件2.创建通道(如果原来没有目标文件,则会自动创建一个)3.写入数
- 一、封装类1.封装类概念Java中存在基础数据类型,但是在某些情况下,我们要对基础数据类型进行对象的操作,例如,集合中只能存对象,而不能存在
- 场景既然要搞懂Redis分布式锁,那肯定要有一个需要它的场景。高并发售票问题就是一个经典案例。搭建环境准备redis服务,设置redis的键
- 本文实例为大家分享了java实现单词小游戏的具体代码,供大家参考,具体内容如下介绍公司最近有一个竞技场项目,里面有一个单词小游戏。游戏大概就
- 最近在做代码优化时学习和研究了下JAVA多线程的使用,看了菜鸟们的见解后做了下总结。1、继承Thread类实现多线程继承Thread类的方法
- 懒加载---就是我们在spring容器启动的是先不把所有的bean都加载到spring的容器中去,而是在当需要用的时候,才把这个对象实例化到
- 本文实例讲述了Java使用Math.random()结合蒙特卡洛方法计算pi值。分享给大家供大家参考,具体如下:一、概述蒙特·卡罗方法(Mo
- Guava Cache:⾕歌开源缓存框架Guava Cache是在内存中缓存数据,相比较于数据库或redis存储,访问内存中的数据会更加高效
- 基于有了OO的基础后,开始认真学习设计模式!设计模式是java设计中必不可少的!Apple.javapackage strategy;/**
- 前言dynamic-tp是一个轻量级的动态线程池插件,它是一个基于配置中心的动态线程池,线程池的参数可以通过配置中心配置进行动态的修改,在配