算法面经--冒泡排序

冒泡排序

一、冒泡排序原理

通过对待排序序列从前向后（从下标较小的元素开始）,依次比较 相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。

优化：

因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在 排序过程中设置一个标志 flag 判断元素是否进行过交换。从而减少不必要的比较。

二 、图解

冒泡1.jpg

小结上面的图解过程: (1) 一共进行 数组的大小-1 次 大的循环 (2)每一趟排序的次数在逐渐的减少 (3) 如果我们发现在某趟排序中，没有发生一次交换， 可以提前结束冒泡排序。这个就是优化

三、代码实现

package sort;
 ​
 import java.text.SimpleDateFormat;
 import java.util.Date;
 ​
 public class BubbleSort {
 ​
  public static void main(String[] args) {
  // TODO Auto-generated method stub
  //冒泡排序时间复杂度为O(n^2)
  //测试；  创建80000个数的随机数组
  int arr[] = new int[80000];
  for(int i=0;i<80000;i++){
  arr[i] = (int)(Math.random()*80000);//生成 一个[0,800000)的数
  }
  Date date1 = new Date();
  SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd             HH:mm:ss");
  String date1Str = simpleDateFormat.format(date1);
  System.out.println("排序前的时间为="+date1Str);

  //执行冒泡排序
  bubbleSort(arr);
 ​
  //排序后的时间
  Date date2 = new Date();
  String date2Str = simpleDateFormat.format(date2);
  System.out.println("排序前的时间为="+date2Str);
  }

  //核心代码
  //将冒泡排序封装为一个方法，优化：设置一个标志变量，(已经有序的)未交换的就不再进行
  public static void bubbleSort(int[] arr){
  int temp =0;
  boolean flag = false; //表示变量，表示是否进行过交换
  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]){  //如果后面的数比前面的数大，则交换
  flag = true;  //表示已发生交换
  temp = arr[j];
  arr[j] = arr[j+1];
  arr[j+1] = temp;
  } //if

  }//for
  if(!flag){ //在一趟排序中，一次交换都没有发生过，
  break;
  }else{
  flag = false; //重置flag,进行下次判断
  }
  }//for
  }
 }
 ​</pre>