Java 十大排序算法之冒泡排序刨析
作者:龍弟-idea 发布时间:2022-07-05 19:30:29
标签:Java,冒泡排序,排序算法
冒泡排序原理
①比较相邻的元素,如果前一个元素比后一个元素大,则交换这两个元素的位置
②对每一对相邻的元素循环上面的步骤,最终最后面的元素就是最大值
冒泡排序API设计
类名 | Bubble |
构造方法 | Bubble:创建Bubble对象 |
成员方法 | 1.public static void sort(Comparable[] a):对数组内元素进行排序 2.private static void greater(Comparable v,Comparable w);判断v是否大于w 3.private static void exchange(Comparable[] a,int x,int y):交换a数组中,索引x和索引y处的值 |
冒泡排序的代码实现
public class Bubble {
//对数组a进行排序
public static void sort(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])){
exchange(a,j,j+1);
}
}
}
}
//比较v元素是否大于w元素
private static boolean greater(Comparable v,Comparable w){
return v.compareTo(w)>0;
}
//数组元素x和y交换位置
private static void exchange(Comparable[] a,int x,int y){
Comparable t=a[x];
a[x]=a[y];
a[y]=t;
}
}
//测试代码
class Test{
public static void main(String[] args) {
Integer[] a={4,5,6,3,2,1};
Bubble.sort(a);
System.out.println(Arrays.toString(a));
}
}
测试结果:
冒泡排序的时间复杂度分析
冒泡排序虽然采用了双层for循环遍历,但是真正完成排序的代码在内循环中,所以主要分析内层循环体的执行次数即可
在最坏的情况下。即数组为{6,5,4,3,2,1}的逆序
元素的比较次数为:(N-1)+(N-2)+(N-3)+...+2+1=
((N-1)+1)*(N-1)/2=N^2/2-N/2;
元素的交换次数为:(N-1)+(N-2)+(N-3)+...+2+1=
((N-1)+1)*(N-1)/2=N^2/2-N/2;
总执行次数为:2*(N^2/2-N/2)=N^2-N;
根据大O推导法则,保留最高阶项,即冒泡排序的时间复杂度为O(N^2)
来源:https://blog.csdn.net/weixin_48838340/article/details/121341772
0
投稿
猜你喜欢
- 在Android Studio中对一个自己库进行生成操作时将会同时生成*.jar与*.aar文件。分别存储位置: &n
- 1、原理事务的概念想必大家都很清楚,其ACID特性在开发过程中占有重要的地位。同时在并发过程中会出现一些一致性问题,为了解决一致性问题,也出
- 1. Easy Rules 概述Easy Rules是一个Java规则引擎,灵感来自一篇名为《Should I use a Rules En
- 一、Spring Boot Admin 的概念 Spring Boot Admin是一个
- 前言在网络通信中,通信传输数据容易被截取或篡改,如果在传输用户隐私数据过程中,被不法分子截取或篡改,就可能导致用户受到伤害,比如被诈 骗,所
- 下面是一个邮件接收的工具类,有点长!!!public class ReciveMail { private MimeMessage msg
- 加密代码using System;using System.IO;using System.Security.Cryptography;pu
- Java中如何输出像1-2-3-4-5 这样的字符抱歉对于这个问题我甚至不能想到一个合适的标题,但是不重要 以下操作基于 jdk 1.8St
- Java是一门天然的面向对象的语言。而所有我们手动创造出来的类,都继承于同一个类,即Object类。可以看一下Object类的结构nativ
- 前言当你编写一个应用时,你通常都会希望用户能够定制化他们和应用交互的方式,以及应用与系统进行交互的方式。这种方式通常被称为 &ldq
- 预加载bean在springBoot启动过程中就完成创建加载在AbstractApplicationContext的refresh方法中//
- 前言最近学习java,接触到了回调机制(CallBack)。初识时感觉比较混乱,而且在网上搜索到的相关的讲解,要么一言带过,要么说的比较单纯
- MyBatis插入Insert、InsertSelective的区别逆向自动生成的mybatis对应配置Mapper文件里面,有两个方法,分
- 方法一:1.在pom.xml文件下添加依赖包<dependency><groupId>com.alibaba<
- 用Java编写简单的五子棋,供大家参考,具体内容如下前言这两天在空闲时间做了个五子棋项目,分享给大家看一下,界面是这样的:界面很丑我知道,本
- LocalDateTime 是 Java 8 中日期时间 API 提供的一个类,在日期和时间的表示上提供了更加丰富和灵活的支持。LocalD
- Java 内存划分: 在Java内存分配中,java将内存分为:方法区,堆,虚拟机栈,本地方法栈,程序计
- 在你的jar文件当前目录中建立一个bat文件:内容是:注意文件名要对应@echo offSTART "commandServer&
- 前言在一些日常业务中,会遇到一些琐碎文件需要统一打包到一个压缩包中上传,业务方在后台接收到压缩包后自行解压,然后解析相应文件。而且可能涉及安
- 基于Java swing+MySQL实现学生信息管理系统:主要实现JDBC对学生信息进行增删改查,应付一般课设足矣,分享给大家。(由于篇幅原