概述
百度百科解释：冒泡重复地走访过要排序的元素列，依次比较两个相邻的元素，如 果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素 的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或 降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒 泡排序”。
以[9,5,4,3,2]为例
总结
对一个长度为n的数组进行排序归纳总结如下：
- 对有n个元素的数组进行排序需要经过n-1轮
- 第i轮比较的次数为n-i
算法
使用两层循环即可实现我们的冒泡排序的算法：
- 使用for循环控制排序的轮数,排序的轮数为n-1,n为数组的长度
- 内层嵌套for循环控制每轮排序的次数,每轮排序的次数为n-i
- 排序过程中依次比较arr[i]与arr[i+1]如果arr[i]>arr[i+1],交换两者位置
- 外层循环结束后返回原数组
代码实现
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 = (n2- n)/2次, 最大的影响 因子是n2 因此冒泡排序总的平均时间复杂度为 O(n2)
