【算法】冒泡排序

用户11456817

发布于 2025-02-25 15:00:56

5010

文章被收录于专栏：学习学习

一、算法概述

冒泡排序（Bubble Sort）是最经典的排序算法之一，其名称源于元素移动方式如同水中气泡上浮的过程。这个简单直观的算法诞生于1956年，至今仍是计算机科学入门教育的经典案例。

二、算法原理

1. 核心思想

通过相邻元素的比较和交换，使较大元素逐步"浮"到数列末端。每一轮排序将确定一个元素的最终位置，类似于气泡从水底升到水面。

2. 排序过程演示

以数组 [5, 3, 8, 1, 2] 为例：

初始：5 3 8 1 2
第1轮：
3 5 8 1 2 → 比较5和3
3 5 1 8 2 → 比较8和1
3 5 1 2 8 → 比较8和2（确定最大值8）

第2轮：
3 1 5 2 8 → 比较5和1
3 1 2 5 8 → 比较5和2（确定次大值5）

第3轮：
1 3 2 5 8 → 比较3和1
1 2 3 5 8 → 比较3和2（确定中间值3）

第4轮：
1 2 3 5 8 → 比较2和1（完全有序）

三、标准实现代码

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # 每次减少比较范围
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

四、时间复杂度分析

最好情况（已有序）：O(n) （优化版）
平均情况：O(n²)
最坏情况（完全逆序）：O(n²)

空间复杂度：O(1)（原地排序）

五、优化策略

1. 提前终止优化

def optimized_bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

2. 记录最后交换位置

def improved_bubble_sort(arr):
    n = len(arr)
    last_swap = n - 1
    while last_swap > 0:
        new_swap = 0
        for j in range(last_swap):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                new_swap = j
        last_swap = new_swap
    return arr

六、算法特性

稳定性：稳定排序（相同元素相对位置不变）
适用场景：
- 小规模数据排序
- 教学演示用途
- 数据基本有序时表现良好
缺点：
- 大规模数据效率低下
- 元素移动次数较多

七、实际应用

硬件资源受限的嵌入式系统
图形界面中的简单数据排序
其他排序算法的基准测试对比
链表数据的排序（相比数组更具优势）

八、扩展思考

双向冒泡排序（鸡尾酒排序）：交替进行正向和反向遍历
结合插入排序的混合算法
并行化处理的可能性

九、总结

冒泡排序虽不是最高效的排序算法，但其简明性使其成为：

理解排序思想的绝佳范例
算法优化的典型研究对象
其他高级排序算法的基础参照

在真实开发中，当数据规模超过1000时建议使用更高效的算法（如快速排序、归并排序）。但对于算法学习者，深入理解冒泡排序将有助于建立基础的算法思维模式。

附录：不同语言实现示例

// Java实现
public static void bubbleSort(int[] arr) {
    boolean swapped;
    for (int i = 0; i < arr.length-1; i++) {
        swapped = false;
        for (int j = 0; j < arr.length-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;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-02-24，如有侵权请联系 cloudcommunity@tencent.com 删除

算法