冒泡排序

   数据结构与算法 / 排序算法 6 分钟读完 (大约890个字)0次访问

冒泡排序

一、算法描述

1.1 核心思想

  • 每次操作只会影响相邻的 2 个元素
  • 每轮冒泡至少让 1 个元素移动到它正确的位置（1 轮是指从头到尾操作一遍元素）
  • 最多经过 n 轮冒泡后，所有元素都会被移到正确的位置

1.2 细节解释

比如说，数组 [2, 7, 1, 4, 3, 6, 5]。

1
2
 ___ ___ ___ ___ ___ ___ ___
| 2 | 7 | 1 | 4 | 3 | 6 | 5 |

从后面往前面冒泡，由于 5 < 6 所以 5 要往前冒泡：

1
2
3
4
5
                       ___
                      |   |
                      V   V
 ___ ___ ___ ___ ___ ___ ___
| 2 | 7 | 1 | 4 | 3 | 5 | 6 |

接着判断 5 > 3，5 不能往前冒泡，当前对象换成 3：

1
2
3
4
                  |
                  V
 ___ ___ ___ ___ ___ ___ ___
| 2 | 7 | 1 | 4 | 3 | 5 | 6 |

接下来是 3 < 4，所以 3 要往前冒泡：

1
2
3
4
5
               ___
              |   |
              V   V
 ___ ___ ___ ___ ___ ___ ___
| 2 | 7 | 1 | 3 | 4 | 5 | 6 |

再接着是 3 > 1，3 不能冒泡，切换当前对象为 1：

1
2
3
4
          |
          V
 ___ ___ ___ ___ ___ ___ ___
| 2 | 7 | 1 | 3 | 4 | 5 | 6 |

接下来是 1 < 7，1 要往前冒泡：

1
2
3
4
5
       ___
      |   |
      V   V
 ___ ___ ___ ___ ___ ___ ___
| 2 | 1 | 7 | 3 | 4 | 5 | 6 |

最后是 1 < 2，所以 1 要往前冒泡：

1
2
3
4
5
   ___
  |   |
  V   V
 ___ ___ ___ ___ ___ ___ ___
| 1 | 2 | 7 | 3 | 4 | 5 | 6 |

这样一轮冒泡结束后，1 已经在它应该在的位置了。

1
2
3
已排序                  未排序
 ___           ___ ___ ___ ___ ___ ___
| 1 |         | 2 | 7 | 3 | 4 | 5 | 6 |

后面再对其他未排序的元素进行冒泡，直到所有元素都排好序为止。

每过一轮冒泡，总能把一个值放到它正确的位置，经过 n 轮后就排好序了。

二、算法实现

  • 总共执行 n 轮冒泡
  • 每轮冒泡，会将未排序元素的最小值放到已排序元素的后面
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
=====第 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]

三、算法优化

当某轮冒泡中，没有执行任何交换时，其实就说明数组已经排序好了。

遇到这种情况，可以对冒泡排序进行优化，提前跳出循环：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
=====第 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 稳定性

  • 稳定排序算法

附录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
 * 冒泡排序
 * <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;
            }
        }
    }

}

冒泡排序

http://example.com/algorithm/sort/bubblesort/

作者

jiaduo

发布于

2022-07-21

更新于

2023-10-06

许可协议

 

目录

×