当前位置： 移动技术网 > IT编程>脚本编程>Python > 大话算法-排序-冒泡排序

大话算法-排序-冒泡排序

2019年09月06日  | 移动技术网IT编程  | 我要评论

太阳的后裔观看免费,哈佛商业评论中文网,阳光招生

1、冒泡排序是反复扫描序列，在扫描过程中顺次比较两个元素大小，如果逆序交换位置（如果某一趟冒泡排序中，没有发现一个逆序，则可以直接结束整个排序），

2、最好情况：序列都是正序的，时间复杂度o(n)，比较n-1次 交换0次，

3、最坏的情况：序列完全逆序。时间复杂度是o(n2)，空间复杂度o(1)

 

# 一般方法
def bubble(nlist):
    nlen = len(nlist)
    if nlen == 0:
        return
    if nlen == 1:
        return nlist
    #i表示趟数，最多进行n-1趟    
    for i in range(nlen-1,0,-1):
        for j in range(i):
            if nlist[j] > nlist[j+1]:
                nlist[j],nlist[j+1] = nlist[j+1],nlist[j]
    return nlist

# 优化
def bubble(nlist):
    nlen = len(nlist)
    if nlen == 0:
        return
    if nlen == 1:
        return nlist
    flag = 1
    while flag and nlen:
        #如果哪一趟没有交换（全部顺序），则表示全部排好序（剩下的都排好序不用交换）
        flag = 0
        for j in range(nlen-1):
            # 判断是否有逆序的，如果有调换
            if nlist[j] > nlist[j+1]:
                nlist[j],nlist[j+1] = nlist[j+1],nlist[j]
                flag = 1
        # print(flag,nlen,nlist)
        nlen -= 1
        
    return nlist

 

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网