冒泡排序

 

        冒泡排序（Bubble Sort），是计算机科学领域的一种较简单的排序算法。

 

        它重复走访要排序的数列，一次比较两个元素。

 

        这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端，故名。

 

 

        如上图，为一趟冒泡排序的过程和结果，从中我们可以总结冒牌排序特点如下：

             1.所谓冒泡，就是“轻”（小）的元素浮上来的过程；

             2.每趟冒泡排序都有一个元素排好序，到其指定的位置上

              如上图，第一趟冒泡排序，最小的元素会排好序到顶端；

      第二趟冒泡排序，从下至上倒数第二个元素会排好序；

                      。。。。

              即如下图所示

      因此，其Java实现代码如下：

public class BubbleSort {
	
	public static void main(String args[]){
		int[] a = {1,5,0,7,2,4,4,8,9};
		sort(a);
	}
	
	public static void sort(int[] a){
		for(int i=0;i<a.length;i++){
			for(int j=0;j<a.length-1;j++){
				if(a[j]<a[j+1]){
					int tmp = a[j];
					a[j] = a[j+1];
					a[j+1] = tmp;
				}
			}
			System.out.print("第"+(i+1)+"趟排序：");
			print(a);
			System.out.println();
		}
		print(a);
	}

	private static void print(int[] a) {
		for(int i:a)
			System.out.print(i+" ");
		
	}

}

  由于第i趟排序后，length - i已排好序了，故优化后的代码如：

 

		for(int i=0;i<a.length;i++){
			for(int j=0;j<a.length-1-i;j++){
				if(a[j]<a[j+1]){
					int tmp = a[j];
					a[j] = a[j+1];
					a[j+1] = tmp;
				}
			}

            .......

 

       算法复杂度：

       通过以上程序，冒泡排序的两个for循环，可以知道冒泡排序总的平均时间复杂度为

 

       算法稳定性

      冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。