冒泡排序

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

算法原理[编辑 | 编辑源代码]

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

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

时间复杂度[编辑 | 编辑源代码]

最坏情况： $O (n^{2})$ （列表完全逆序）
平均情况： $O (n^{2})$
最好情况： $O (n)$ （列表已经有序，且优化后的算法可以提前终止）

算法步骤[编辑 | 编辑源代码]

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

伪代码示例[编辑 | 编辑源代码]

  
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  // 如果没有发生交换，说明列表已经有序

代码实现[编辑 | 编辑源代码]

以下是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)

输出：

  
排序后的列表: [11, 12, 22, 25, 34, 64, 90]

逐步解析[编辑 | 编辑源代码]

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