图解Java经典算法冒泡排序的原理与实现
作者:Binaire-沐辰 发布时间:2023-03-14 21:41:23
冒泡排序
冒泡排序是一种比较简单的排序算法,我们可以重复遍历要排序的序列,每次比较两个元素,如果他们顺序错误就交换位置,重复遍历到没有可以交换的元素,说明排序完成。
算法原理
从第一个元素开始,比较相邻的两个元素,如果第一个大于第二个,则交换它们
对每一对相邻的元素做相同的操作,从第一对到最后一对,最终最后一位元素就是最大值
对每一个元素重复上述步骤,最后一个除外
动图演示
算法练习
题目描述: 给定一个无序数组,利用冒泡排序将数组按升序排列。
示例一:
输入: arrs= [5,0,9,3,-1,12]
输出: arrs= [-1,0,3,5,9,12]
示例二:
输入: arrs= [3,5,9,7,2,1]
输出: arrs= [1,2,3,5,7,9]
解题思路:
通过比较相邻的元素,如果前一个比后一个大,则交换位置。
第一趟:比较第1个和第2个元素,然后是第2个和第3个比较,这样直到倒数第2个和最后1个,将最大的数移动到最后一位。
第二趟:重复上面步骤,将第二大的数交换至倒数第二位。
…
每一趟都会将元素中第 n 大的元素交换到倒数第 n 位。
一共需要n-1趟。
代码实现:
public class BubbleTest {
public static void main(String[] args) {
Integer[] arr = {3,5,9,7,2,1};
Bubble.sort(arr);
System.out.println(Arrays.toString(arr));
}
//数组排序
public static void bubblesort(Comparable[] a){
for (int i = a.length - 1;i > 0;i--){
for (int j = 0;j < i;j++){
if (greater(a[j],a[j + 1])){
swap(a,j,j + 1);
}
}
}
}
//比较 v 是否大于 w
public static boolean greater(Comparable v,Comparable w){
return v.compareTo(w) > 0;
}
//数组元素交换位置
private static void swap(Comparable[] a,int i,int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
算法分析
时间复杂度
冒泡排序是一种用时间换空间的排序方法,最坏情况是把顺序的排列变成逆序,或者把逆序的数列变成顺序。在这种情况下,每一次比较都需要进行交换运算。
而对于有n个元素的数列它的比较次数为 (n-1) + (n-2) + … + 1 = n * (n - 1) / 2;因此它的时间复杂度为O(n^2)。
空间复杂度
冒泡排序的辅助变量只是一个临时变量,不会随数组规模的增大而增大,所以冒泡排序的空间复杂度为O(1)。
来源:https://binaire.blog.csdn.net/article/details/126298003
猜你喜欢
- 一、前言环境:jdk 1.8,SpringCloud Greenwich.SR2。如题,springcloud config-client启
- 效果图如下所示: 1、在Adapter中加入如下代码<pre style="background-color:#2
- 只使用try和finally不使用catch的原因和场景JDK并发工具包中,很多异常处理都使用了如下的结构,如AbstractExecuto
- 不废话了,直接给大家贴代码了。class term { String str; int id; &
- 以前一直接触.net相关的web开发,现在猛然使用javaWeb还是很不习惯,就连搭个框架也是第一次。一、谈谈项目架构一开始接触.net相关
- 一、线程的优先级别线程优先级别的使用范例:package cn.galc.test;public class TestThread6 { p
- 目录前言一、技术介绍1.Minio是什么?二、使用步骤1.引入maven库2.封装Minio3.配置文件4.单元测试总结前言使用Spring
- mybatis使用${}时sql注入的问题最近在上线项目的时候,代码审查没有通过,提示有sql注入的风险。ORDER BY ${orderB
- 1、概念首先我们理解一下,什么叫做完美数?问题描述:若一个自然数,它所有的真因子(即除了自身以外的约数)的和恰好等于它本身,这种数叫做完全数
- 方式一public class Test{ public static void main(String[] args) throws Ex
- Android中有两种主要方式使用Service,通过调用Context的startService方法或调用Context的bindServ
- 微服务通过Feign调用进行密码安全认证在项目中,微服务之间的通信也是通过Feign代理的HTTP客户端通信,为了保护我们的业务微服务不被其
- 前言我们在配置Spring Xml配置文件的时候,可以在文件路径字符串中加入 ${} 占位符,Spring会自动帮我们解析占位符,这么神奇的
- 使用IDEA开发微服务项目,需要启动多个微服务,可以开启IDEA的Run DashBoard窗口,需要对IDEA中指定工程的父工程进行配置进
- Java设计模式的模板方法模式定义一个操作中算法的框架,而将一些步骤延迟到子类中,使得子类可以不改变算法的结构即可重定义该算法中的某些特定步
- Flink中设计了用户自定义函数体系(User Defined Function,UDF),开发人员实现业务逻辑就是开发UDF。一、环境对象
- MVC三层架构我们在刚刚成为程序员的时候,就会被前辈们 “教育” 说系统的设计要遵循 MVC(Model-View-Controller)架
- 员工管理系统1、准备工作资料下载内含源码 + 笔记 + web素材源码下载地址:http://xiazai.jb51.net/202105/
- 下载和上传附件、发送短信和发送邮件,都算是程序中很常用的功能,之前记录了文件的上传和下载还有发送短信,由于最近比较忙,邮件发送的功能就没有时
- ⭐️前面的话⭐️本篇文章带大家认识Java语法——泛型与通配符,泛型和通配符是一个非常抽象的概念,简