冒泡排序
什么是冒泡排序呢？冒泡排序只会操作相邻的两个数据，每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小要求。如果不满足就让他们互换。一次冒泡会让至少一个元素移动到它应该在的位置。重复n次，就完成了n个数据的排序工作
案例
我们要对一组数据4，5，6，3，2，1，从小到到大进行排序。第一次冒泡操作的详细过程就是这样：
可以看出，经过一次冒泡操作之后，6这个元素已经存储在正确的位置上。要想完成所有数据的排序，我们只要进行6次这样的冒泡操作就行了。
实际上，刚讲的冒泡过程还可以优化。当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。
我这里还有另外一个例子，这里面给6个元素排序，只需要4次冒泡操作就可以了。
代码
package cn.study.sufa.Day27; import java.util.Arrays; /** * @PackageName: cn.study.sufa.Day27 * @author: youjp * @create: 2022-05-15 20:50 * @description: todo 冒泡排序 * @Version: 1.0 */ public class Solution { /** * 冒泡排序 * @param a * @param n */ public void sortInt(int a[],int n){ if (n<=1) return ; int tem=0; for(int i=0;i<n;i++){ //提前退出冒泡循环标志 boolean flag= false; for (int j=0;j<a.length-i-1;j++){ if(a[j]>a[j+1]){ //交换 tem =a[j]; a[j] =a[j+1]; a[j+1] =tem; flag =true; //表示有数据交换 } } if (!flag){ break; //没有数据交换，直接退出循环 } } } public static void main(String[] args) { int a[] ={24,21,3,5,99,88,90}; //输出排序结果 System.out.println("排序前"+Arrays.toString(a)); new Solution().sortInt(a,7); //输出排序结果 System.out.println("排序后"+Arrays.toString(a)); } }
输出结果
总结
1.冒泡排序是原地排序算法吗？
冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为O(1)，是一个原地排序算法。
2.冒泡排序是稳定的排序算法吗？
在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。
3.冒泡排序的时间复杂度是多少？
最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是O(n)。而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行n次冒泡操作，所以最坏情况时间复杂度为O(n2)。
平均情况：
“有序度”和“逆序度”：对于一个不完全有序的数组，如4，5，6，3，2，1，有序元素对为3个（4，5），（4，6），（5，6），有序度为3，逆序度为12；
对于一个完全有序的数组，如1，2，3，4，5，6，有序度就是n*(n-1)/2，也就是15，称作满有序度；逆序度=满有序度-有序度；冒泡排序、插入排序交换（或移动）次数=逆序度。
最好情况下初始有序度为n*(n-1)/2，最坏情况下初始有序度为0，则平均初始有序度为n*(n-1)/4，即交换次数为n*(n-1)/4，因交换次数<比较次数<最坏情况时间复杂度，所以平均时间复杂度为O(n^2)。
有兴趣的老爷，还可以关注我的公众号【一起收破烂】，回复【006】获取 最新java面试资料以及简历模型120套哦~
