冒泡排序算法详解：原理、实现与复杂度分析

冒泡排序算法详解：原理、实现与复杂度分析

冒泡排序是一种简单直观的比较型排序算法，通过重复遍历待排序序列、比较相邻元素并交换位置（若顺序错误），最终将序列按指定顺序排列。其核心思想是让较大的元素逐渐“冒泡”到序列末尾。

算法步骤

1. 从第一个元素开始，依次比较相邻两个元素，如果前一个大于后一个，则交换它们的位置。
2. 对每一对相邻元素重复上述过程，直到最后一对元素比较完成，此时最大元素会移动到数组末尾。
3. 重复以上步骤，但每次遍历时减少已排序部分的比较次数，直至整个数组有序。

例如，对于序列 [4, 3, 8, 1] 进行升序排序：

• 第一轮：(4,3), (4,8), (8,1)，得到 [3, 4, 1, 8]
• 第二轮：(3,4), (4,1)，得到 [3, 1, 4, 8]
• 第三轮：(3,1), (3,4)，得到 [1, 3, 4, 8]
• 第四轮：没有进行交换，序列保持不变

Python代码实现

def bubble_sort(li: list) -> list:
    """冒泡排序 升序"""
    for i in range(len(li) - 1):  # 决定遍历多少趟， n-1趟
        flag = False  # 标识 是否进行元素交换，未发生交换则表明数组已然是有序得了，后续就不在执行剩余趟
        for j in range(len(li) - i - 1):  # 相邻两元素的索引，不大于n-1，且为无序区长度-1
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j + 1], li[j]
                flag = True
        if not flag:
            return
        print('第' + str(i) + '趟：', li)

if __name__ == '__main__':
    nums = [1, 5, 8, 9, 10, 4, 6, 13, 0]    # 执行全部n-1趟
    print('原数组：', nums)
    bubble_sort(nums)

时间复杂度与空间复杂度

• 时间复杂度：最好情况下为O(n)（当输入数据基本有序时），最坏和平均情况均为O(n^2)。
• 空间复杂度：O(1)，属于原地排序算法。

稳定性

冒泡排序是一种稳定的排序算法，在排序过程中相同大小的元素不会改变相对位置。例如，当两个相同元素在一起时，不会发生交换，从而保持其原始顺序。

应用场景与局限性

尽管冒泡排序效率较低，但在以下场景中仍具实用价值：

• 小规模数据集：数据量较小时，实现简单且占用内存少的优势明显。
• 教学与演示：逻辑清晰，易于理解，常用于教授基础排序原理。
• 嵌入式系统：资源受限环境下，因其实现简单而成为优选。

然而，对于大规模数据排序，冒泡排序的O(n^2)时间复杂度使其效率低下，此时应选择更高效的排序算法，如快速排序、归并排序等。

与其他排序算法的对比

• 插入排序：同样是O(n^2)时间复杂度，但插入排序在部分有序数据上表现更好。
• 选择排序：同样是O(n^2)时间复杂度，但选择排序通过减少交换次数来提高效率。
• 快速排序：平均时间复杂度为O(n log n)，在大多数情况下效率更高。

冒泡排序以其易理解性和简易性成为初学者学习排序算法的良好起点。虽然它在大规模数据处理中的效率较低，但在特定场景下依然有其独特优势。