欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

关于Java冒泡排序算法的优化

程序员文章站 2022-04-12 22:42:34
冒泡排序的优化最基础的冒泡排序算法优化算法(一).关于减少每次遍历数组的次数利用闭合原则进行提前中断遍历(最终版)结语最基础的冒泡排序算法// Java冒泡排序算法(最基础版本)import java.util.Arrays;//研究冒泡排序public class BubbleSort {public static void main(String[] args) {//arrays自带的排序方法int[] a = {3,1,4,5,6};/*Arrays.sort(a)...

最基础的冒泡排序算法

// Java冒泡排序算法(最基础版本)
import java.util.Arrays;

//研究冒泡排序
public class BubbleSort {
	public static void main(String[] args) {
		//arrays自带的排序方法
		int[] a = {3,1,4,5,6};
		/*Arrays.sort(a);
		System.out.println(Arrays.toString(a));*/
		int inner = 0;
		int outner = 0;
		
		for (int j = 0; j < a.length; j++) {
			for (int i = 0; i < a.length-1; i++) {
				if (a[i]>a[i+1]) {
					int temp = a[i];
					a[i] = a[i+1];
					a[i+1] = temp;
				}
				System.out.println("当前内循环的次数:" + (++inner));
			}
			System.out.println("当前外循环的次数为:" + (++outner)+"当前数组的输出为:"+Arrays.toString(a));
		}
		
		System.out.println(Arrays.toString(a));
		
	}
}

算法输出如下:
关于Java冒泡排序算法的优化

这是大多数人第一次写出来的冒泡排序算法(为了下面更加直观的表现出来优化算法的好坏,直接在代码里面记录一下内外循环的次数),每一个学习Java的未来程序员,可能都会经历这个最基础的算法,而你想没想过为这个算法做一些优化呢?
下面我总结出来的算法的两种优化:

优化算法(一).关于减少每次遍历数组的次数

// 第一次优化
import java.util.Arrays;

//研究冒泡排序
public class BubbleSort {
	public static void main(String[] args) {
		//arrays自带的排序方法
		int[] a = {3,1,4,5,6};
		/*Arrays.sort(a);
		System.out.println(Arrays.toString(a));*/
		int inner = 0;
		int outner = 0;
		
		for (int j = 0; j < a.length-1; j++) {
			for (int i = 0; i < a.length-1-j; i++) {
				if (a[i]>a[i+1]) {
					int temp = a[i];
					a[i] = a[i+1];
					a[i+1] = temp;
				}
				System.out.println("当前内循环的次数:" + (++inner));
			}
			
			System.out.println("当前外循环的次数为:" + (++outner)+"当前数组的输出为:"+Arrays.toString(a));
		}
		
		System.out.println(Arrays.toString(a));
		
	}
}

第一次优化后的输出如下:
关于Java冒泡排序算法的优化
整整减少了一半的内循环的次数!!!
通过每次内循环得到一个最大值放到数组的结尾,第二次遍历直接跳过这个数.得到了第一次的优化!

利用开闭原则进行提前中断遍历(最终版)

// 利用闭合原则对算法的二次优化
import java.util.Arrays;

//研究冒泡排序
public class BubbleSort {
	public static void main(String[] args) {
		//arrays自带的排序方法
		int[] a = {3,1,4,5,6};
		/*Arrays.sort(a);
		System.out.println(Arrays.toString(a));*/
		int inner = 0;
		int outner = 0;
		
		for (int j = 0; j < a.length-1; j++) {
			boolean flag = true;
			for (int i = 0; i < a.length-1-j; i++) {
				if (a[i]>a[i+1]) {
					flag = false;
					int temp = a[i];
					a[i] = a[i+1];
					a[i+1] = temp;
				}
				System.out.println("当前内循环的次数:" + (++inner));
			}
			
			System.out.println("当前外循环的次数为:" + (++outner)+"当前数组的输出为:"+Arrays.toString(a));
			if (flag) {
				System.out.println("提前就结束啦!");
				break;
			}
		}
		
		System.out.println(Arrays.toString(a));
		
	}
}

算法的输出如下:
关于Java冒泡排序算法的优化
又一次的减少了遍历的次数!!!
通过在外循环定义了一个Boolean类型的变量flag,如果内循环的if语句不执行的话,说明该次循环无元素移动,即此时数组已经排序完成,无须再进行排序.

结语

在我们初学Java的时候,不必要为了快而学习,要在学习了每个知识点之后对其进行较深的挖掘,可能你会找到其他不可思议的东西!!!

本文地址:https://blog.csdn.net/xiaole060901/article/details/107574678

相关标签: 算法优化