一、算法思想
冒泡排序是一种交换排序算法，元素通过两两的比较，交换不满足次序要求的元素，直到整个数组都满足次序要求为止。
比如一个无序的数组中有元素[4,3,8,6,1]，如果按照升序的排序顺序，则采用冒泡排序的过程则是：
第一趟排序：先是4和3比较，4比3大，则交换位置，则顺序是
3 4 8 6 1
然后4和8比较，8比4大，则不交换顺序，顺序还是
3 4 8 6 1
然后8和6比较，8比6大，则交换顺序，则顺序是
3 4 6 8 1
然后 8 和 1 比较 8 比1 大，则交换顺序，则顺序是
3 4 6 1 8
所以第一趟排序的最终结果是3 4 6 1 8，即最大的元素在最后的位置。
第二趟排序：3 和 4 比较，3 比 4小，不交换顺序，顺序不变
4 和 6 比较，4 比6 小，不交换顺序，顺序不变
6 和 1 比较，6 比 1 大，交换顺序，则顺序为 3 4 1 6 8，
6 和 8 比较，6 比 8 小，不交换顺序，则顺序为3 4 1 6 8
所以第二趟的排序结果为3 4 1 6 8，即第二大的元素在倒数第二的位置
第三趟排序 3 和 4 比较 不交换顺序
4 和 1 比较 交换顺序，交换后顺序为3 1 4 6 8
。。。。后面已经为顺序了，交换顺序不变，
所以第三趟的排序为3 1 4 6 8，即第三大的顺序在倒数第三的位置
第四趟排序 3 和 1 比较，交换顺序，交换后排序为 1 3 4 6 8，
经过四趟排序，数组为顺序数组。
二、算法分析
通过上述演示，我们可以发现当长度为N的数组的初始状态是顺序的，则一趟排序即可完成排序。比较次数为N-1和记录移动次数为0，均为最小值。所以，冒泡排序最好时间复杂度为O(N)。
当数组的初始顺序是倒叙的，则需要进行 N -1 趟排序。每趟排序要进行 N - i 次关键字的比较(1 ≤ i ≤ N - 1)，每次比较都必须移动记录三次来达到交换记录位置。比较和移动次数均达到最大值N^2,所以冒泡排序的最坏时间复杂度为O(N^2)。
所以，冒泡排序的平均时间复杂度为O(N^2)。 当两个元素大小相等时，相对位置不会发生改变，所以冒泡排序是稳定的排序算法
三、Java代码
import java.util.Arrays; /** * @Author: 江夏 * @Date: 2021/11/02/20:50 * @Description:冒泡排序算法 */ public class MaoPaoSort { public static void main(String[] args) { int testTime=500000; int size = 10; int value=100; boolean succeed = true; for(int i = 0 ;i<testTime;i++){ int[] arr1 = generateRandomArray(size,value); int[] arr2 = copyArray(arr1); int[] arr3= copyArray(arr1); bubbleSort(arr1); rightMethod(arr2); if(!isEqual(arr1,arr2)){ succeed=false; printArray(arr3); break; } } int[] arr= generateRandomArray(size,value); printArray(arr); bubbleSort(arr); printArray(arr); } //产生一个随机数组，数组的长度和值都是随机的， public static int[] generateRandomArray(int size,int value){ int[] arr = new int[(int)((size+1)*Math.random())]; for(int i = 0 ;i<arr.length;i++){ //值也可以是随机的 arr[i]=(int)((value+1)*Math.random())-(int)(value*Math.random()); } return arr; } //复制数组 public static int[] copyArray(int[] arr){ if(arr==null){ return null; } int[] res = new int[arr.length]; for(int i = 0 ;i<arr.length;i++){ res[i]=arr[i] ; } return res; } public static void rightMethod(int[] arr){ Arrays.sort(arr); } public static boolean isEqual(int[] arr1,int[] arr2){ if(arr1==null&&arr2!=null||arr1!=null&&arr2==null){ return false; } if (arr1==null&&arr2==null){ return true; } if (arr1.length!=arr2.length){ return false; } for(int i = 0;i<arr1.length;i++){ if(arr1[i]!=arr2[i]){ return false; } } return true; } //打印出数组 public static void printArray(int[] arr){ if(arr==null){ return; } for(int i = 0 ;i<arr.length;i++){ System.out.print(arr[i]+" "); } System.out.println(); } //N个数字冒泡排序，总共要进行N-1趟比较，每趟的排序次数为(N-i)次比较 public static void bubbleSort(int[] arr){ if(arr==null||arr.length<2){ return; } //需要进行arr.length趟比较 for(int i = 0 ;i<arr.length-1;i++){ //第i趟比较 for(int j = 0 ;j<arr.length-i-1;j++){ //开始进行比较，如果arr[j]比arr[j+1]的值大，那就交换位置 if(arr[j]>arr[j+1]){ int temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } } } public static void rightMathods(int[] arr){ //调用系统调用的函数来进行验证 Arrays.sort(arr); } } 复制代码
运行结果如下：
四 总结
冒泡排序原理就是比较两个相邻的元素，将值大的元素交换到右边，因为这种排序相等的元素不进行交换，所以它是一种稳定排序
冒泡排序的优点：每进行一趟排序，就会少比较一次，因为每进行一趟排序都会找出一个较大值。一定程度上减少了算法的量。
如果元素刚好都是正序排序，只需要走一趟即可完成排序。所需的比较次数C和记录移动次数M均达到最小值，即：Cmin=n-1;Mmin=0;所以，冒泡排序最好的时间复杂度为O(n)。
如果元素都是反序排序，则需要进行n-1趟排序。每趟排序要进行n-i次比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达
到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
所以冒泡排序总的平均时间复杂度为：O(n2)（n的平方）。
以上就是关于冒泡排序的介绍！
