首页 > 代码库 > 冒泡排序
冒泡排序
冒泡排序
排序思路:
将列表每两个相邻的数对比,如果前边的比后边的大,那么交换这两个数直到将最大的数放至最右侧。
时间复杂度为:
O(n2)
import random import time def cal_time(func): """ 测试时间装饰器 :param func: 接收一个函数 :return: """ def wrapper(*args, **kwargs): ti = time.time() x = func(*args, **kwargs) ti2 = time.time() print("time cost:", func.__name__, ti2 - ti) return x return wrapper @cal_time def bubble_sort(li): """ 冒泡排序 :param li: 列表 :return: """ for i in range(len(li) - 1): for j in range(len(li) - i - 1): if li[j] > li[j + 1]: li[j], li[j+1] = li[j+1], li[j] data = list(range(999, 1500)) # 将顺序打乱 random.shuffle(data) print(data) # [944, 664, 701, 110, 482, 968, 108, 465, 246, 902, 216, 171, 361, 734, 242, 138, 914, 620, 923, 393,] bubble_sort(data) print(data) -------------------------------------执行结果--------------------------------------- # time cost: bubble_sort 0.04400277137756348 # [999, 1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008, 1009, 1010, 1011, 1012, 1013, 1014, 1015,]
冒泡排序之优化
优化说明:如果冒泡排序中执行一趟而没有交换,则列表已经是有序状态,可以直接结束算法。
@cal_time def bubble_sort_1(li): """ 冒泡排序之优化 :param li: 列表 :return:None """ for i in range(len(li) - 1): change = False for j in range(len(li) - i - 1): if li[j] > li[j + 1]: li[j], li[j+1] = li[j+1], li[j] change = True if not change: break data = list(range(10000)) random.shuffle(data) bubble_sort_1(data) bubble_sort(data) -------------------------------执行结果时间差----------------------- time cost: bubble_sort_1 0.011000633239746094 time cost: bubble_sort 19.759130239486694
冒泡排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。