编辑“︁冒泡排序”︁

{{DISPLAYTITLE:冒泡排序}}  
'''冒泡排序'''（Bubble Sort）是一种简单的排序算法，通过重复比较相邻元素并交换它们的位置来将列表按升序或降序排列。因其排序过程中较小的元素会逐渐“浮”到列表顶端（像气泡一样上升），故得名“冒泡排序”。  

== 算法原理 ==  
冒泡排序的核心思想是：  
1. 从列表的第一个元素开始，依次比较相邻的两个元素。  
2. 如果它们的顺序错误（例如前一个元素大于后一个元素），则交换它们的位置。  
3. 重复上述步骤，直到列表完全有序。  

每次完整的遍历列表称为“一轮”，每轮结束后，最大的未排序元素会被移动到正确的位置。  

=== 时间复杂度 ===  
* 最坏情况：<math>O(n^2)</math>（列表完全逆序）  
* 平均情况：<math>O(n^2)</math>  
* 最好情况：<math>O(n)</math>（列表已经有序，且优化后的算法可以提前终止）  

== 算法步骤 ==  
以下是一个升序排序的步骤分解：  
1. 比较第1个和第2个元素，如果第1个更大，则交换它们。  
2. 比较第2个和第3个元素，重复上述操作。  
3. 继续比较直到列表末尾。此时，最大的元素会被移动到最后一个位置。  
4. 重复上述过程，但忽略已经排序的末尾部分，直到列表完全有序。  

=== 伪代码示例 ===  
<syntaxhighlight lang="python">  
procedure bubbleSort(list)  
    n = length(list)  
    for i from 0 to n-1  
        swapped = false  
        for j from 0 to n-i-1  
            if list[j] > list[j+1]  
                swap(list[j], list[j+1])  
                swapped = true  
        if not swapped  
            break  // 如果没有发生交换，说明列表已经有序  
</syntaxhighlight>  

== 代码实现 ==  
以下是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  # 提前终止优化  

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

'''输出：'''  
<pre>  
排序后的列表: [11, 12, 22, 25, 34, 64, 90]  
</pre>  

=== 逐步解析 ===  
以输入 <code>[64, 34, 25, 12, 22, 11, 90]</code> 为例：  
1. 第一轮结束后，最大值 90 被移动到末尾：<code>[34, 25, 12, 22, 11, 64, 90]</code>  
2. 第二轮结束后，次大值 64 被移动到倒数第二位：<code>[25, 12, 22, 11, 34, 64, 90]</code>  
3. 重复上述过程，直到列表完全有序。  

== 优化策略 ==  
1. '''提前终止'''：如果某一轮未发生交换，说明列表已有序，可直接退出。  
2. '''记录最后交换位置'''：最后一次交换的位置之后的元素已经有序，下一轮可跳过这部分。  

== 实际应用案例 ==  
冒泡排序虽然效率较低，但在以下场景仍有应用：  
* 教学用途：因其简单性，常用于算法入门教学。  
* 小规模数据排序：当数据量极小时（如 <10 个元素），其实现简单且性能可接受。  
* 部分有序数据：若数据接近有序，优化后的冒泡排序可能比其他 <math>O(n^2)</math> 算法更快。  

== 可视化示例 ==  
<mermaid>  
graph TD  
    A[初始列表: 5, 3, 8, 4, 2] --> B[第一轮: 比较5和3]  
    B --> C[交换 → 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[第一轮结束，8已就位]  
    G --> H[第二轮: 比较3和5 → 不交换]  
    H --> I[比较5和4 → 交换 → 3, 4, 5, 2, 8]  
    I --> J[比较5和2 → 交换 → 3, 4, 2, 5, 8]  
    J --> K[第二轮结束，5已就位]  
    K --> L[...继续直到完全有序]  
</mermaid>  

== 总结 ==  
冒泡排序是一种基础的排序算法，适合初学者理解排序的基本逻辑。尽管其时间复杂度较高，但通过优化（如提前终止）可提升部分场景下的性能。实际开发中，更高效的算法（如快速排序、归并排序）通常优先被采用。

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:排序算法]]