手把手教你搞懂冒泡排序和选择排序
作者:小胖java攻城狮 发布时间:2022-05-08 23:08:34
标签:冒泡排序,选择排序
冒泡排序
原理:
从头(左边)开始比较每一对相邻的元素,如果第1个比第2个大,就交换它们的位置,执行完一轮后,最末尾(最右边)就是最大的元素。
举例:
假设存在数组nums={6,8,2,9,4},对nums数组进行排序
从左往右开始,拿出两个元素进行对比,出现两种情况:
1.左边元素 <= 右边元素,不变
2.左边元素 > 右边元素,交换他们的位置(这里可以写成>=吗?不行,因为会造成排序不稳定)
接下来就是新的一轮排序,逻辑跟上图的流程是一样的,不同的是会将最大的元素排除在外,不用进行比较。
手撕代码:
/*
没有使用过优化策略的冒泡排序
*/
public class BubbleSort1 {
//测试数据
public static int[] nums = {4,1,7,11,9,55};
//main方法
public static void main(String[] args){
//这个for循环每循环完一次,end--,说明就把最大的元素给选出来了
for (int end = nums.length - 1; end > 0; end--){
for (int begin = 1; begin <= end; begin++){
if(nums[begin] < nums[begin - 1]){ //每当发现左边的元素大于右边的元素
//交换元素
int temp = nums[begin];
nums[begin] = nums[begin - 1];
nums[begin - 1] = temp;
}
}
}
//打印验证结果
for(int num : nums){
System.out.print(num+"_");
}
}
}
时间复杂度为O(n^2),
也就是n的平方,不过这是平均时间复杂度
存在最好时间复杂度O(n)
,那就是数组本来就有序,也就是说只扫描一遍就行了。
优化策略:
由于存在部分有序的情况,例如nums数组为{8,5,2,10,11,12},也就是说10,11,12都没有比较的必要了
优化代码:
/*
使用过优化策略的冒泡排序
*/
public class BubbleSort1 {
public static int[] nums = {4,1,7,11,9,55};
public static void main(String[] args){
for (int end = nums.length - 1; end > 0; end--){
int sortIndex = 1; //记录最后一次交换位置
for (int begin = 1; begin <= end; begin++){
if(nums[begin] < nums[begin - 1]){
int temp = nums[begin - 1];
nums[begin - 1] = nums[begin];
nums[begin] = temp;
sortIndex = begin;
}
end = sortIndex;
}
}
for(int num : nums){
System.out.print(num+"_");
}
}
}
选择排序
原理:
从数组中找到最大的元素,然后与末尾(最右边)的元素交换位置,执行完一轮后,末尾(最右边)的那个元素就是最大的元素。
举例:
假设存在数组nums={5,8,1,9,3},对nums数组进行排序,准备一个maxIdex代表当前最大元素的下标
接下来就是新的一轮排序,逻辑跟上图的流程是一样的,不同的是会将最大的元素排除在外,不用进行比较。
手撕代码:
/**
* 选择排序
*/
public class SelectionSort {
//测试数据
private static int[] nums = {6,3,2,8,9};
//main方法
public static void main(String[] args){
//这个for循环每循环完一次,end--,说明就把最大的元素给选出来了
for(int end = nums.length - 1; end > 0; end--){
int maxIndex = 0; //假设下标0是数组中最大元素
for(int begin = 1; begin <= end; begin++){ //从左往右开始比较
if(nums[maxIndex] < nums[begin]){ //发现存在一个元素大于假设最大元素
maxIndex = begin; //更改最大元素索引
}
}
//最右边一个元素和最大值元素交换位置
int temp = nums[maxIndex];
nums[maxIndex] = nums[end];
nums[end] = temp;
}
//打印结果
for(int num : nums){
System.out.print(num+"_");
}
}
}
来源:https://blog.csdn.net/qq_45798556/article/details/116936068
0
投稿
猜你喜欢
- 一、根据流向分为输入流和输出流:注意输入流和输出流是相对于程序而言的。输出:把程序(内存)中的内容输出到磁盘、光盘等存储设备中输入:读取外部
- 有个小伙伴遇到了这样一个问题,就是AutoCompleteTextView实现自动填充的功能。同时要具备手机格式化的功能。下拉列表最后一行是
- 通过http://localhost:7002/card/services/HelloWorld?wsdl访问到xml如下,说明接口写对了。
- 可以给已有实体类动态的添加字段并返回新的实体对象,不影响原来的实体对象结构。添加依赖<dependency> &n
- 引言你在服务端的安全管理使用了 Spring Security,用户登录成功之后,Spring Security 帮你把用户信息保存在 Se
- 用java实现简易外卖订餐系统,供大家参考,具体内容如下一、使用技术javaSE二、实现功能外卖订餐系统具体要求如下:使用选择结构,循环结构
- 如果你是想在java目录下创建多级目录,直接新建package,如图输入然后,取消勾选Compact Empty Middle Packag
- 前言${} 和 #{} 都是 MyBatis 中用来替换参数的,它们都可以将用户传递过来的参数,替换到 MyBatis 最终生成的
- 一、先看下项目结构CodeGenerator:生成器主类resources下的mapper.java.vm:一个模板类,用以在生成dao层时
- 前段时间写了一篇基于mybatis实现的多数据源博客。感觉不是很好,这次打算加入git,来搭建一个基于Mybatis-Plus的多数据源项目
- FeignClient脱离eureka自定义URL需求Spring Cloud环境中的FeignClient有时候需要调用特定主机的接口,但
- 本文研究的主要是Java数组的扩容的相关代码示例,具体实现过程如下所示。在写程序的过程中,我们常常会碰见数组空间不够用的情况,比如我已经初始
- idea 鼠标悬浮显示详情2020 版 idea 之前file -> settings设置如下 2020 版 idea 之后
- 1、什么是委托从数据结构来讲,委托是和类一样是一种用户自定义类型。委托是方法的抽象,它存储的就是一系列具有相同签名和返回回类型的方法的地址。
- 本文为大家分享了java学生信息管理系统的源代码,供大家参考,具体内容如下/*学生信息管理系统,实现学生信息: *增加 int[] a=n
- Spring框架的关键组件是面向方面编程(AOP)框架。面向方面的编程不仅打破程序逻辑分成不同的部分称为所谓的担忧。跨越多个点的应用程序的功
- 编写RedisConfig首先我们要明白RedisConfig中需要包含什么,首先看看我们直接使用RedisTemplate的问题,我们就知
- 本文实例为大家分享了javaweb登录验证码的具体代码,供大家参考,具体内容如下使用:Controller:生成验证码@RequestMap
- 简介使用 SpringBoot 配置 FTP 服务器,上传、删除、下载文件。配置 FTP检查是否安装 vsftpdrpm -qa | gre
- 下面是我自己收集整理的2017年Java岗位的面试题,可以用它来好好准备面试。一、Java基础1. String类为什么是final的。2.