冒泡算法思路

假设对数组arr=[9,1,5,8,3,7,4,6,2]由小到大排序

 

方式一：

从左到右遍历，把每个位置确定下来。

for(i=0;i<len-1;i++){

   for(j=i+1;j<len-1;j++){

      if(arr[j]>arr[i]){

         swap

执行顺序：

1,9,5,8,3,7,4,6,2//只换一次，就确定第1个位置的数据

1,5,9,8,3,7,4,6,2

1,3,9,8,5,7,4,6,2

1,2,9,8,5,7,4,6,3//交换了三次，但是把3居然交换到最后了，这会导致下一次的循环交换次数增加。所以出现更优化的方式二

……

 

方式二：

仍然是从左到右遍历，确定每个位置的数值。但是内部的循环方式不一样。

for(i=0;i<len-1;i++){

   for(j=len-1;j>=i;j--){//从尾部开始循环

      if(arr[j]>arr[j+1]){//把小的往前排，就像冒泡一样

         swap

9,1,5,8,3,7,4,2,6

9,1,5,8,3,7,2,4,6

9,1,5,8,3,2,7,4,6

9,1,5,8,2,3,7,4,6

9,1,5,2,8,3,7,4,6

9,1,2,5,8,3,7,4,6

1,9,2,5,8,3,7,4,6

继续第二遍循环

1,9,2,5,8,3,4,7,6

1,9,2,5,3,8,4,7,6

1,9,2,3,5,8,4,7,6

1,2,9,3,5,8,4,7,6

……

可以看出，优化主要集中在减少swap次数。方式一会把一个很小的数扔到最后，导致后续的无效swap次数增多。方式二在循环的过程中，一直把小的数字往前调整，直到调整不动为止。可以看出，swap都是有效的。即使前期swap增多，后期swap也会大大减少。

 

方式二的进一步优化：

假如数组排序前就是2,1,3,4,5,6,7,8,9呢，这样第一次交换后，就已经排好序，后面的比较都浪费了。怎么才能让程序知道已经排好序了呢，答案就是冒泡时发现一个泡都冒不动了。

boolean flag = true;

for(i=0;(i<len-1)&&flag;i++){//

   flag = false;

   for(j=len-1;j>=i;j--){//从尾部开始循环

      if(arr[j]>arr[j+1]){//把小的往前排，就像冒泡一样

         flag = true;

         swap

 

可以看出，假如没有swap，flag就会变成false导致循环立即退出。