冒泡排序多种写法，python

冒泡排序是一种基本的排序算法，它的思路是不断比较相邻的两个元素，如果顺序不对就交换位置，直到最后一个元素。以下是几种不同的 Python 冒泡排序实现方法：

1. 普通的冒泡排序写法

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

2. 优化版 1：增加 flag 标志，如果某一轮没有交换，说明已经有序了，可以提前结束循环。

def bubble_sort_v1(arr):
    n = len(arr)
    for i in range(n - 1):
        flag = False
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                flag = True
        if not flag:
            break
    return arr

3. 优化版 2：记录最后一次交换的位置，因为该位置后的元素已经是有序的了，下一轮循环不需要再比较。

def bubble_sort_v2(arr):
    n = len(arr)
    last_swap = n - 1
    for i in range(n - 1):
        flag = False
        for j in range(last_swap):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                flag = True
                last_swap = j
        if not flag:
            break
    return arr

4. 递归版本：每次调用递归函数时，将待排序的数组长度减 1，直到长度为 1。

def bubble_sort_v3(arr, n=None):
    if n is None:
        n = len(arr)
    if n == 1:
        return arr
    for i in range(n - 1):
        if arr[i] > arr[i + 1]:
            arr[i], arr[i + 1] = arr[i + 1], arr[i]
    return bubble_sort_v3(arr, n - 1)

以上是几种不同的冒泡排序实现方法，它们的时间复杂度都是 O(n^2)，但是优化后的版本能够在特定情况下提高排序效率。