java实现冒泡算法及三种常见优化

2021年9月6日 9点热度 0条评论 来源: 东北溜达滑

冒泡算法

冒泡排序顾名思义是通过两两比较,将数据当中最大的那个“浮”到数列的顶端,通过这种不断的上“浮”,最终达到有序的排序算法。冒泡排序因其简单稳定而受到大家的欢迎,也是初学者最容易掌握的一种排序算法。
稳定性:冒泡排序就是把大的元素往后调(或者小的元素往前调)。比较的是相邻的两个元素,交换也只发生在这两个元素之间。所以,如果两个元素相等,是不会交换的;即使两个元素相等却没有相邻,那么通过前面的两两交换把他们相邻起来,这时候比较的相等也是不会交换的,因此相同元素的前后顺序不会改变,所以冒泡排序是一种稳定排序算法。
时间复杂度:假设数据有n条,那么需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(i表示循环第几次,1≤i≤n-1),在这种情况下,比较次数为n(n-1)/2,即O(n²)。所以时间复杂度为O(n²)
冒泡排序优点:比较简单,空间复杂度较低,是稳定的算法。
冒泡排序缺点:因其每次只能移动相邻两个数据,所以时间复杂度高,效率低。当处理大量数据排序时,效率低下这一特点非常明显。

实现代码

实现原理:采用双重for循环来完成算法。外层循环负责控制“冒泡”的数据个数,也就是说要冒泡n-1条数据,才能结束排序算法。内层循环负责控制具体的“冒泡”过程,也就是将剩下的数据两两比较(注意:这里的两两比较指得是相邻的数据两两比较),找出最大的,因此一共要比较总的数据条数减去已经排好序的数据条数次。明白原理后,代码实现起来就简单的多了,下面是java实现代码:

private static int[] bubbleSort(int[] date){
		int length = date.length;//防止每次循环重复计算数组长度
		for (int i = 0; i < length-1; i++) {//控制冒泡次数
			for (int j = 0; j < length-i-1; j++) {//具体的数据冒泡过程
				if (date[j] > date[j+1]) {//如果相邻的两条数据,前面的比后面的大,就交换顺序。
					int temp = date[j];
					date[j] = date[j+1];
					date[j+1] = temp;
				}
			}
		}
		return date;
	}

优化一

让我们来设想这样一种情况,那就是数据已经有序,并且是最终的正序。就像是已经用冒泡排好序了,又来让你的算法排一遍,我们还要像之前那样的挨个比较么?像1、2、3、4、5、6、7、8、9或者9、1、2、3、4、5、6、7、8}(冒泡第一条数据后,数据就已经有序)这样的数据我们怎么处理。换句话我们思考什么情况下我们认为数据已经有序了。有序了就意味着我们不需要交换,不需要将大的数据向后调,所以当我们发现内层循环比较下来一次也没有交换,那么我们是不是就可以认为数据已经有序了?如果是无序的,那么它一定比它后面的数大,冒泡时一定会进行交换。所以没有交换我们就可以认为数据有序了。明白了这一点,优化就简单了。直接上代码。

private static int[] bubbleSort(int[] date){
		int length = date.length;
		boolean flag = true;//设立一个标志,判断当前数据是否有序,默认为有序
		for (int i = 0; i < length-1; i++) {
			for (int j = 0; j < length-i-1; j++) {
				if (date[j] > date[j+1]) {
					int temp = date[j];
					date[j] = date[j+1];
					date[j+1] = temp;
					flag = false;//如果发生交换就意味着当前数据还无序。
				}
			}
			if (flag) {//判断是否有序。如果数据有序了,直接返回
				return date;
			}
			flag = true;//如果还处于无序状态,记得将标志复原,进行下一轮冒泡之后的判断使用。
		}
		return date;
	}

优化二

优化了一个问题之后,又发现了新的问题,就是部分有序。像这样3、2、1、4、5、6、7、8、9。当我们进行一次冒泡后9移到最后的位置,同时4、5、6、7、8、9这部分数据已经有序,并且都是每一次冒泡的“泡泡”。当一次冒泡,3交换到1的位置后,发现之后的数据顺序不变,那么当再次冒泡2时,2还需要跟456789比较么。显然不需要。针对这一问题,我们加入了一个标志记录最后交换的位置,下一次冒泡时,这个标志之后的数据就不需要排序了。代码如下:

private static int[] bubbleSort(int[] date){
		int length = date.length;
		boolean flag = true;
		int lastLocation = length-1;//标志,用于记录最后交换的位置。初始值是最后一位。
		for (int i = 0; i < length-1; i++) {
			int nowLocation = 0;//临时标志,最后一次交换之前还有多次交换,这些并不是我们想要的。我们通过最后的覆盖之前的这种方式得到最后的标志位。
			for (int j = 0; j < lastLocation; j++) {//标志位之后的数据已经有序,之前是固定的length-i-1,现在是可变的不确定的。
				if (date[j] > date[j+1]) {
					int temp = date[j];
					date[j] = date[j+1];
					date[j+1] = temp;
					flag = false;
					nowLocation = j;//交换后将位置告诉临时标志
				}
			}
			lastLocation = nowLocation;//临时标志将最后的位置告诉标志位
			if (flag) {
				return date;
			}
			flag = true;
		}
		return date;
	}

优化三

终极优化则针对这样一种情况1、2、3、4、5、6、7、8、9、0。如果没有优化,我们需要一次一次冒泡,知道将最小的0一步一挪到前面。显然这样效率极低。这里我们采用双相冒泡的方法。从前向后冒泡后,再从后向前冒泡,将最小的移到最前面。代码如下:

private static int[] bubbleSort(int[] date){
		int length = date.length;
		boolean flag = true;
		int newLocation = 0;//记录前面最小的已经有序的数据个数
		int lastLocation = length-1;
		for (int i = 0; i < length-1; i++) {
			int nowLocation = 0;
			for (int j = 0; j < lastLocation; j++) {
				if (date[j] > date[j+1]) {
					int temp = date[j];
					date[j] = date[j+1];
					date[j+1] = temp;
					flag = false;
					nowLocation = j;
				}
			}
			lastLocation = nowLocation;
			if (flag) {
				return date;
			}
			flag = true;
			for (int j = lastLocation; j > newLocation; j--){//从后向前冒泡,找出最小的。原理同上面代码。
				int tmp = date[j];
				date[j] = date[j - 1];
				date[j - 1] = tmp;
				flag = false;
			}
			newLocation++;
			if (flag){
				return date;
			}
			flag = true;
		}
		return date;
	}

以上就是本次冒泡排序及优化的全部内容,希望对大家有所帮助,有什么错误也希望大家能够指正。

    原文作者:东北溜达滑
    原文地址: https://blog.csdn.net/qq_39188747/article/details/88266386
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。