设为首页 加入收藏

TOP

大话算法-排序-冒泡排序
2019-09-07 07:09:18 】 浏览:27
Tags:大话 算法 排序 冒泡

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

 


大话算法-排序-冒泡排序 https://www.cppentry.com/bencandy.php?fid=77&id=250293

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇零基础入门学习python--第一章 下一篇[课后作业] 第001讲:我和Python..