冒泡排序¶
一、算法描述¶
1.1 核心思想¶
- 每次操作只会影响相邻的 2 个元素
- 每轮冒泡至少让 1 个元素移动到它正确的位置（1 轮是指从头到尾操作一遍元素）
- 最多经过 n 轮冒泡后，所有元素都会被移到正确的位置
1.2 细节解释¶
比如说，数组 [2, 7, 1, 4, 3, 6, 5]。
___ ___ ___ ___ ___ ___ ___
| 2 | 7 | 1 | 4 | 3 | 6 | 5 |
从后面往前面冒泡，由于 5 < 6 所以 5 要往前冒泡：
___
| |
V V
___ ___ ___ ___ ___ ___ ___
| 2 | 7 | 1 | 4 | 3 | 5 | 6 |
接着判断 5 > 3，5 不能往前冒泡，当前对象换成 3：
|
V
___ ___ ___ ___ ___ ___ ___
| 2 | 7 | 1 | 4 | 3 | 5 | 6 |
接下来是 3 < 4，所以 3 要往前冒泡：
___
| |
V V
___ ___ ___ ___ ___ ___ ___
| 2 | 7 | 1 | 3 | 4 | 5 | 6 |
再接着是 3 > 1，3 不能冒泡，切换当前对象为 1：
|
V
___ ___ ___ ___ ___ ___ ___
| 2 | 7 | 1 | 3 | 4 | 5 | 6 |
接下来是 1 < 7，1 要往前冒泡：
___
| |
V V
___ ___ ___ ___ ___ ___ ___
| 2 | 1 | 7 | 3 | 4 | 5 | 6 |
最后是 1 < 2，所以 1 要往前冒泡：
___
| |
V V
___ ___ ___ ___ ___ ___ ___
| 1 | 2 | 7 | 3 | 4 | 5 | 6 |
这样一轮冒泡结束后，1 已经在它应该在的位置了。
已排序 未排序
___ ___ ___ ___ ___ ___ ___
| 1 | | 2 | 7 | 3 | 4 | 5 | 6 |
后面再对其他未排序的元素进行冒泡，直到所有元素都排好序为止。
每过一轮冒泡，总能把一个值放到它正确的位置，经过 n 轮后就排好序了。
二、算法实现¶
- 总共执行 n 轮冒泡
- 每轮冒泡，会将未排序元素的最小值放到已排序元素的后面
public void bubbleSort(int[] arr) {
int n = arr.length;
// 进行 n 轮冒泡
for (int i = 0; i < n; i++) {
// 每轮冒泡，都会将一个元素放置到正确的位置
for (int j = n - 1; j > i; j--) {
// 每次只会操作相邻的2个元素
if (arr[j] < arr[j - 1]) {
// 交换相邻元素
swap(arr, j, j - 1);
}
}
}
}
举个例子，原始数据是：[0, 3, 1, 6, 2, 5, 4]，冒泡排序过程如下：
=====第 1 轮冒泡=====
[0, 3, 1, 6, 2, 4, 5]
[0, 3, 1, 6, 2, 4, 5]
[0, 3, 1, 2, 6, 4, 5]
[0, 3, 1, 2, 6, 4, 5]
[0, 1, 3, 2, 6, 4, 5]
[0, 1, 3, 2, 6, 4, 5]
=====第 2 轮冒泡=====
[0, 1, 3, 2, 6, 4, 5]
[0, 1, 3, 2, 4, 6, 5]
[0, 1, 3, 2, 4, 6, 5]
[0, 1, 2, 3, 4, 6, 5]
[0, 1, 2, 3, 4, 6, 5]
=====第 3 轮冒泡=====
[0, 1, 2, 3, 4, 5, 6]
[0, 1, 2, 3, 4, 5, 6]
[0, 1, 2, 3, 4, 5, 6]
[0, 1, 2, 3, 4, 5, 6]
=====第 4 轮冒泡=====
[0, 1, 2, 3, 4, 5, 6]
[0, 1, 2, 3, 4, 5, 6]
[0, 1, 2, 3, 4, 5, 6]
=====第 5 轮冒泡=====
[0, 1, 2, 3, 4, 5, 6]
[0, 1, 2, 3, 4, 5, 6]
=====第 6 轮冒泡=====
[0, 1, 2, 3, 4, 5, 6]
三、算法优化¶
当某轮冒泡中，没有执行任何交换时，其实就说明数组已经排序好了。
遇到这种情况，可以对冒泡排序进行优化，提前跳出循环：
public void bubbleSort(int[] arr) {
int n = arr.length;
// 进行 n 轮冒泡
for (int i = 0; i < n; i++) {
// 每轮冒泡，都会将一个元素放置到正确的位置
boolean flag = false;
for (int j = n - 1; j > i; j--) {
// 每次只会操作相邻的2个元素
if (arr[j] < arr[j - 1]) {
// 交换相邻元素
swap(arr, j, j - 1);
flag = true;
}
}
// 一轮冒泡里没有交换，说明已经排好序了
if (!flag) {
break;
}
}
}
上面同样的例子，执行过程如下：
=====第 1 轮冒泡=====
[0, 3, 1, 6, 2, 4, 5]
[0, 3, 1, 6, 2, 4, 5]
[0, 3, 1, 2, 6, 4, 5]
[0, 3, 1, 2, 6, 4, 5]
[0, 1, 3, 2, 6, 4, 5]
[0, 1, 3, 2, 6, 4, 5]
=====第 2 轮冒泡=====
[0, 1, 3, 2, 6, 4, 5]
[0, 1, 3, 2, 4, 6, 5]
[0, 1, 3, 2, 4, 6, 5]
[0, 1, 2, 3, 4, 6, 5]
[0, 1, 2, 3, 4, 6, 5]
=====第 3 轮冒泡=====
[0, 1, 2, 3, 4, 5, 6]
[0, 1, 2, 3, 4, 5, 6]
[0, 1, 2, 3, 4, 5, 6]
[0, 1, 2, 3, 4, 5, 6]
=====第 4 轮冒泡=====
[0, 1, 2, 3, 4, 5, 6]
[0, 1, 2, 3, 4, 5, 6]
[0, 1, 2, 3, 4, 5, 6]
四、算法分析¶
4.1 时间复杂度¶
- 最好时间复杂度：O(n)
- 最坏时间复杂度：O(n^2)
- 平均时间复杂度：O(n^2)
4.2 空间复杂度¶
- 空间复杂度：O(1)
- 原地算法
4.3 稳定性¶
- 稳定排序算法
附录¶
/**
* 冒泡排序
* <p>
* 时间复杂度：最好 O(n) 最差 O(n^2) 平均 O(n^2)
* <p>
* 空间复杂度：O(1)
* <p>
* 稳定性：稳定
*
* @author weijiaduo
* @since 2022/7/21
*/
public class BubbleSort implements Sort {
/**
* 排序
*
* @param arr 数组
*/
@Override
public void sort(int[] arr) {
// slowSort(arr);
fastSort(arr);
}
/**
* 慢一点的冒泡排序
*
* @param arr 数组
*/
private void slowSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
for (int j = n - 1; j > i; j--) {
if (arr[j] < arr[j - 1]) {
swap(arr, j, j - 1);
}
}
}
}
/**
* 快一点的冒泡排序
*
* @param arr 数组
*/
private void fastSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
boolean flag = false;
for (int j = n - 1; j > i; j--) {
if (arr[j] < arr[j - 1]) {
swap(arr, j, j - 1);
flag = true;
}
}
// 一轮冒泡里没有交换，说明已经排好序了
if (!flag) {
break;
}
}
}
}