【0】冒泡排序

**冒泡排序**

冒泡排序是一种简单的排序算法，通过反复地遍历列表并相邻元素之间进行比较来实现。它的名字来源于水中气泡上升的过程，类似于冒泡排序中的元素不断向上"冒"到正确位置。

**基本原理**

冒泡排序的基本原理是：每次遍历列表时，将最小或最大元素移动到列表的起始位置。这样一来，每次遍历后，列表中最小或最大元素都已经排好序了。

**算法步骤**

1. **首先，我们需要将列表中的元素进行比较，以确定哪个元素是最小或最大。**
2. **然后，我们交换列表中相邻的两个元素，使得较小或较大的元素移动到列表的起始位置。**
3. **重复步骤1和2，直到整个列表都排好序为止。**

**代码示例**

def bubble_sort(arr):
 """
 冒泡排序算法 Args:
 arr (list): 需要排序的列表 Returns:
 list: 排序后的列表 """
 n = len(arr)
 # 重复遍历列表，直到整个列表都排好序为止 for i in range(n-1):
 # 初始化一个标志位，表示是否有元素交换过 swapped = False # 遍历列表中的每个元素 for j in range(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 return arr# 测试冒泡排序算法arr = [64,34,25,12,22,11,90]
print("原始列表：", arr)
print("排序后列表：", bubble_sort(arr))

**注释**

* `bubble_sort`函数是冒泡排序算法的实现。
* `arr`参数是需要排序的列表。
* `n`变量存储了列表中的元素数量。
* `swapped`变量用于标志是否有元素交换过。
* `i`和`j`变量分别表示当前遍历的轮数和位置。
* `arr[j] > arr[j+1]`条件判断语句检查当前元素是否大于下一个元素。如果是，则进行元素交换。

**时间复杂度**

冒泡排序算法的时间复杂度为 O(n^2)，其中 n 是列表中的元素数量。这种情况下，算法的性能会随着列表长度的增长而明显恶化。

**空间复杂度**

冒泡排序算法的空间复杂度为 O(1)，因为它只需要常数个额外的存储空间来保存一些临时变量。

**总结**

冒泡排序是一种简单的排序算法，通过反复地遍历列表并相邻元素之间进行比较来实现。虽然它的时间复杂度较高，但在某些特定场景下仍然是一个有效的选择。