冒泡排序法

1.原理

假设数组长度为N：

1.从第1个元素开始，两两比较相邻元素的大小，如果前一个元素大于后一个元素，就调换两者位置（升序）.

2.当所有相邻元素比较并换位后，最大的元素就排在位置N.

3.重复步骤1，从第1个元素开始两两比较，直到将第n-2个元素与第n-1个元素比较并换位（此时无需将第n-1个元素和第n个元素比较，因为第n个元素已经最大）.

注：即第一次排序检查n-1次，第二次排序检查n-2次......最后一次只需检查1次

4.当只有第1个元素和第2个元素比较并排序时，排序完成.

2.示例

待排序数组：| 8 | 4 | 7 | 3 | 5 | 1 |

第一次外排序：第二次外排序第三次外排序

第一次比较：8>4,换位第一次比较：4<7,不换位第一次比较：4<3,换位

换位前：| 8 | 4 | 7 | 3 | 5 | 1 | 换位前：| 4 | 7 | 3 | 5 | 1 | 8 | 换位前：| 4 | 3 | 5 | 1 | 7 | 8 |

换位后：| 4 | 8 | 7 | 3 | 5 | 1 | 换位后：| 4 | 7 | 3 | 5 | 1 | 8 | 换位后：| 3 | 4 | 5 | 1 | 7 | 8 |

第二次比较：8>7,换位第二次比较：7>3,换位第二次比较：4<5,不换位

换位前：| 4 | 8 | 7 | 3 | 5 | 1 | 换位前：| 4 | 7 | 3 | 5 | 1 | 8 | 换位前：| 3 | 4 | 5 | 1 | 7 | 8 |

换位后：| 4 | 7 | 8 | 3 | 5 | 1 | 换位后：| 4 | 3 | 7 | 5 | 1 | 8 | 换位后：| 3 | 4 | 5 | 1 | 7 | 8 |

第三次比较：8>3,换位第三次比较：7>5,换位第三次比较：5>1,换位

换位前：| 4 | 7 | 8 | 3 | 5 | 1 | 换位前：| 4 | 3 | 7 | 5 | 1 | 8 | 换位前：| 3 | 4 | 5 | 1 | 7 | 8 |

换位后：| 4 | 7 | 3 | 8 | 5 | 1 | 换位前：| 4 | 3 | 5 | 7 | 1 | 8 | 换位后：| 3 | 4 | 1 | 5 | 7 | 8 |

第四次比较：8>5,换位第四次比较：7>1,换位

换位前：| 4 | 4 | 3 | 8 | 5 | 1 | 换位前：| 4 | 3 | 5 | 7 | 1 | 8 |

换位后：| 4 | 7 | 3 | 5 | 8 | 1 | 换位后：| 4 | 3 | 5 | 1 | 7 | 8 |

第五次比较：8>1,换位

换位前：| 4 | 7 | 3 | 5 | 8 | 1 |

换位后：| 4 | 7 | 3 | 5 | 1 | 8 |

第四次外排序：第五次外排序：

第一次比较：3<4,不换位第一次比较：3<4,不换位

换位前：| 3 | 4 | 1 | 5 | 7 | 8 | 换位前：| 3 | 1 | 4 | 5 | 7 | 8 |

换位后：| 3 | 4 | 1 | 5 | 7 | 8 | 换位后：| 1 | 3 | 4 | 5 | 7 | 8 |

第二次比较：4>1,换位

换位前：| 3 | 4 | 1 | 5 | 7 | 8 |

换位后：| 3 | 1 | 4 | 5 | 7 | 8 |

3.时间复杂度

最好情况：序列是升序排列，在这种情况下，需要进行的比较操作为（n-1）次，交换操作为0次，即O(n)。

最坏情况：序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次，交换操作也是n(n-1)/2次，即O(n^2)。

注：例如654321，需要将它排为654321，则只需要比较5次，此时顺序不变，不要进行第二次循环；当将它排为123456时，就要比较5+4+3+2+1次，换位5+4+3+2+1次。

4.动态演示

5.实例

 1 public class BubbleSort {
 2     public static void main(String args[]){
 3         int i,j=0;
 4         int a[]={8,4,7,3,5,1};
 5         for(i=0;i<a.length-1;i++){
 6             for(j=0;j<a.length-1-i;j++){
 7                 if(a[j]>a[j+1]){
 8                     int temp=a[j];
 9                     a[j]=a[j+1];
10                     a[j+1]=temp;
11                 }
12             }
13         }
14         for(i=0;i<6;i++){
15             System.out.println("a["+i+"]"+"="+a[i]);
16         }
17     }
18 }

6.变形

当数组变为int等类型的数字变量时，冒泡排序同样能将数字重新排序。

原理

1.此时将数字n%10取余数，作为数组的第一个元素

2.然后n/10,由于为int类型，会取整数

3.重复步骤1，将余数作为数组的第二个元素

4.将数字除到个位数，获取了所有一个数各个位的数字

待排序数字：847351

 1 public class ShuZuTest {
 2     public static void main(String args[]){
 3         int i,j=0;
 4         int n=847351;
 5         int a[]=new int[6];            //用于存放各个数
 6         for( i=0;i<6;i++){            
 7             a[i]=n%10;                 //取余
 8                 n=n/10;                 
 9         }      
10          //冒泡排序         
11         for(i=0;i<a.length-1;i++){
12             for( j=0;j<a.length-1-i;j++){
13                 if(a[j]>a[j+1]){
14                     int temp=a[j];
15                     a[j]=a[j+1];
16                     a[j+1]=temp;
17                 }
18             }
19         }
20         for(int k=0;k<6;k++){
21             System.out.println("a"+k+":  "+a[k]);
22         }
23         //可以获取最大值或最小值
24         int min=a[0]*100000+a[1]*10000+a[2]*1000+a[3]*100+a[4]*10+a[5]*1;
25         int max=a[5]*100000+a[4]*10000+a[3]*1000+a[2]*100+a[1]*10+a[0]*1;
26         System.out.println("min:"+min+"  max:"+max);
27     }  
28 }