冒泡排序

冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字
的位置”这一操作的算法。在这个过程中，数字会像泡泡一样，慢慢从右往左“浮”到序列的
顶端，所以这个算法才被称为“冒泡排序”。

• 1. 比较相邻元素， 如果第一个比第二个大， 就交换他们两个
• 2. 对每一对相邻的元素做同样的工作， 执行完毕后， 找到第一个最大值
• 3. 重复以上步骤， 每次比较 次数 - 1， 直到不需要比较

image
image
image
image
image
image
image
image

在冒泡排序中，第 1 轮需要比较 n -1 次，第 2 轮需要比较 n -2 次……第 n -1 轮需
要比较 1 次。因此，总的比较次数为 (n -1) +(n -2) +…+1 ≈ n^2
/2。这个比较次数恒定为该数值，和输入数据的排列顺序无关。
不过，交换数字的次数和输入数据的排列顺序有关。假设出现某种极端情况，如输
入数据正好以从小到大的顺序排列，那么便不需要任何交换操作；反过来，输入数据要
是以从大到小的顺序排列，那么每次比较数字后便都要进行交换。因此，冒泡排序的时
间复杂度为 O(n^2)。
一层循环/右侧开始版

arr = [5, 9, 3, 1, 2, 8, 4, 7, 6]
def BubbleSort(arr:list)->list:
    num = 0
    for i in range(0, len(arr)-1):
        for j in range(len(arr) - 1, i, -1):
            num +=1
            if arr[j - 1] > arr[j]:
                arr[j - 1], arr[j] = arr[j], arr[j - 1]
    print(num)
    return arr
print(BubbleSort(arr))