八大排序之冒泡排序

概述

百度百科解释：冒泡重复地走访过要排序的元素列，依次比较两个相邻的元素，如 果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素 的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或 降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒 泡排序”。

以[9,5,4,3,2]为例

总结

对一个长度为n的数组进行排序归纳总结如下：

1. 对有n个元素的数组进行排序需要经过n-1轮
2. 第i轮比较的次数为n-i

算法

使用两层循环即可实现我们的冒泡排序的算法：

1. 使用for循环控制排序的轮数,排序的轮数为n-1,n为数组的长度
2. 内层嵌套for循环控制每轮排序的次数,每轮排序的次数为n-i
3. 排序过程中依次比较arr[i]与arr[i+1]如果arr[i]>arr[i+1],交换两者位置
4. 外层循环结束后返回原数组

代码实现

def bubble(arr):
    n = len(arr)
    for i in range(n-1): #控制排序的轮数
        for j in range(n-1-i):#控制排序的次数 
            if arr[j]>arr[j+1]:
                arr[j],arr[j+1] = arr[j+1],arr[j]
    return arr

时间复杂度

冒泡排序一共遍历了n-1 + n-2 + … + 2 + 1 = n * (n-1) / 2 = (n²- n)/2次, 最大的影响 因子是n2 因此冒泡排序总的平均时间复杂度为 O(n²)