原理简述
冒泡排序是最简单的排序算法之一，主要是通过不断交换相邻元素，实现排序。
简单例子
对[4,2,6,3,2,1]进行升序排序
第一遍(排出最大值)
1.png
第二遍(排出次大值)
2.png
第三遍
3.png
第四遍
4.png
第五遍
5.png
每次循环都通过比较相邻的元素，逆序就进行交换，每次都将本次循环内的最大元素交换到最后，通过多次循环，最终变为一个有序的数组。
代码实现Java
public static int[] sort(int[] array){
//数组长度
int length = array.length;
//外层循环
for (int i=0; i
//内层循环
for (int j=0; j
//如果后面的元素比前面的大，交换
if (array[j+1]
int temp = array[j+1];
array[j+1] = array[j];
array[j] = temp;
}
}//内层循环 end
}//外层循环 end
return array;
}
优化
上面数组的例子其实并不好，加入我们要排序的数组为[1,2,3,4,5,6],我们使用上面的算法进行排序，可以发现，即便是一个已经排序好的数组，该走的步骤一步不落，虽然没有进行交换，但是循环次数和比较次数是一定的。也就是说，这些循环完全是没有必要的。那么，如何判断一个数组是有序的呢？
其实可以发现，如果内层循环没有发生交换，那么数组便已经是有序的，我们便可以退出循环了。我们可以用一个标记，来记录是否发生了交换，进而判断是否还要继续进行排序。
代码实现
public static int[] sort(int[] array){
int length = array.length;
for (int i=0; i
//用来标记是否需要结束循环
boolean flag = true;
for (int j=0; j
if (array[j+1]
int temp = array[j+1];
array[j+1] = array[j];
array[j] = temp;
//发生了交换，不能结束循环
flag = false;
}
}
//是否结束循环
if (flag){
break;
}
}
return array;
}
通过这个标记，对于数组[1,2,3,4,5,6]，内循环只需要进行一次，没有发生交换，外部循环就会结束，避免了多余的循环。
算法分析
时间复杂度：
最坏情况：O(n^2)
最好情况：O(n)
稳定性：
冒泡排序是稳定的排序，在排序过程中，相等的元素的相对位置不会发生变化。
完整代码
public class BubbleSort {
public static int[] sort(int[] array){
int length = array.length;
for (int i=0; i
//用来标记是否需要结束循环
boolean flag = true;
for (int j=0; j
if (array[j+1]
int temp = array[j+1];
array[j+1] = array[j];
array[j] = temp;
//发生了交换，不能结束循环
flag = false;
}
}
//是否结束循环
if (flag){
break;
}
}
return array;
}
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,6};
int[] sort = sort(arr);
for (int i : sort) {
System.out.println(i);
}
}
}
