冒泡排序算法

冒泡排序算法

原理

  • 比较相邻的两个数,将值较大的元素放在最前面,由于较小的数字像泡泡一样浮上来,因此取名为冒泡

从后向前比较(小的数上浮)

  • 第一趟:从数组的最后一个元素和倒数第二个元素比较,小的上浮(交换),之后倒数第二个和倒数第三个数字比较,小的上浮(交换),直至第二个数字和第一个数字比较,小的上浮,那么经过一趟排序之后,此时的第一个元素就是最小的
  • 第二趟: 经过第一趟之后,第一个就是最小的数字,因此第二趟就不比较第一个和第二个数字了。从最后一个元素和倒数第二个元素比较,小的上浮,直至第三个元素和第二个元素比较,小的上浮,那么此时的第二个就是仅次于第一个的小的元素
  • 第三趟:和前面一样的比较,不过就是不用比较第二个和第三个元素了,因为经过第一趟和第二趟之后,数组中的第一个和第二个元素已经是最小的两个了。经过第三趟比较,第三个元素是仅次于第一个和第二个元素小的元素
  • 第四趟第五趟………………………………
  • 从上面我们可以得出,假设数组中有n个元素,那么需要经过n-1趟排序才可以完成全部的比较,最后一趟可以比较出倒数第一个和倒数第二个元素的大小

实现

/**
 * 冒泡排序算法之从后向前比较排序
 * @param a  需要排序的数组
 */
public static void bubbleSort(int[] a) {
	// 外层循环控制排序的趟数,总共需要n-1趟排序
	for (int i = 0; i < a.length - 1; i++) {
		//内层循环控制的是每一趟排序需要比较的次数,j=a.length-1 表示从最后一个元素开始比较,j>i是用于控制每趟之后比较的次数
		//比如,经过第一趟之后,那么第一个元素肯定是最小的,因此就不需要将第二个元素和其比较了,第二趟之后第二个元素第一个和第二个元素就是最小的,都需要比较了
		for(int j=a.length-1;j>i;j--){
			//比较大小,较小的就上浮
			if(a[j]<a[j-1]){
				//交换位置
				int temp=a[j];
				a[j]=a[j-1];
				a[j-1]=temp;
			}
		}
	}

}

从前向后比较(大的数字下沉)

  • 第一趟:从第一个元素和第二个元素进行比较,较大的下沉(交换),然后第二个元素和第三个元素比较,较大的下沉,直至倒数第二个和最后一个比较,大的下沉,那么此时的最后一个数就是最大的
  • 第二趟: 从第一个元素和第二个元素进行比较,较大的下沉,然后第二个和第三个比较,直至倒数第三个和倒数第二个比较,大的下沉,那么此时的倒数第二个数是仅次于最后一个数小的元素。因为经过第一趟之后,最后一个元素已经是最大的,因此不需要比较了
  • 第三趟: 经过第二趟之后,倒数第二个仅次于最后一个元素小的元素了,因此在第三趟中只需要比较到倒数第四个和倒数第三个元素的大小即可,大的下沉,那么此时的倒数第三个元素又是前面所有元素中最大的,因此在第四趟排序就不需要和其比较了。
  • 第四趟……………………………………………………
  • 从上面我们可以得出结论: 假设有n个元素,那么总共需要进行n-1趟排序

实现

/**
	 * 冒泡排序算法之从前向后比较排序
	 * @param a  需要排序的数组
	 */
	public static void bubbleSort(int[] a) {
		// 外层循环控制排序的趟数,总共需要n-1趟排序
		for (int i = 0; i < a.length - 1; i++) {
			//内层循环控制每趟循环比较的次数,j=0表示从第一个元素开始进行比较,j<a.length-1-i用来控制每趟循环之后不用再比较的元素索引
			//比如第一趟循环之后,最后一个元素就是最大的,那么在第二趟循环就不需要和其比较了
			for (int j = 0; j < a.length - 1 - i; j++) {
				//相邻的元素进行比较,如果前面的大于后面的就交换位置
				if (a[j] > a[j + 1]) {
					int temp = a[j];
					a[j] = a[j + 1];
					a[j + 1] = temp;
				}
			}
		}

	} 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java技术分享圈

杨老师课堂_Java教程第四篇之数组运用

今天主要是讲解以下知识点: 1、流程控制语句switch 2、数组 3、王者荣耀英雄随机出战案例

914
来自专栏WindCoder

Java漫谈-深拷贝与浅拷贝

2、运用反射手段创建对象,调用java.lang.Class 或者 java.lang.reflect.Constructor 类的newInstance()实...

1.7K3
来自专栏闻道于事

JavaScript数字例子,二分法,冒泡排序

先看一下两个例子: 十个成绩,求总分,最高分,最低分 //输入10个成绩,求总分,最高,最低 var arr=new Array(67,45,5...

3315
来自专栏Java帮帮-微信公众号-技术文章全总结

第六天 知识点练习与回顾【悟空教程】

1696
来自专栏desperate633

五分钟搞懂hashCode()和equals()方法的原理常见的误区错误出现的原因

这两个方法最开发者来说是十分重要的,必须清楚的理解,但实际上,甚至很多经验丰富的Java开发者有时候也没有真正搞清楚这两个方法的使用和原理。当我们自定义了对象,...

895
来自专栏大数据挖掘DT机器学习

正则表达式总结

一、元字符 . 匹配除换行符以外的任意字符 \w 匹配单词(字母、数字、下划线、汉字) \s 匹配任意空白符(空格、制表符tab、换行符、中文全角空格) \d...

3625
来自专栏Bingo的深度学习杂货店

Q190 Reverse Bits

Reverse bits of a given 32 bits unsigned integer. For example: given input 43261...

3415
来自专栏xingoo, 一个梦想做发明家的程序员

Java程序员的日常—— Arrays工具类的使用

这个类在日常的开发中,还是非常常用的。今天就总结一下Arrays工具类的常用方法。最常用的就是asList,sort,toStream,equals,copy...

1897
来自专栏黑泽君的专栏

调用Thread类的方法:public final String getName() 为什么得到的线程对象的名称默认是:Thread-0、Thread-1、Thread-2、...呢?

调用Thread类的方法:public final String getName() 为什么得到的线程对象的名称默认是:Thread-0、Thread-1、Th...

1232
来自专栏机器学习入门

挑战程序竞赛系列(72):4.7高度数组(2)

挑战程序竞赛系列(72):4.7高度数组(2) 传送门:POJ 3415: Common Substrings 题意: 公共子串:统计A和B长度不小于K的公共...

19110

扫码关注云+社区

领取腾讯云代金券