java实现冒泡排序算法和冒泡排序算法的优化

这段时间在学习数据结构与算法，看的书籍是程杰老师编著《大话数据结构》，确实收益匪浅。书中都是用C语言实现的，所以自己想用java去实现一下，废话不多说直接开始吧。

一、冒泡排序算法的思路：

    冒泡排序（Bubble Sort）是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

二、正宗冒泡算法java实现

/**
 * 冒泡排序算法
 * @author xiaoqiang
 *
 */
public class BubbleSort {
	
	public static void sort(int[] a){
		//1. 检查参数合法性
		if(a==null && a.length<=0){
			return;
		}
		//2. 两两比较相邻的关键字
		for(int i=0; i<a.length; i++){
			for(int j=a.length-2; j>=i; j--){//注意j是从后往前循环
				//3. 比较
				if(a[j]>a[j+1]){//若前者大于后者
					//4. 交换
					int temp = a[j];
					a[j] = a[j+1];
					a[j+1] = temp;
				}
			}
		}
	}
	
	public static void main(String[] args){
		int[] arr = {9,1,5,8,3,7,4,6,2};
		sort(arr);
		System.out.println(Arrays.toString(arr));
	}
}

结果：[1, 2, 3, 4, 5, 6, 7, 8, 9]

三、冒泡排序优化

      冒泡程序是否还可以优化呢？当然是可以的。假设我们待排序的序列为{2,1,3,4,5,6,7,8,9}，也就是说，除了第一和第二的关键字需要交换外，别的都已经是正常的顺序。按照上面的算法当i=0时，交换2和1，此时序列已经有序，但是上面的算法依然不依不饶地将i=1到8以及每个循环中的j循环都执行了一遍，尽管并没有交换数据，但是之后的大量比较还是大大地多余了。

    优化的思路：当没有任何数据交换时，就说明此序列已经有序，不要再继续后面的循环判断工作了。为了实现这个想法，需要改进上面的代码，增加一个标志位flag即可。

/**
 * 冒泡排序算法的优化
 * @author xiaoqiang
 *
 */
public class BubbleSort02 {
	
	public static void sort(int[] a){
		//1. 检查参数合法性
		if(a==null && a.length<=0){
			return;
		}
		//2. 优化的细节----设置一个标志位
		boolean flag = true;
		//3. 循环比较
		for(int i=0; i<a.length && flag; i++){
			flag = false;
			for(int j=a.length-2; j>=i; j--){//注意j是从后往前循环
				//4. 比较
				if(a[j]>a[j+1]){//若前者大于后者
					//5. 交换
					int temp = a[j];
					a[j]=a[j+1];
					a[j+1]=temp;
					flag = true;//有交换，则标志位置为true
				}
			}
		}
		
	}
	
	public static void main(String[] args){
		//int[] arr = {9,1,5,8,3,7,4,6,2};
		int[] arr = {2,1,3,4,5,6,7,8};
		sort(arr);
		System.out.println(Arrays.toString(arr));
	}
}

结果：[1, 2, 3, 4, 5, 6, 7, 8]

代码改动的关键就是在i变量的for循环中，增加了对flag是否为true的判断。经过这样的改进，你用Debug去调试一下，会发现冒泡排序在性能上有了一些提升，从而可以避免在已经有序的情况下继续无意义循环判断。