算法回顾之一：冒泡排序

数据结构与算法是计算机本科相关专业学生的必修课，我当年自然也是学过的，而且印象考试成绩还不错。

不过近期写了一个冒泡排序算法(不使用类库实现)，竟然出现了Bug，实在惭愧。

仔细想想工作这几年一直都是使用Java集合框架和类库，因此感觉还是有必要再重温一下。

-----------------------------------------------------------

冒泡排序

基本原理：

依次比较相邻的2个元素，把小数放在前面，把大数放在后面。遍历数组的每一个元素后，最大的数放在了最后。

再次从头比较相邻2个元素，把小数放在前面，把大数放在后面。直到比较到倒数第二个数(倒数第一个数已经是最大的了)。

依此类推，直到将数组中所有元素都排序一遍。

程序实现：

 

public static void bubbleSort(){
	    int[] array=new int[]{9,8,7,6,5,4,3,2,1};
	    boolean noSwapFlag=true;//未发生交换标识
	    int temp=0;//临时变量,用于排序时的数据交换.
		for (int i=0;i<array.length-1;i++) {//数组中的已排序元素.
			noSwapFlag=true;//每轮排序前重置未交换标识
			for (int j=0;j<array.length-i-1;j++){//每一轮排序需要遍历的元素个数.
				//升序排序:如果前面的元素大于后面的元素,交换位置(小于为降序).
				if (array[j] > array[j+1]){
					temp=array[j];
					array[j]=array[j+1];
					array[j+1]=temp;
					//如果有交换时,未发生交换的标识置为false.
					noSwapFlag=false;
				}
			}
			System.out.println("Sort"+i+":"+Arrays.toString(array));
			if(noSwapFlag){//该轮排序中没有任何元素发生交换,代表已达到所需顺序.
				System.out.println("No swap!");
				break;
			}
		}
		System.out.println("Sort Result:"+Arrays.toString(array));
	}

 

性能分析：

1、如果目标序列为升序，而数组本身也是升序，那么只需要1次排序即可排出。排序次数为n-1次。

2、如果目标序列为升序，而数组全部元素逆序，那么需要n*(n-1)/2次比较和移动。

因此，冒泡排序的总时间复杂度为O(n^2).

 

空间复杂度：1。

稳定性：稳定的排序。