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
