冒泡排序算法（Python）

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。

它重复地走过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

用一个动图来解释一下

 

代码实现：

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

lst=list(range(100))
import random
random.shuffle(lst)
print(lst)
bubble_sort(lst)
print(lst)

结果为：

注意：

i循环len(lst)-1次 可以这样理解 8个数只用排7次 最后一个数自动排好

j 循环的意义为：

由于最左侧的值已经有序，不再比较，每次都减少遍历次数

什么时候最快

当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊）。

什么时候最慢

当输入的数据是反序时（写一个 for 循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗）。

时间复杂度最差的情况为O(n^2) 

第一层for

执行了n次

第二层for

第一次比较了n-1次

第二次比较了n-2次

....

第n-1次比较了1次

所以最差情况的时间复杂度为O(n^2)

最好的情况时间复杂度是O(n)

列表是排好序的状态，但第一次for循环还是要遍历一层列表，所以时间复杂度为O(n)

🌸🌸🌸🌸🌸🌸完结撒花！🌸🌸🌸🌸🌸🌸

如有疑问或错误，欢迎大家评论区留言指出，谢谢支持！！