python 冒泡排序|极客教程

python 冒泡排序

冒泡排序是一种简单且经典的排序算法，它重复地遍历要排序的列表，一次比较两个元素，如果它们的顺序错误就交换它们。这个过程持续直到没有需要交换的元素，也就是列表已经排序好了。

算法原理

冒泡排序的算法原理可以简单概括为以下几步：

从第一个元素开始，比较相邻的元素，如果第一个元素比第二个元素大，则交换它们的位置。
继续向后比较相邻的元素，依次类推，直到最后一个元素，此时最大的元素已经到达列表的末尾。
回到起始位置，重复上述步骤，但不再考虑已经排好序的元素。
重复以上步骤，直到所有元素都排好序。

示例代码

下面是使用Python实现冒泡排序的示例代码：

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

# 测试示例
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print("排序前的列表:", arr)
print("排序后的列表:", sorted_arr)

运行上述代码，可以得到以下结果：

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

以上代码中，我们定义了一个名为bubble_sort的函数，它接受一个列表作为输入，并返回排序好的列表。在函数内部，我们使用嵌套的for循环来实现冒泡排序的逻辑。外部循环控制每轮比较的次数，内部循环则负责实际比较和交换元素的操作。

算法复杂度分析

冒泡排序是一种简单直观的排序算法，但其时间复杂度是 $O(n^2)$ ，空间复杂度为 $O(1)$ ，其中 $n$ 是待排序列表的长度。在最坏情况下，即列表已经是倒序排列的情况下，冒泡排序的性能表现最差。

总的来说，冒泡排序适用于数据量较小或者是基本有序的情况下。对于大规模数据集合或者对性能有较高要求的场景，通常不推荐使用冒泡排序。

总结

冒泡排序是最经典的排序算法之一，其实现简单、易于理解。虽然性能不如其他高级算法，但对于小规模数据集合来说，仍然是一个有效的选择。熟悉冒泡排序的原理和实现，可以帮助我们更好地理解算法设计和效率分析的基本概念。

python 冒泡排序