算法研究系列---冒泡排序

为了毕业面试需要，计划好好的研究一遍算法，以博客的形式记录下来，同时也为了加深自己的理解.

今天要记录的是：冒泡排序

 

 

冒泡排序是一种典型的交换排序算法.同时也是几大排序算法中比较简单的一个.

 

算法思想：通过无序区中相邻记录关键字间的比较和位置的交换，，是关键字较小的记录如同气泡一样上浮，整个算法从记录的最下面开始，对每两个相邻的关键字进行比较，并将关键字小的记录置换到关键字较大的记录之上，是的一趟排序之后，关键字最小的记录上浮到了记录的最上端。以此类推，每次比较都会将本次比较范围的记录中最小的记录置换到最上端，这样当最后一趟完成时，所有记录就都是有序的了...

 

java代码：

 

public class BubbleSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		int[] a = new int[]{7,5,3,4,6,1,10,9,8,2}; 
		a = bubbleSort(a, 10);
		for(int i = 0; i<10; i++) {
			System.out.println(a[i]);
		}
		
	}
	
	public static int[] bubbleSort(int[]a, int n) {
		int i, j;
		int change = 0; 
		int tmp=-1;
		for(i=0; i<n-1; i++) {
			 change= 0;
			 for(j=n-1; j>i; j--) {
				 if(a[j] < a[j-1]) {
					tmp = a[j-1];
					a[j-1] = a[j];
					a[j] = tmp;
					change = 1;
				 }
			 }
			 if(change == 0) {
				 break;
			 }
		}
		return a;
	}

}

 

 

这里用到了一个小技巧,即代码中的变量：change，因为如果在一趟排序中没有发生位置交换，则表明当前的序列已经是有序的了,后面的比较操作就不需要再进行下去,应当跳出循环，所以在这里用change变量来标识在一趟比较中是否发生的置换操作，若没有，则跳出循环.