以前接触过一些排序方法，对冒泡排序也有一定的了解。但是只是为了记住而了解。此次重新学习了冒泡排序，发现自己当初学习的只是最简单的冒泡排序算法。急需进一步的优化。在此，我将自己最新学到的优化方法说出来和大家一起分享，也为了自己将来的巩固学习。

          先来看最简单的冒泡：

class Bubble_2{	public void bubble_2(int a[])	{		int temp;		for(int i=0;i
    
     a[j])				{					temp=a[j];					a[j]=a[i];					a[i]=temp;				}			}		}			}	}
    

            

  此处代码应该很好理解，如图1:所示。这也是初学者先学习的一种排序方法。但是此算法的效率非常低下，因为先排好序的关键字对后边没什么帮助。还有可能将关键字较小者放在靠后的位置。急需改进。

          优化代码如下：

//优化，从尾部开始，将最小值向前移动class Bubble_3{	public void bubble_3(int a[])	{		int temp;		//外层循环的i表示数组前面已经有序的个数。		for(int i=0;i
    
     i;j--)			{				if(a[j]
    

        

如图2所示：此算法的好处在于，排序时候从后边开始，将较小者往前边移动。这样较小者会不断往前移动。解决了第一个算法，可能将较小者移到后边的情况，提高了算法效率。在上十万条数据的排序过程中，这种差异将会体现出来。

             

如此看来，冒泡排序算法似乎已经够完美了？然而还可以进一步的优化。为什么呢？

        因为如果待排序列为{2,1,3,4,5,6,7,8,9} 也就是说，除了第一个和第二个关键字需要交换外，别的已经有序。按照第二种算法，算法将会对每个循环中的j都会执行一遍，即使只有比较数据，并没有交换数据。这个动作是大大多余的，所以可以改进。如图3所示：

      

        算法改进可以使用最常用的办法，那就是设置一个标记变量flag，当循环中没有交换数据时，算法将停止循环。执行结束。代码如下：

public static void bubble_4(int a[])  	     {  	         int temp;  	        boolean flag=true;  	         //外层循环的i表示数组前面已经有序的个数。  	         for(int i=0;i
    
     i;j--)  	            {  	                  	                if(a[j]
    

 

        经过这样的改进，算法执行效率有了一定的提高，可以避免在已经有序的情况下的无意义的循环判断。

分析两种冒泡排序，代码如下：

 

排序1为从前面将数据挨个移到最后面。内层循环中，j<a.length-1-i是因为： -i是指数组中后边的i为已经有序，减去i可以减少比较次数。当然不减去i也可以搞定。

//冒泡排序1 public static void bubble(int[] a) {  boolean flag=true;  //外层循环的i表示数组后面已经有序的个数。  for(int i=0;i
    
     a[j+1])    {     int temp=a[j];     a[j]=a[j+1];     a[j+1]=temp;     flag=true;    }   }  }  for(int x:a)  {   System.out.println(x);  }  }
    

 

排序2将数据从后边挨个移到最前面。内层循环中，j>i是因为：此处j>i而不是j>0可以减少比较次数，因为前面的i位已经有序。当然j>0也可以排序。

//冒泡排序2  public static void bubble_4(int a[])        {            int temp;           boolean flag=true;            //外层循环的i表示数组前面已经有序的个数。            for(int i=0;i
    
     i;j--)                  {                                      if(a[j]