算法之冒泡排序

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

 

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

 

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

 

 

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

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

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

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

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

                      。。。。

              即如下图所示

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

Java代码 

1. public class BubbleSort {  
2.       
3.     public static void main(String args[]){  
4.         int[] a = {1,5,0,7,2,4,4,8,9};  
5.         sort(a);  
6.     }  
7.       
8.     public static void sort(int[] a){  
9.         for(int i=0;i<a.length;i++){  
10.             for(int j=0;j<a.length-1;j++){  
11.                 if(a[j]<a[j+1]){  
12.                     int tmp = a[j];  
13.                     a[j] = a[j+1];  
14.                     a[j+1] = tmp;  
15.                 }  
16.             }  
17.             System.out.print("第"+(i+1)+"趟排序：");  
18.             print(a);  
19.             System.out.println();  
20.         }  
21.         print(a);  
22.     }  
23.   
24.     private static void print(int[] a) {  
25.         for(int i:a)  
26.             System.out.print(i+" ");  
27.           
28.     }  
29.   
30. }  

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

 

Java代码 

1. for(int i=0;i<a.length;i++){  
2.     for(int j=0;j<a.length-1-i;j++){  
3.         if(a[j]<a[j+1]){  
4.             int tmp = a[j];  
5.             a[j] = a[j+1];  
6.             a[j+1] = tmp;  
7.         }  
8.     }  
9.   
10.           .......  

 

       算法复杂度：

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

 

       算法稳定性

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

优秀微信公众号推荐：Java和Android大牛频道群，共同交流和学习！

扫描下方的二维码即可快速关注！！！

大家也可以加我们运营的微信：AMEPRE 或者 QQ:124526720

或者加入官方QQ群：558902989