冒泡排序的简单理解

翔仔收录于数据结构与算法

2022-06-18 约 874 字预计阅读 2 分钟

冒泡排序是学习排序算法时最先遇到的算法，其形象名称和排序过程最容易记住，很多人会在面试时谈论起，真正理解了冒泡排序算法才能更深入地学习其他排序算法。

详细描述

冒泡排序是一种交换排序，基本思想是在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。

即每当两个相邻的数比较后发现它们的顺序与排序要求相反时，就将它们互换。

冒泡排序详细的执行步骤如下：

从第一个元素开始，比较相邻的元素，如果前一个比后一个大，就交换它们两个；
从前往后，对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素就会是最大的数；
将这次找出的最大元素放在最后一个元素位置上，然后针对除这个最大元素以外的其他所有元素重复以上 1~2 步骤；
重复以上步骤，直到最后第一个元素和第二个元素完成比较、交换，则排序完成。

算法图解

问题解疑

冒泡排序是原地排序算法吗？

冒泡排序是一个原地排序算法，过程只涉及相邻数据的交换操作，只需要常量级的临时空间，它的空间复杂度是 $O(1)$。

冒泡排序是稳定的排序算法吗？

为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等时可以不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。

冒泡排序的时间复杂度是多少？

使用最优时间复杂度解法，原序列是有序时的时间复杂度是 $O(n)$；最坏情况时间复杂度为 $O(n^2)$；平均时间复杂度是 $O(n^2)$。

代码实现

排序接口

1
2
3
4
5
6
7
8
package cn.fatedeity.algorithm.sort;

/**
 * 排序接口
 */
public interface Sort {
    int[] sort(int[] numbers);
}

排序抽象类

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
package cn.fatedeity.algorithm.sort;

/**
 * 排序抽象类
 */
public abstract class AbstractSort implements Sort {
    protected void swap(int[] numbers, int src, int target) {
        int temp = numbers[src];
        numbers[src] = numbers[target];
        numbers[target] = temp;
    }
}

冒泡排序类

 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
package cn.fatedeity.algorithm.sort;

/**
 * 冒泡排序类
 */
public class BubbleSort extends AbstractSort {
    @Override
    public int[] sort(int[] numbers) {
        if (numbers.length <= 1) {
            return numbers;
        }

        for (int i = 0; i < numbers.length - 1; i++) {
            boolean doSwap = false;
            for (int j = 0; j + 1 < numbers.length - i; j++) {
                if (numbers[j] > numbers[j + 1]) {
                    this.swap(numbers, j, j + 1);
                    doSwap = true;
                }
            }
            // 优化基础冒泡排序的步骤
            if (!doSwap) {
                // 如果遍历整个序列无需交换，则表示整个序列已经完全有序
                return numbers;
            }
        }
        return numbers;
    }
}

目录