冒泡排序

冒泡排序原理：

比较相邻的元素，如果第一个比第二个大，就交换他们， 把大的放到后面再和后面的其他元素比较。

对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。每次执行完都会产生一个最大数。

每次比较完都会使需要比较的数少 1 ，一直进行到只剩最后一个,即 比较次数从n-1 一直到1。

n 个数需要进行的循环次数从n - 1次到1次。

静态实现图：

ps:这是一个循环的实现情况。

动态实现图：

代码实现：

importjava.util.Arrays;

​

publicclassBubbleSort{

publicstaticvoidmain(String[]args){

int[]arr={10,30,25,58,45,74};

inttemp=0;

​

for(inti=0;i<arr.length-1;i++){

//arr.length -1-i 是为了减少循环次数，已经排好序的数据不需要再次比较。

for(intj=0;j<arr.length-1-i;j++) {

if(arr[j]>arr[j+1]) {

temp=arr[j];

arr[j]=arr[j+1];

arr[j+1]=temp;

               }

           }

       }

System.out.println(Arrays.toString(arr));

​

   }

}

优缺点：

优点：代码简单，易于理解，空间复杂度低，属于稳定排序。

缺点：不管数据是否有序，都会进行固定次数的排序操作，效率不高，时间复杂度：

交换数据的代码执行次数 T(n) = 1+2+....+(n-1) = (1+n-1)*(n-1)/2 = (n^2 - n)/2

所以最坏情况：T(n) = O(f(n)) = O(n^2)

改进版：

importjava.util.Arrays;

​

publicclassBubbleSort{

publicstaticvoidmain(String[]args){

int[]arr={1,3,5,8,45,74};

inttemp=0;

booleanflag=true;

​

for(inti=0;i<arr.length-1;i++){

for(intj=0;j<arr.length-1-i;j++) {

if(arr[j]>arr[j+1]) {

temp=arr[j];

arr[j]=arr[j+1];

arr[j+1]=temp;

flag=false;

               }

           }

if(flag){

break;

}else{

flag=true;

           }

       }

System.out.println(Arrays.toString(arr));

   }

}

​

加入一个flag变量作为岗哨，探测有没有发生数据交换，如果某一次循环的时候没有发生数据交换，那么就说明数组已经是有序的了，就不再继续执行循环。