Java经典算法汇总之选择排序(SelectionSort)
作者:神话丿小王子 发布时间:2021-12-23 03:59:52
a)原理:每一趟从待排序的记录中选出最小的元素,顺序放在已排好序的序列最后,直到全部记录排序完毕。也就是:每一趟在n-i+1(i=1,2,…n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。(这里只介绍常用的简单选择排序)
b)简单选择排序的基本思想:给定数组:int[]arr={里面n个数据};第1趟排序,在待排序数据arr[1]~arr[n]中选出最小的数据,将它与arrr[1]交换;第2趟,在待排序数据arr[2]~arr[n]中选出最小的数据,将它与r[2]交换;以此类推,第i趟在待排序数据arr[i]~arr[n]中选出最小的数据,将它与r[i]交换,直到全部排序完成。
c)举例:数组int[]arr={5,2,8,4,9,1};
-------------------------------------------------------
第一趟排序: 原始数据:528491
最小数据1,把1放在首位,也就是1和5互换位置,
排序结果:128495
-------------------------------------------------------
第二趟排序:
第1以外的数据{28495}进行比较,2最小,
排序结果:128495
-------------------------------------------------------
第三趟排序:
除1、2以外的数据{8495}进行比较,4最小,8和4交换
排序结果:124895
-------------------------------------------------------
第四趟排序:
除第1、2、4以外的其他数据{895}进行比较,5最小,8和5交换
排序结果:124598
-------------------------------------------------------
第五趟排序:
除第1、2、4、5以外的其他数据{98}进行比较,8最小,8和9交换
排序结果:124589
-------------------------------------------------------
注:每一趟排序获得最小数的方法:for循环进行比较,定义一个第三个变量temp,首先前两个数比较,把较小的数放在temp中,然后用temp再去跟剩下的数据比较,如果出现比temp小的数据,就用它代替temp中原有的数据。具体参照后面的代码示例,相信你在学排序之前已经学过for循环语句了,这样的话,这里理解起来就特别容易了。
代码示例:
//选择排序
public class SelectionSort {
public static void main(String[] args) {
int[] arr={1,3,2,45,65,33,12};
System.out.println("交换之前:");
for(int num:arr){
System.out.print(num+" ");
}
//选择排序的优化
for(int i = 0; i < arr.length - 1; i++) {// 做第i趟排序
int k = i;
for(int j = k + 1; j < arr.length; j++){// 选最小的记录
if(arr[j] < arr[k]){
k = j; //记下目前找到的最小值所在的位置
}
}
//在内层循环结束,也就是找到本轮循环的最小的数以后,再进行交换
if(i != k){ //交换a[i]和a[k]
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
System.out.println();
System.out.println("交换后:");
for(int num:arr){
System.out.print(num+" ");
}
}
}
运行结果截图:
选择排序的时间复杂度:简单选择排序的比较次数与序列的初始排序无关。假设待排序的序列有N个元素,则比较次数永远都是N(N-1)/2。而移动次数与序列的初始排序有关。当序列正序时,移动次数最少,为0。当序列反序时,移动次数最多,为3N(N-1)/2。
所以,综上,简单排序的时间复杂度为O(N2)。
猜你喜欢
- Android中有两种主要方式使用Service,通过调用Context的startService方法或调用Context的bindServ
- FFmpeg是一套可以用来记录、转换数字音频、视频,并能将其转化为流的开源计算机程序。采用LGPL或GPL许可证。它提供了录制、转换以及流化
- 1.短信平台购买次数地址https://market.aliyun.com/products/57000002/cmapi00046920.
- 1.微信配置信息 global.properties2.方法wxpay用于生成预支付订单信息方法notifyWeiXinPay用于微信支付成
- Spring main方法调用Dao层和Service层的方法在web环境中,一般serviceImpl中的dao之类的数据库连接都由容器启
- 目标效果: 点击动画按钮之后每张牌各自旋转 散开到屏幕上半部分的任意位置之后回到初始位置 比较像LOL男刀的技能动画 : )1: 创建卡牌对
- 按照官方文档进行的配置:快速开始|mybatis-plus引入依赖:<!-- 引入mybatisPlus --> &
- 摘要:这个问题算是老生常谈了,我也是一段时间没弄过了,所以感觉有些忘了,就记录一下。一、后端通过shiro在session中存储数据://
- 需要用到 java 写一个 ftp 的工具,因为只有一点点 java 基础,但是由于好几年不用,几乎算是不会了,只好一点点来搞,还好能捡起来
- JAVA调用webservice,当你刚开始接触的时候你会觉得它是一个恶梦,特别是没有一个统一的标准实现,比起.net的那些几步
- 一:问题描述 在已经root过的android设备下,app执行一个linux命令,app需要获取su权限,在某些a
- 关于idea2021最新激活教程,请点击此处,获取最新激活教程还有一种激活方法,点击此处获取吧 !下面看下IDEA 2021.2 启动报错问
- 一、链表的介绍什么是链表链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结
- 前段时间写了一篇基于mybatis实现的多数据源博客。感觉不是很好,这次打算加入git,来搭建一个基于Mybatis-Plus的多数据源项目
- 线程中断机制提供了一种方法,用于将线程从阻塞等待中唤醒,尝试打断目标线程的现有处理流程,使之响应新的命令。Java 留给开发者这一自由,我们
- 新建一个集合List<Bill> billList = new ArrayList<>();将订单中所有物品的名称提
- 1.可能是缓存导致的。解决方法:清除缓存!2.全局编译可能项目依赖别的模块,别的模块修改未进行编译,这时须先对依赖模块进行编译补充知识:ID
- public void add(intindex, Eelement)从index索引的位置添加element元素,后面的元素都往
- yaml语法注解配置文件两种形式application.properties和.yaml第一种语法 key=value第二种key:空格va
- 目录环境准备1.数据库操作1.1获取所有数据库1.2获取指定库的所有集合名1.3.删除数据库2.文档操作2.1插入文档2.2查询文档2.3分