Python实现冒泡排序算法的两种方法

Python实现冒泡排序算法有两种方法，分别是普通冒泡排序和改进冒泡排序。

普通冒泡排序

普通冒泡排序是一种简单的排序算法。它通过比较相邻元素的值，如果前者大于后者，则交换它们的位置，直到整个序列有序为止。

def bubble_sort(list):
    # 获取列表长度
    length = len(list)
    # 外层循环控制比较轮数
    for i in range(length):
        # 内层循环控制比较次数
        for j in range(1, length-i):
            if list[j-1] > list[j]:
                list[j-1], list[j] = list[j], list[j-1]
    return list

上面的代码就是普通冒泡排序的实现，它的时间复杂度是O(n^2)，空间复杂度是O(1)。

改进冒泡排序

改进冒泡排序是在普通冒泡排序的基础上进行改进的，它在每次排序时记录一次元素交换的位置，作为下次比较的边界，也就是说，每次比较只需要比到这个位置就可以了。

def bubble_sort_2(list):
    # 获取列表长度
    length = len(list)
    # 外层循环控制比较轮数
    for i in range(length):
        # 记录一次交换的位置
        last_exchange_index = 0
        # 内层循环控制比较次数
        for j in range(1, length-i):
            if list[j-1] > list[j]:
                list[j-1], list[j] = list[j], list[j-1]
                # 记录一次交换的位置
                last_exchange_index = j
        # 如果一次交换的位置等于0，说明没有交换，已经排序完成，直接退出
        if last_exchange_index == 0:
            break
    return list

上面的代码就是改进冒泡排序的实现，它的时间复杂度是O(n)，空间复杂度是O(1)。

以上就是，普通冒泡排序和改进冒泡排序，它们的时间复杂度和空间复杂度都不同，可以根据实际情况来选择合适的算法。