基本思路

遍历给定的数组，从左往右，两两比较，小的放在左边，大的放在右边，遍历完成，数组有序。

先来看一个冒泡排序的过程：

给定数组：[5,3,2,1,4]

排序结果：[1,2,3,4,5]

拆解步骤

1.第一轮从左往右循环，遍历前5个数：

(1) 来到5和3，5大于3  ==>  5和3交换 

(2) 来到5和2，5大于2 ==> 5和2交换

 (3) 来到5和1,5大于1 ==> 5和1交换

 (4) 来到5和4,5大于4 ==> 5和4交换

 第一轮遍历结束，最右侧的5是数组中最大的，不用动了。

2.第二轮从左往右循环，遍历前4个数

 (1) 来到3和2，3大于2 ==> 3和2交换

(2) 来到3和1，3大于1 ==> 3和1做交换 

 (3) 来到3和4，3小于4 ==> 不用交换

第二轮遍历结束，最右侧的4已经是待排序数中最大的，不用动。

……略

得出规律

依次类推，得出规律：

1.每一次遍历的都是左侧待排序的数，遍历完成后会将最大的数放到最右边。

2.一共需要数组长度次数的遍历，比如数组长度是5，就需要5次遍历。

代码实现

public class BubbleSort {public static void main(String[] args) {int[] arr = {5, 3, 2, 1, 4};for (int i : arr) {System.out.print(i);System.out.print(" ");}System.out.println();bubbleSort(arr);System.out.println("冒泡排序后 ---->");for (int i : arr) {System.out.print(i);System.out.print(" ");}}/*** 冒泡排序** @param arr 待排序的数组*/public static void bubbleSort(int[] arr) {if (arr == null || arr.length < 2) {return;}for (int i = 0; i < arr.length; i++) {  // 数组长度是多少，就需要遍历多少次数组for (int j = 0; j < arr.length - i - 1; j++) { // 每次遍历的范围是 0 ~ len-i-1if (arr[j] > arr[j + 1]) {swap(arr, j, j + 1);}}}}/*** 数组交换** @param arr    数组* @param index1 下标1* @param index2 下标2*/public static void swap(int[] arr, int index1, int index2) {arr[index1] = arr[index1] + arr[index2];arr[index2] = arr[index1] - arr[index2];arr[index1] = arr[index1] - arr[index2];}
}

对数器验证

import cn.hutool.core.util.RandomUtil;
import java.util.Arrays;
public class BubbleSortTest {public static void main(String[] args) {int[] arr1 = new int[1000];for (int i = 0; i < arr1.length; i++) {arr1[i] = RandomUtil.randomInt(0, 10000);}final int[] arr2 = Arrays.copyOf(arr1, arr1.length);System.out.println("拷贝的数组arr2是否等于arr1：" + equals(arr1, arr2));print(arr1);Arrays.sort(arr1);System.out.println("使用系统的排序算法排序后的数组 ------->");print(arr1);BubbleSort.bubbleSort(arr2);System.out.println("使用冒泡排序算法排序后的数组 ------->");print(arr2);System.out.println("冒泡排序算法结果与系统内置排序算法结果是否一致：" + equals(arr1, arr2));}public static void print(int[] arr){for (int i : arr) {System.out.print(i);System.out.print(" ");}System.out.println();}public static boolean equals(int[] arr1, int[] arr2){if(arr1 == null && arr2 == null){return true;}if(arr1 == null || arr2 == null){return false;}if(arr1.length != arr2.length){return false;}for (int i = 0; i < arr1.length; i++) {if(arr1[i] != arr2[i]){return false;}}return true;}}

 优化

思路：如果在一次遍历中，发现所有的元素都不需要交换，那么说明这个数组已经是有序数组了。

比如一个数组：[1,2,3,4,5]，其冒泡排序过程如下：

 对于这种有序数组，其实只需要遍历一次就可以了。我们可以在每次循环的时候记录当前循环是否发生了交换操作，如果没有发生，就提前结束排序操作，因为数组已经是有序了。

需要优化的核心代码：

/*** 冒泡排序** @param arr 待排序的数组*/
public static void bubbleSort(int[] arr) {if (arr == null || arr.length < 2) {return;}for (int i = 0; i < arr.length; i++) {  // 数组长度是多少，就需要遍历多少次数组boolean swaped = false; // 用来记录是否交换的变量for (int j = 0; j < arr.length - i - 1; j++) { // 每次遍历的范围是 0 ~ len-i-1if (arr[j] > arr[j + 1]) {swaped = true; // 如果发生了交换，就记为trueswap(arr, j, j + 1);}}if(!swaped){// 如果一次交换都没有发生，就是数组已经有序了return;}}
}

其他定论

1.冒泡排序在排序期间没有申请其他的内存空间，它的空间复杂度是O(1)，所以是原地排序算法。

2.冒泡排序对于相同数值的元素来说，每次排序后所在的位置不变，因此冒泡排序是稳定的排序算法。

3.冒泡排序的时间复杂度是O(n^2)