冒泡排序—冒泡排序算法优化

常用的排序算法主要包括：

1、插入排序  直接插入排序 希尔排序
2、交换排序  冒泡排序  快速排序
3、选择排序   简单选择排序  堆排序  快速排序    
4、归并排序

其中，冒泡排序算是最简单的一种排序算法

• 排序思想:

  对一组数字进行从小到大或者从大到小的进行排序。
  它是通过让相邻的两个元素进行比较，大的元素向下沉，小的元素向上冒
  arr[0]与arr[1]进行比较，如果前者大于后者，则交换位置
  然后arr[1]与arr[2]进行比较，以此类推。当进行到n-1轮后，排序完成。
  
  

• 代码实现：

  public class Bubble {
      public static void main(String[] args) {
          int arr[]= {29,45,64,12,98,6};
          int temp=0;    
          for(int i=0;i<arr.length-1;i++) {
              for(int j=0;j<arr.length-1-i;j++) {
                  if(arr[j]>arr[j+1]) {
                       temp=arr[j+1];
                       arr[j+1]=arr[j];
                       arr[j]=temp;
                   }
               }
               System.out.println("第["+(i+1)+"]轮，排序结果:"+Arrays.toString(arr));
           }
     }
  }

• 排序结果：
  第[1]轮，排序结果:[29, 45, 12, 64, 6, 98]
  第[2]轮，排序结果:[29, 12, 45, 6, 64, 98]
  第[3]轮，排序结果:[12, 29, 6, 45, 64, 98]
  第[4]轮，排序结果:[12, 6, 29, 45, 64, 98]
  第[5]轮，排序结果:[6, 12, 29, 45, 64, 98]

通过分析我们可以得到冒泡排序的时间复杂度为O(n^2)，假如现在存在这种情况，存在一个数组，现在已经是有序的数据，如果使用冒泡排序同样需要O(n^2)的时间复杂度，这时我们需要对冒泡排序进行优化。

• 优化思路：
  假如在第1轮比较当中，发现所有的元素都没有进行交换，则说明此原数据就是有序的，不需要再进行排序。

• 优化代码：

  public class BubbleOptimization {
      public static void main(String[] args) {
          int arr[]= {10,23,32,66,45,88};
  		int temp=0;
  		int flag=0;
  		for(int i=0;i<arr.length-1;i++) {
              flag=0;
  			for(int j=0;j<arr.length-1-i;j++) {
                  if(arr[j]>arr[j+1]) {
                      temp=arr[j+1];
  					arr[j+1]=arr[j];
  					arr[j]=temp;
  					//如果有交换的行为,则flag=1
  					flag=1;
  				}
  			}
  			//说明上面 内for循环中，没有交换任何元素。
  			if(flag==0) {
  				   break;
  			}
  			System.out.println("第["+(i+1)+"]轮，排序结果:"+Arrays.toString(arr));
  		}
  	}
  }

• 排序结果：
  第[1]轮，排序结果:[10, 23, 32, 45, 66, 88]