Java排序之冒泡排序的实现与优化
作者:指北君 发布时间:2023-11-10 21:35:56
jwt简介
冒泡排序:(Bubble Sort)是一种简单的交换排序。之所以叫做冒泡排序,因为我们可以把每个元素当成一个小气泡,根据气泡大小,一步一步移动到队伍的一端,最后形成一定对的顺序。
冒泡排序的原理
我们以一个队伍站队为例,教官第一次给队员排队是无序的,这时候就需要排队,按矮到高的顺序排列,首先拎出第一第二个比较,如果第一个队员比第二个要高,则两个交换位置, 高的放到排到第二个位置,矮的就排到第一个,再把第二个,第三个比较,把高的排到后面一个位置,然后以此类推,直至第一轮所有队员都比较过一次(记住每次比较都是相邻的两个),这样就可以把最高的排到最后的位置。
总结就是: 每一轮都需要从第一位开始进行相邻的两个数的比较,将较大的数放后面,比较完毕之后向后挪一位继续比较下面两个相邻的两个数大小关系,重复此步骤,直到最后一个还没归位的数。
冒泡排序流程图
我们进行分解看看每一步是怎么执行的
首先我们给个无序数组 [3,14,32,16,53,8] 进行升序排序
第一轮:初始值 [3,14,32,16,53,8]
如图所示,走完第一轮之后,我们得到的结果就是[3,14,16,32,8,53],此时已经将最大的数53排到了指定位置,所以冒泡排序每一轮只能确定将一个数归位。即第一趟只能确定将末位上的数归位, 第二趟只能将倒数第 2 位上的数归位,依次类推下去
第二轮:初始值 [3,14,16,32,8,53]
第二轮排序结果[3,14,16,8,32,53]
第三轮:初始值 [3,14,16,8,32,53]
第三轮排序结果[3,14,8,16,32,53]
第四轮:初始值 [3,14,8,16,32,53]
第四轮排序结果[3,8,14,16,32,53]
第五轮:初始值 [3,8,14,16,32,53]
第五轮排序结果[3,8,14,16,32,53] 到这,我们最终排序完成。
Java代码实现
public static void bubbleSort(int[] array){
for(int i=0;i<array.length-1;i++){//控制比较轮次,一共 n-1 趟
int num = 0; //用来记录比每轮比较的次数
for(int j=0;j<array.length-1;j++){//控制两个挨着的元素进行比较
if(array[j] > array[j+1]){
//换位
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
//比较一次,加1
num =num+1;
}
//结果输出
System.out.print("第"+(i+1)+"轮:[");
for (int a=0;a<array.length; a++){
if(a!=array.length-1)
{
System.out.print(array[a]+",");
}else{
System.out.print(array[a]+"]");
}
}
System.out.println(",比较了:"+num+" 次");
}
}
输出结果
第1轮结果:[3,14,16,32,8,53],每轮比较了:5 次
第2轮结果:[3,14,16,8,32,53],每轮比较了:5 次
第3轮结果:[3,14,8,16,32,53],每轮比较了:5 次
第4轮结果:[3,8,14,16,32,53],每轮比较了:5 次
第5轮结果:[3,8,14,16,32,53],每轮比较了:5 次
我在每轮比较的时候定义了一个num来记录比较次数,大家可以看到长度为6的数组比较,比较了5轮,每轮都比较了5次, 但是通过上面拆分的每一轮比较细节可以看出,其实约到后面的比较,有一部分已经是排好了,如果某个数比他的下一个位置还小, 就没有必要和后面已经排好的数据再做比较,这样只会增加程序运行压力。
比如,第四轮,8和14比较,换位之后,16,32,53都已经排好了,14再和16比较,不用换位,那16之后的数据已经在第三轮排好,就没必要再比较16和32,32和53了。
那我们来对程序做一个优化,其实在第一轮把最大的数字排到最后之后,第二轮就不用再和最后一个数字比较,因为最大的数字已经排好,再比较也只能排在最后一位之前了。
优化
我们就在程序内层循环做一个限制,每轮比较之后,下一轮就比较到array.length-1-i的位置。就是第一轮6位数都比较完成,最大排在最后,第二轮就比较前五个数,把前五个数中最大的排在第五位。这样以此类推,就可以减少程序中无用的比较。
优化代码如下:
public static void bubbleSort(int[] array){
for(int i=0;i<array.length-1;i++){//控制比较轮次,一共 n-1 趟
int num = 0; //用来记录比每轮比较的次数
//每一轮比较一次就排除最后一位,每轮的最后一位一定是这轮最大的,所以-i,
for(int j=0;j<array.length-1-i;j++){//控制两个挨着的元素进行比较
//换位
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
//比较一次,加1
num =num+1;
}
//结果输出
System.out.print("第"+(i+1)+"轮结果:[");
for (int a=0;a<array.length; a++){
if(a!=array.length-1)
{
System.out.print(array[a]+",");
}else{
System.out.print(array[a]+"]");
}
}
System.out.println(",每轮比较了:"+num+" 次");
}
}
我们再来看看结果:
第1轮结果:[3,14,16,32,8,53],每轮比较了:5 次
第2轮结果:[3,14,16,8,32,53],每轮比较了:4 次
第3轮结果:[3,14,8,16,32,53],每轮比较了:3 次
第4轮结果:[3,8,14,16,32,53],每轮比较了:2 次
第5轮结果:[3,8,14,16,32,53],每轮比较了:1 次
由此,我们可以看到,由之前30次比较减少到15次,所以程序压力会少很多,程序复杂度也降低了。由上面结果可知:6位长度的数组需要排五轮,每轮次数减1,那如果由n个长度的数组,需要比较多少次呢?
第一轮:6-1
第二轮:6-2
第三轮:6-3
倒数第二轮:2
倒数第一轮:1
得出结果:(n-1)+(n-2)+...+2+1 = n(n-1)/2 =1/2n^2 -1/2n
是一个等差数列,按照时间复杂度规则,直接取最高阶项并去除常熟系数等到时间复杂度就是 O(n^2)了
到这,我们的冒泡排序就了解完了。
来源:https://mp.weixin.qq.com/s/QYxK6fwHBkw8ZsAkR5pVGA
猜你喜欢
- 前言 因为自己在做的一个小软件里面需要用到从A-Z排序的ListView,所以自然而然的想到了微信的联系人,我想要的就是那样的效果。本来没
- 1.editplus1.1 官方下载https://www.editplus.com/官方下载最新的64位2 .解压就可以使用2.1 vsc
- 自定义TypeHandler映射JSON类型为List1. 实体类这里只展示需要映射的字段,分别在所需映射的字段和实体类上添加注解。&nbs
- 该工具包含是封装了jedis,包含redis.properties和jedisPool,序列化使用的是protostuff,map类型操作使
- Hibernate是一个彻底的ORM(Object Relational Mapping,对象关系映射)开源框架。我们先看一下官方文档所给出
- 1 配置多数据源时,application.yml 的有关mybatis的配置是失效的,因为他不知道配置哪一个数据源2 applicatio
- 一、整体设计1、需求分析池化技术是计算机中的一种设计模式,内存池是常见的池化技术之一,它能够有效的提高内存的申请和释放效率以及内存碎片等问题
- strftime函数主要用于时间格式化,它的函数原型如下:size_t __cdecl strftime(char * __restrict
- [LeetCode] 9. Palindrome Number 验证回文数字Determine whether an integer is
- 一、简介ThreadPool相比Thread来说具备了很多优势,但是ThreadPool却又存在一些使用上的不方便。比如:Task支持线程的
- 一 应用规划: ※ 确定功能。 ※ 必须的界面及界面跳转的流程。
- 云计算、大数据地快速发展催生了不少热门的应用及工具。作为老牌语言Java,其生态圈也出来了一些有关云服务、监控、文档分享方面的工具。本文总结
- 之前学习 Java 的时候,感觉最难做的一件事情就是配置 jdk 的环境。那叫一个困难啊,Path, JAVA_HOME, CLASSPAT
- 1、引入依赖<dependency> <groupId>org.apache.pdfbox</gr
- 前言枚举在java里也算个老生长谈的内容了,每当遇到一组需要类举的数据时我们都会自然而然地使用枚举类型:public enum Color
- 一、打印直角三角形这个循环控制打印十行空格for (int x = 1; x <= 10; x++) {//因为要打印一个十行的直角三
- 一、输入输出流对象cout:标准输出流cerr:标准出凑 和cout(只是用于如果是错误时要输出的)cin :&nb
- 概述:App几乎都离不开与服务器的交互,本文主要讲解了flutter网络请求三种方式 flutter自带的HttpClient、 第三方库h
- 1、前言当提及如何终止一个线程时,部分读者通常立马想到的方法肯定是stop(),但是stop()方法并不被推荐使用(很多规范中是禁止使用的)
- 过年微信红包很火,最近有个项目也要做抢红包,于是写了个红包的生成算法。红包生成算法的需求预先生成所有的红包还是一个请求随机生成一个红包简单来