算法:简单排序1-冒泡排序

2018-03-17

简单排序1-冒泡排序

"排序-bubble"

思路

1.每次从左开始两个紧邻元素比较大小，如果大就交换位置到右边。
2.得到大数并且交换到右边位置后，它继续和它的右边一个数比较大小重复1步骤，这样重复下来第一轮最后一个位置就是最大数。
3.下次排序时重复1,2步骤一直到上一次排好顺序的前一个位置上。

SortUtils.java 主要完成换位和打印任务，在之后的简单排序中都会用此工具类


public class SortUtils {
	/**
	 * @param array=数组
	 * @param index=当前位置
	 * @param next=下一个位置
	 */
	public static void swap(int[] array,int index,int next){
		int tmp=array[index];
		array[index]=array[next];
		array[next]=tmp;
	}
	
	/**
	 * @param array=要打印的数组
	 */
	public static void display(int[] array){
		for(int i=0;i<array.length;i++){
			System.out.print(" "+array[i]);
		}
	}
}

Bubble.java 具体实现


public class Bubble {
	public static int array[]={5,6,3};
	
	public static void main(String[] args) {
		for (int out = array.length-1; out > 0; out-- ) {//1
			
			for (int in = 0; in < out; in++ ) {//2
			
				if ( array[in] > array[in+1] ) {//3
				
					SortUtils.swap(array, in, in+1);//交换位置
					
				}
			}
		}
		SortUtils.display(array);//打印排序好的数据
	}
}

输出：3 5 6

说明

1.主要负责两个功能。1:外层计数器总共要进行几次的交换位置，2:内层循环时比大小的停止位置
2.每次从0位置开始和下一个位置比对大小，一直遇到out的停止排序的位置为止
3.如果这里是> 那么最终结果是3 5 6，如果这里是< 最终结果是6 5 3

简单排序1-冒泡排序优化版

在相对已经有序的数组中冒泡排序缺点是最后几个位置已经是固定的顺序时每次还会去消耗时间去比较大小。

比如：5,6,3,1,2,0,7,8,9
本身已经没有比较再去比较7,8,9但是还会在前三轮比较

优化思路

1.增加一个标识符来判断内循环时有无交换数据，如果内循环一次交换都没有发生就说明已经是有序数据，不用在消耗时间去做不必要地比较。
2.记录上一次交换索引的位置(lastExchangeIndex)，每次数据比较只交换到lastExchangeIndex索引上，不用再去比较右边已经有序的数据。

BubbleOptimize.java 具体实现


public class BubbleOptimize {
	public static int array[]={5,6,3,1,2,0,7,8,9};
	
	public static void main(String[] args) {
		int lastExchangeIndex=array.length-1;		//1
		int sortLength=array.length-1;	
		
		for (int out = 0; out < array.length; out++) {		
			
			boolean isSorted=true;			//2
			
			for (int in = 0; in < sortLength; in++) {		//3
				
				if ( array[in] > array[in+1] ) {			
				
					SortUtils.swap(array, in, in+1);//交换位置
					isSorted=false;		//4
					lastExchangeIndex=in;		//5
				}
			}
			sortLength=lastExchangeIndex;		//6
			if(isSorted){		//7
				break;
			}
		}
		SortUtils.display(array);//打印排序好的数据
	}
}