冒泡排序算法

简介

冒泡排序是一种简单的排序算法，它通过重复遍历要排序的列表，比较每对相邻元素，并在必要时交换它们的位置。这个名称由于较小或较大的元素会逐渐“冒泡”到列表的一端而得名。

算法原理

冒泡排序重复地遍历列表，比较相邻的元素。如果一对元素的顺序错误，则将它们交换。每次遍历列表后，最大的元素将“冒泡”到列表的末尾。

Python 实现示例

lst = [1, 9, 8, 11, 6, 3, 4, 10, 5, 2, 7]
length = len(lst)
for i in range(length):
    for j in range(length - 1 - i):
        if lst[j] > lst[j + 1]:
            lst[j], lst[j + 1] = lst[j + 1], lst[j]
print(lst)

排序过程

1. 初始列表: [1, 9, 8, 11, 6, 3, 4, 10, 5, 2, 7]

2. 第一轮: [1, 8, 9, 6, 3, 4, 10, 5, 2, 7, 11]

3. 第二轮: [1, 8, 6, 3, 4, 9, 5, 2, 7, 10, 11] ...

4. 最终结果: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

性能分析

• 时间复杂度：平均和最坏情况为 O(n^2)，最好情况为 O(n)。

• 空间复杂度：O(1)，因为它是原地排序。

适用场景和局限性

适用于元素数量较少的列表。由于其平均和最坏情况的时间复杂度较高，不适用于大量数据的排序。

总结

冒泡排序是理解排序概念的一个很好的入门选择，它的简单性使其成为排序算法中最容易理解和实现的算法之一。