冒泡排序算法

介绍

冒泡排序（Bubble Sort）是一种简单直观的排序算法，其基本思想是：在待排序的一组数中，将相邻的两个数进行比较，若前面的数比后面的数大就交换两数，否则不交换；如此重复遍历下去，直到没有再需要交换的元素，最终完成排序。由此可得，在排序过程中，大的数据往下沉，小的数据往上浮，就像水中气泡上升一样，于是将这种排序算法形象地称为冒泡排序。

算法步骤

比较相邻的元素。如果第一个比第二个大，就交换它们
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对
这步做完后，最后的元素会是最大的数
针对所有的元素重复以上的步骤，除了已经是最大数的最后一个
持续每次对越来越少(每次重复都会少一个最大数)的元素重复上面的步骤，直到没有任何一对数字需要比较

核心特性

稳定性：冒泡排序是稳定的排序算法，相等元素的相对位置在排序后不会改变
原地排序：只需要常数级的额外空间
时间复杂度：最坏和平均情况为O(n²)，最好情况为O(n)
比较排序：基于元素间的比较进行排序

基础实现

接下来大家一起看下冒泡排序的几个主流语言实现：

代码实现

▼
text
复制代码
public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            // 每次遍历后，最大的i+1个元素已经排好序
            for (int j = 0; j < n - i - 1; j++) {
                // 如果当前元素大于下一个元素，则交换
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
    
    // 打印数组
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
    
    // 测试
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("排序前的数组：");
        printArray(arr);
        
        bubbleSort(arr);
        
        System.out.println("排序后的数组：");
        printArray(arr);
    }
}

优化版本

如果是一个已经排好序的数组，上述代码也会循环执行，我们可以针对这一点进行如下优化：

▼
java
复制代码
public static void optimizedBubbleSort(int[] arr) {
    int n = arr.length;
    boolean swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - i - 1; 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;
        }
    }
}

优缺点

优点

代码简单，容易实现
适合小规模数据排序
对于几乎已经排好序的数据，效率较高
稳定的排序算法

缺点

时间复杂度高，为O(n²)
随着元素数量增加，效率急剧下降
每次只能将一个元素移动到其最终位置，效率不高

应用场景

由于效率问题，冒泡排序的应用场景比较少，不过也不是完全没有，比如：

教学演示：简单直观，常用于算法入门教学
小规模数据排序：当数据量较小、空间资源有限时可以使用
对于接近有序的数组：有优化版本可以在接近有序的情况下提前终止
嵌入式系统或资源受限环境：因为它不需要额外的内存空间

扩展

鸡尾酒排序（双向冒泡排序）

鸡尾酒排序是冒泡排序的一种变体，它从低到高然后从高到低来回排序，比冒泡排序的效率稍微高一点：

▼
java
复制代码
public static void cocktailSort(int[] arr) {
    boolean swapped = true;
    int start = 0;
    int end = arr.length - 1;
    
    while (swapped) {
        // 从左到右
        swapped = false;
        for (int i = start; i < end; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                swapped = true;
            }
        }
        
        // 如果没有交换，则已经排序完成
        if (!swapped)
            break;
            
        // 否则重置swapped标志准备从右到左
        swapped = false;
        end--;
        
        // 从右到左
        for (int i = end - 1; i >= start; i--) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                swapped = true;
            }
        }
        
        start++;
    }
}

测验

冒泡排序的平均时间复杂度是多少？
冒泡排序是稳定的排序算法吗？
对于已经排好序的数组，优化版冒泡排序的时间复杂度是多少？
冒泡排序每一轮遍历后，数组尾部会有什么特点？
如何优化冒泡排序以提高效率？

测验答案

冒泡排序的平均时间复杂度是O(n²)。

是的，冒泡排序是稳定的排序算法。因为只有当前一个元素大于后一个元素时才交换，相等元素不会改变相对位置。

对于已经排好序的数组，优化版冒泡排序的时间复杂度是O(n)。因为第一轮遍历不会发生交换，优化版会检测到这点并提前终止。

冒泡排序每一轮遍历后，数组尾部会有一个元素到达其最终位置，且是当前未排序部分中的最大元素。第i轮结束后，末尾i个元素已排好序。

优化冒泡排序的方法:

添加标志位跟踪是否发生交换，无交换则提前终止

记录最后一次交换位置，下一轮只遍历到该位置

使用双向冒泡(鸡尾酒排序)，同时将最大值上浮和最小值下沉

一文带你学会"冒泡排序"