冒泡排序
冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小,再根据结果交换两个数字
的位置”这一操作的算法。在这个过程中,数字会像泡泡一样,慢慢从右往左“浮”到序列的
顶端,所以这个算法才被称为“冒泡排序”。
- 比较相邻元素, 如果第一个比第二个大, 就交换他们两个
- 对每一对相邻的元素做同样的工作, 执行完毕后, 找到第一个最大值
- 重复以上步骤, 每次比较 次数 - 1, 直到不需要比较
在冒泡排序中,第 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))