编辑“︁冒泡排序（Bubble Sort）”︁

{{Note|本文适用于编程初学者及需要复习排序算法的开发者。内容涵盖基础理论、实现代码、复杂度分析及优化策略。}}

= 冒泡排序（Bubble Sort） =
冒泡排序是一种简单的'''比较排序算法'''，通过重复遍历待排序列表，依次比较相邻元素并交换位置，使较大（或较小）元素逐渐“浮”到列表末端。因其排序过程中元素像气泡一样上浮而得名。

== 算法原理 ==
=== 核心思想 ===
1. '''相邻比较'''：从列表首部开始，比较相邻的两个元素。
2. '''交换条件'''：若前一个元素大于后一个元素（升序排序时），则交换它们的位置。
3. '''遍历终止'''：每一轮遍历会将当前未排序部分的最大元素移动到正确位置，下一轮遍历范围减少一位。

=== 动态示例 ===
<mermaid>
graph TD
    A[初始列表: 5, 3, 8, 4, 2] --> B[第一轮遍历]
    B --> C[比较5和3: 交换 → 3,5,8,4,2]
    C --> D[比较5和8: 不交换]
    D --> E[比较8和4: 交换 → 3,5,4,8,2]
    E --> F[比较8和2: 交换 → 3,5,4,2,8]
    F --> G[第二轮遍历范围: 3,5,4,2]
</mermaid>

== 代码实现 ==
以下是Python实现的冒泡排序代码：

<syntaxhighlight lang="python">
def 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

# 示例
input_list = [64, 34, 25, 12, 22, 11, 90]
print("排序前:", input_list)
print("排序后:", bubble_sort(input_list))
</syntaxhighlight>

'''输出结果：'''
<pre>
排序前: [64, 34, 25, 12, 22, 11, 90]
排序后: [11, 12, 22, 25, 34, 64, 90]
</pre>

== 复杂度分析 ==
{| class="wikitable"
|+ 时间复杂度与空间复杂度
! 情况 !! 时间复杂度 !! 说明
|-
| 最优情况（已有序） || <math>O(n)</math> || 通过'''swapped标志'''提前退出
|-
| 平均情况 || <math>O(n^2)</math> || 嵌套循环导致平方级复杂度
|-
| 最差情况（逆序） || <math>O(n^2)</math> || 需完全执行所有比较
|-
| 空间复杂度 || <math>O(1)</math> || 原地排序，仅需常数空间
|}

== 优化策略 ==
1. '''提前终止'''：若某轮遍历未发生交换，说明列表已有序。
2. '''记录最后交换位置'''：下一轮遍历只需到该位置即可。

== 实际应用场景 ==
* '''教学工具'''：因逻辑简单，常用于算法入门教学。
* '''小规模数据'''：当数据量极小（如<math>n < 50</math>）时，可能优于复杂排序算法。
* '''部分有序数据'''：若列表基本有序，优化后的冒泡排序效率接近<math>O(n)</math>。

== 与其他排序算法对比 ==
* '''优点'''：实现简单、空间效率高。
* '''缺点'''：大规模数据性能差，不适合实际生产环境。

{{Warning|冒泡排序在'''LeetCode'''等算法题中可能因超时被拒，需谨慎使用！}}

== 练习问题 ==
# 手动模拟冒泡排序对列表 `[7, 3, 9, 2, 5]` 的排序过程。
# 尝试用其他编程语言（如Java/C++）实现冒泡排序。

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:排序算法]]