冒泡排序是比较经典的一种排序方法。冒泡排序主要就是从序列的左端开始重复比较相邻两个元素的大小 根据比较的结果来判断是否需要交换两个元素的位置 最终使得序列元素满足升序或降序排列。
python实现
def bubble_sort(list): # 冒泡排序 n len(list) flag False# 外层循环控制每轮的比较次数 for i in range(n-1): # 内层循环用于比较元素并交换 for j in range(n-i-1): if list[j] list[j 1] list[j],list[j 1] list[j 1], list[j] flag Ture if not flag: break print(list)
另外关于冒泡排序的时间复杂度
情况好时 列表元素按要求顺序排序 则只需要遍历一次列表 时间复杂度为O(n);
情况坏时 列表元素逆序排列 总的比较次数为 n-1 n-2 … 1, 时间复杂度为O n^2 .
如上
