bubbleSort

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

算法步骤

第一版

template<typenameT>

voidbubbleSort(Tarr[],intn){

   //在当前数组上，每次都是从第一个元素开始比较，直到没有元素交换，flag仍为true，排序完成

   for(inti=0;i<n;i++){

       boolflag=true;

       //循环一次，比较总数就减少一次

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

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

               swap(arr[j-1],arr[j]);

               flag=false;

           }

       }

       if(flag) break;

   }

   return;

}

template<typenameT>

voidbubbleSort(Tarr[],intn){

   boolswapped;

   do{

       swapped=false;

       for(inti=1;i<n;i++){

           if(arr[i-1]>arr[i]){

               swap(arr[i-1],arr[i]);

               swapped=true;

           }

       }

       // 优化, 每一趟Bubble Sort都将最大的元素放在了最后的位置

       // 所以下一次排序, 最后的元素可以不再考虑

       n--;

   }while(swapped);

}

第二版

使用newn进行优化，记录最后交换的位置

template<typenameT>

voidbubbleSort(Tarr[],intn){

   intnewn;//使用newn进行优化

   do{

       newn=0;

       for(inti=1;i<n;i++){

           if(arr[i-1]>arr[i]){

               swap(arr[i-1],arr[i]);

               //记录最后一次交换位置，在此之后的元素在下一轮扫描中不被考虑

               newn=i;

           }

       }

       n=newn;

   }while(n>0);

}

python实现

defbubbleSort(arr):

   n = len(arr)

   foriinrange(n):

       flag = 1

       forjinrange(1, n-i):

           ifarr[j-1] >arr[j]:

               arr[j-1], arr[j] = arr[j], arr[j-1]

               flag = 0

       ifflag == 1:

           break

   returnarr