算法——冒泡排序
冒泡排序（Bubble Sort）是一种交换排序算法，其核心思想是：通过多次相邻元素之间的比较和交换，将数组中的最大（或最小）元素逐步移动到数组的最后（或最前面）。因为最大（或最小）的元素像气泡一样逐渐“冒泡”到数组的边缘，因此得名冒泡排序。
冒泡排序的基本步骤
假设要对一个包含 n个元素的数组进行从小到大的排序：
- 从第一个元素开始，比较相邻的两个元素。如果前一个元素比后一个元素大，则交换这两个元素的位置，使得较大的元素后移。
- 依次比较相邻的每对元素，不断将较大的元素移动到靠后的位置。
- 每完成一次完整的遍历，最大元素会“冒泡”到数组的最后一位（无需再次比较）。
- 重复以上过程，对剩下的元素继续比较和交换。每进行一次遍历，待排序的元素数量减少1，直到所有元素排序完成。
冒泡排序的性质
- 稳定性：冒泡排序是一种稳定的排序算法。稳定性指的是：对于相同的元素，在排序后它们的相对顺序保持不变。因为在冒泡排序中，只有当两个相邻的元素不满足排序要求时，才会进行交换。
-
时间复杂度：
- 最优时间复杂度：O(n)，当输入数据已经是有序时，只需要进行一次遍历，并且没有发生交换。
- 最坏时间复杂度：O(n2)，当输入数据是逆序时，每一次比较都需要交换。
- 平均时间复杂度：O(n2)，无论输入数据的初始顺序如何。
- 空间复杂度：O(1)，因为冒泡排序只需要常数级别的额外空间来交换元素。
冒泡排序的算法演示
以排序数组 [5, 1, 4, 2, 8] 为例，进行冒泡排序的过程如下：
-
初始数组：
[5, 1, 4, 2, 8] - 第一趟排序：
- 比较
5和1，因为5 > 1，交换它们 →[1, 5, 4, 2, 8] - 比较
5和4，因为5 > 4，交换它们 →[1, 4, 5, 2, 8] - 比较
5和2，因为5 > 2，交换它们 →[1, 4, 2, 5, 8] - 比较
5和8，因为5 < 8，不交换 →[1, 4, 2, 5, 8] - 第一趟结束，最大值
8已经在正确位置。
- 比较
- 第二趟排序：
- 比较
1和4，因为1 < 4，不交换 →[1, 4, 2, 5, 8] - 比较
4和2，因为4 > 2，交换它们 →[1, 2, 4, 5, 8] - 比较
4和5，因为4 < 5，不交换 →[1, 2, 4, 5, 8] - 第二趟结束，次大值
5已经在正确位置。
- 比较
- 第三趟排序：
- 比较
1和2，因为1 < 2，不交换 →[1, 2, 4, 5, 8] - 比较
2和4，因为2 < 4，不交换 →[1, 2, 4, 5, 8] - 第三趟结束，次次大值
4已经在正确位置。
- 比较
- 第四趟排序：
- 比较
1和2，因为1 < 2，不交换 →[1, 2, 4, 5, 8] - 第四趟结束，数组已经完全有序。
- 比较
冒泡排序的优化
在某些情况下，数组可能在提前几轮就已经完全有序，因此没有必要继续执行剩下的比较过程。可以通过一个布尔变量 swapped 来记录在每轮遍历中是否有交换发生。如果在某一轮中没有发生交换，表示数组已经有序，可以提前结束排序。
public class OptimizedBubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换相邻元素
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// 如果没有发生交换，提前结束
if (!swapped) {
break;
}
}
}
}
完整流程总结
- 冒泡排序每次遍历会将最大（或最小）元素冒泡到正确位置。
- 对每一趟遍历，剩余未排序的部分继续进行比较和交换。
- 可以通过优化，避免无效的排序操作，减少时间复杂度。
尽管冒泡排序的思想非常直观，适合教学和小规模数据排序，但由于其时间复杂度较高，在实际应用中通常不适用于大规模数据的排序。