排序算法：冒泡排序

一、简介

冒泡排序（Bubble Sort）是一种简单直观的排序算法。通过对要排序的数组从前向后循环遍历，依次对相邻两个元素的值进行比较，如果他们的顺序错误就把他们交换过来。一直重复执行，直到没有元素交换，也就代表该数组已经排序完成了。这个算法的名字由来是因为越小的元素会经由交换慢慢的到数组的最前面。

作为最简单的排序算法之一，冒泡排序还有一种优化手段，就是创建一个布尔变量，用于判断当前循环是否发送了交换，如果遍历中元素没有发生交换，则证明该数组已经有序。但这种改进对于提升性能来说并没有什么太大作用。

二、动图演示

---

三、代码实现

3.1 原始版本

import java.util.Arrays;public class Sort {public static void main(String[] args) {// 排序前的数组int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};System.out.println("排序前：" + Arrays.toString(arr));// 调用冒泡排序方法bubbleSort(arr);// 排序后的数组System.out.println("排序后：" + Arrays.toString(arr));}// 冒泡排序public static void bubbleSort(int[] arr) {// 每次排序都会冒出一个最大值，如果有 n 个数据，则要进行 n - 1 次排序// 当你进行第 n - 1 次循环，剩下的那个数据必然是符合要求的，就没必要进行排序，所以可以 -1for (int i = 0; i < arr.length - 1; i++) {// 这里要 -i 的原因是，当每次外层循环结束后，都会产生一个最大值// 所以在后面的内层循环就没必要再对这个最大值进行比较，没意义for (int j = 0; j < arr.length - 1 - i; j++) {// 核心逻辑：如果当前元素大于后一个元素，则交换，最终达到从小到大排序// 反之：如果当前元素小于后一个元素，再=在交换的话，最终会达到从大到小排序if (arr[j] > arr[j + 1]) {// 交换规则：让当前元素变成后一个元素，后一个元素变成当前元素int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}
}

运行结果：

排序前：[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
排序后：[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

---

3.2 优化版本

试想一下，如果排序的数组在某一轮排序中没有元素交换，这就说明这个数组已经有序了，则可以提前结束排序，避免不必要操作。

优化步骤：

• 引入 swapped 布尔变量，用于标记每一轮排序是否发生了元素交换。
• 在内层循环中，如果有元素交换，将 swapped 设为 true。
• 在内层循环结束后，如果 swapped 为 false，说明数组已经有序，提前结束排序。

import java.util.Arrays;public class Sort {public static void main(String[] args) {// 排序前的数组int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};System.out.println("排序前：" + Arrays.toString(arr));// 调用冒泡排序方法bubbleSort(arr);// 排序后的数组System.out.println("排序后：" + Arrays.toString(arr));}// 冒泡排序public static void bubbleSort(int[] arr) {// 用于标记是否发生交换boolean swapped;// 每次排序都会冒出一个最大值，如果有 n 个数据，则要进行 n - 1 次排序// 当你进行第 n - 1 次循环，剩下的那个数据必然是符合要求的，就没必要进行排序，所以可以 -1for (int i = 0; i < arr.length - 1; i++) {// 没有交换swapped = true;// 这里要 -i 的原因是，当每次外层循环结束后，都会产生一个最大值// 所以在后面的内层循环就没必要再对这个最大值进行比较，没意义for (int j = 0; j < arr.length - 1 - i; j++) {// 核心逻辑：如果当前元素大于后一个元素，则交换，最终达到从小到大排序// 反之：如果当前元素小于后一个元素，再=在交换的话，最终会达到从大到小排序if (arr[j] > arr[j + 1]) {// 交换规则：让当前元素变成后一个元素，后一个元素变成当前元素int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;// 发生交换swapped = false;}}// 如果没有发生交换，则代表当前数组已经有序了，可以中断外层循环，减少循环次数，提高效率if (swapped) {break;}}}
}

运行结果：

排序前：[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
排序后：[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

---

3.3 性能比较

我通过定义一个 count 变量，得到两个版本完成排序后的的循环次数，用于统计两个版本冒泡排序的性能，结果如下：

• 原始版本：105 次
• 优化版本：95 次

原始冒泡排序和优化后的冒泡排序在最坏和平均情况下的时间复杂度都是 O(n^2)，但优化后的冒泡排序在最好情况下（即数组已经有序）可以提前终止，将时间复杂度降至 O(n)，提高了在部分有序数组排序时的性能。

在空间复杂度方面，二者都为 O(1)，因为只使用了少量辅助变量，不需要额外空间存储元素。

---

四、总结

冒泡排序并非是很高效的排序算法，冒泡排序主要适用于小数据量排序，在实际应用中使用的比较少，更多可能会出现在考试和简单的笔试中。要求掌握其两个版本的实现和知道其时间复杂度，这样有助于理解排序算法的基本原理。

---