冒泡排序是什么？冒泡排序的优化方法有哪些

冒泡排序的基础概念

冒泡排序是一种简单的交换排序算法，它的核心思想是通过重复遍历待排序的序列，每次比较相邻的两个元素，如果它们的顺序不符合排序要求就交换它们的位置。这样每一轮遍历结束后，最大或者最小的元素就会像气泡一样浮到序列的顶端，因此得名冒泡排序。

冒泡排序的基本执行流程可以分为以下几步：

• 从序列的第一个元素开始，依次比较相邻的两个元素
• 如果前一个元素大于后一个元素（以升序排序为例），就交换两个元素的位置
• 重复上述比较和交换过程，直到遍历到序列的最后一个元素，此时最大的元素会被移动到序列末尾
• 排除已经排好序的末尾元素，对剩余的元素重复上述过程，直到所有元素都排好序

原始冒泡排序的实现

我们以升序排序为例，实现一个最基础的冒泡排序，代码如下：

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        // 外层循环控制排序的轮次，一共需要arr.length-1轮
        for (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;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] testArr = {5, 3, 8, 4, 2};
        bubbleSort(testArr);
        // 输出排序后的数组
        for (int num : testArr) {
            System.out.print(num + " ");
        }
    }
}

原始冒泡排序的时间复杂度在最坏和平均情况下都是O(n²)，其中n是待排序序列的长度，空间复杂度为O(1)，属于原地排序算法，也是稳定的排序算法。

冒泡排序的常见优化方法

优化一：提前终止排序

原始冒泡排序不管序列是否已经有序，都会执行完所有的轮次比较，存在不必要的性能浪费。如果在某一轮遍历中没有发生任何元素交换，说明序列已经完全有序，此时可以直接终止排序过程。

实现方式是在每轮遍历开始时设置一个交换标志位，默认值为false，只要发生了交换就将标志位设为true，每轮结束后判断标志位，如果还是false就直接退出循环。优化后的代码如下：

public class BubbleSortOptimized1 {
    public static void bubbleSort(int[] arr) {
        // 外层循环控制排序轮次
        for (int i = 0; i < arr.length - 1; i++) {
            // 交换标志位，初始为false
            boolean swapped = false;
            // 内层循环比较相邻元素
            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;
                    // 发生交换，标志位设为true
                    swapped = true;
                }
            }
            // 如果本轮没有发生交换，说明序列已经有序，直接退出
            if (!swapped) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] testArr = {1, 2, 3, 4, 5};
        bubbleSort(testArr);
        for (int num : testArr) {
            System.out.print(num + " ");
        }
    }
}

这种优化在序列本身已经有序或者接近有序的场景下，能大幅减少比较次数，最好情况下时间复杂度可以降到O(n)。

优化二：记录最后交换位置减少比较范围

原始冒泡排序每轮都会固定比较到arr.length - 1 - i的位置，但实际上，每轮最后一次发生交换的位置之后的元素，在下一轮已经是有序的，不需要再参与比较。我们可以记录每轮最后一次交换的位置，下一轮的比较范围就截止到这个位置之前。

优化后的实现代码如下：

public class BubbleSortOptimized2 {
    public static void bubbleSort(int[] arr) {
        // 记录最后一次交换的位置，初始为数组最后一个索引
        int lastSwapIndex = arr.length - 1;
        for (int i = 0; i < arr.length - 1; i++) {
            // 每轮开始时的交换标志位
            boolean swapped = false;
            // 当前轮的比较截止到上一次最后交换的位置
            int currentLastSwap = lastSwapIndex;
            for (int j = 0; j < currentLastSwap; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                    // 更新最后一次交换的位置
                    lastSwapIndex = j;
                }
            }
            // 没有发生交换，直接退出
            if (!swapped) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] testArr = {5, 1, 3, 2, 4};
        bubbleSort(testArr);
        for (int num : testArr) {
            System.out.print(num + " ");
        }
    }
}

这种优化进一步缩小了每轮的比较范围，在序列中存在部分有序区域的情况下，能进一步减少不必要的比较操作。

优化前后性能对比

我们可以通过一个简单的测试来对比三种冒泡排序的比较次数，假设待排序数组为{5, 3, 8, 4, 2}：

如果待排序数组为{1, 2, 3, 4, 5}（已经有序）：

可以看出，在序列本身有序的场景下，优化后的冒泡排序能明显减少比较次数，提升执行效率。

冒泡排序的适用场景

冒泡排序虽然时间复杂度较高，但是它的实现逻辑非常简单，不需要额外的存储空间，在待排序序列长度很小，或者对排序效率要求不高的场景下，仍然是一个可用的选择。同时它也是学习排序算法的基础，能帮助开发者理解排序的核心逻辑和算法优化的思路。

冒泡排序排序算法算法优化时间复杂度修改时间：2026-07-21 02:48:30