冒泡算法

算法"/>

冒泡算法

em~冒泡的原理就不重复了，这个百度下就清楚啦。

首先写一版大家都会的冒泡排序代码：

当我们现在需要对数组int array[] = new int[]{2,3,1,323,32,233,23,122,13,4254,232,435,242,453,53};进行排序时，我们最简单的方法就是通过两层for循环遍历判断来进行排序，此时O（n^2) 

public class Bubble {int array[] = new int[]{2,3,1,323,32,233,23,122,13,4254,232,435,242,453,53};public Bubble() {for(int i = 0 ; i < array.length ; i++) {for(int j = 0 ; j < array.length - i - 1 ; j++) {if(array[j]>array[j+1]) {int temp = array[j];array[j] = array[j+1];array[j+1] = temp ;}}}for(int a : array) {System.out.print(a+",");}}public static void main(String[] args) {new Bubble();}
}

而平时我们排序的数组有可能是这样的：int array[] = new int[]{11,1,2,3,4,5,6}; 此时除了11以外的元素已经排好序了。那么对于上面的代码当i=0的时候11已经沉底，数组array[]={1,2,3,4,5,6,11}此时数组已经完成了排序。那么当i>=1的时候array[j]>array[j+1]条件将不会成立。我们可以认为当i=n，对于所有的j ，array[j]>array[j+1]都不成立，则表示数组已经排好序不需要有任何的元素移动了。此时就可以跳出判断。如下代码中O=n，就大大优化了算法的时间

public class Bubble {int array[] = new int[]{11,1,2,3,4,5,6};public Bubble() {for(int i = 0 ; i < array.length ; i++) {boolean isChange = false ;for(int j = 0 ; j < array.length - i - 1 ; j++) {if(array[j]>array[j+1]) {int temp = array[j];array[j] = array[j+1];array[j+1] = temp ;isChange = true ;}}if(!isChange) {System.out.println(i);break ;}}for(int a : array) {System.out.print(a+",");}}public static void main(String[] args) {new Bubble();}
}

然鹅也有这样一种数组int[] array = new int[]{11,12,13,14,15,1}; 前面是已经排好序的，最后一个元素是最小的。按照冒泡排序的规则，第一次排序后array={11,12,13,14,1,15} ， 第二次为array={11,12,13,1,14,15} ， 第三次为array={11,12,1,13,14,15}，第四次为array={11,1,12,13,14,15}，最后一次为array={1,11,12,13,14,15}，需要遍历到最后一次才能得到结果。对于这样的情况也有一种优化方式。em，业界上管这算法叫做鸡尾酒算法，鸡尾酒算法的原理跟冒泡差不多，只不过是鸡尾酒算法第一轮从左到右冒泡，第二轮从右到左冒泡，第三轮从左到右冒泡...依次循环到n次。

代码如下：

public class Cocktail {int array[] = new int[]{11,12,13,14,1};public void doIt() {for(int i = 0 ; i < array.length ; i++) {boolean isChange = false ;if(i%2==0) {for(int j = 0 ; j < array.length -i- 1 ; j++) {if(array[j]> array[j+1]) {int temp = array[j];array[j] = array[j+1];array[j+1] = temp ;isChange = true ;}}}else {for(int j = array.length-i-1 ; j > 0; j--) {if(array[j-1]> array[j]) {int temp = array[j-1];array[j-1] = array[j];array[j] = temp ;isChange = true ;}}}if(!isChange) {System.out.println(i);break ;}}for(int a : array) {System.out.print(a+",");}}public static void main(String[] args) {Cocktail cocktail = new Cocktail();cocktail.doIt();}}