在python中对列表进行冒泡排序最有效吗？

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了在python中对列表进行冒泡排序最有效吗？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2695字，纯文字阅读大概需要4分钟。

内容图文

我正在尝试查看这是否是在python中对气泡列表进行排序的最有效方法,或者是否有人有更好的方法告诉我使用两个循环,这样做与下面相比有什么好处？

def sort_bubble(blist):
    n = 0
    while n < len(blist) - 1:
        if blist[n] > blist[n + 1]:
            n1 = blist[n]
            n2 = blist[n + 1]
            blist[n] = n2
            blist[n + 1] = n1
            n = 0
        else:
            n = n + 1
    print blist

解决方法:

从技术上来说,您的算法是一种冒泡排序,因为它完全可以进行应有的交换.但是,这是一种非常低效的冒泡排序,因为它所做的比较超出了必要.

你怎么知道检测代码以计算比较和交换的数量非常容易.同时,Wikipedia使用伪代码语言提供了一种简单的冒泡排序的实现,以及带有跳过排序的尾部优化的实现,该伪代码语言很容易移植到Python和类似的工具.我将在底部显示代码.

对于一个完美的冒泡排序,给定一个长度为100的随机列表,您应该期望比较值小于10000(100 * 100),而交换值小于2500.而Wikipedia实现正是这样做的. “跳过排序的尾巴”版本应该具有比比较多一半的数字,而且确实如此.

但是,您的比较结果是应有结果的10倍.您的代码效率低下的原因是,它从头开始一遍又一遍地开始,而不是在任何可能的地方从头开始交换.这导致了一个额外的因数O(sqrt(N)).

同时,对于几乎所有输入,几乎任何排序算法都比冒泡排序更好,因此,即使有效的冒泡排序也不是有效的排序.

我对您的代码做了一个小的更改：用更惯用的单行交换替换四行交换.否则,除了添加cmpcount和swapcount变量并返回结果而不是打印结果之外,什么都不会改变.

def bogo_bubble(blist):
    cmpcount, swapcount = 0, 0
    n = 0
    while n < len(blist) - 1:
        cmpcount += 1
        if blist[n] > blist[n + 1]:
            swapcount += 1
            blist[n], blist[n+1] = blist[n+1], blist[n]
            n = 0
        else:
            n = n + 1
    return blist, cmpcount, swapcount

这是Wikipedia的Psuedocode implementation,已翻译为Python.我不得不用一会儿True来代替重复…单元…如果不是…：打破,但是其他一切都是微不足道的.

def wp1_bubble(blist):
    cmpcount, swapcount = 0, 0
    while True:
        swapped = False
        for i in range(1, len(blist)):
            cmpcount += 1
            if blist[i-1] > blist[i]:
                swapcount += 1
                blist[i-1], blist[i] = blist[i], blist[i-1]
                swapped = True
        if not swapped:
            break
    return blist, cmpcount, swapcount

这是Optimizing bubble sort,它执行的是跳过排序的尾部优化的简单版本,而不是更复杂的版本(紧随其后).

def wp2_bubble(blist):
    cmpcount, swapcount = 0, 0
    n = len(blist)
    while True:
        swapped = False
        for i in range(1, n):
            cmpcount += 1
            if blist[i-1] > blist[i]:
                swapcount += 1
                blist[i-1], blist[i] = blist[i], blist[i-1]
                swapped = True
        n -= 1
        if not swapped:
            break
    return blist, cmpcount, swapcount

import random
alist = [random.randrange(100) for _ in range(100)]
bb, cb, sb = bogo_bubble(alist[:])
b1, c1, s1 = wp1_bubble(alist[:])
b2, c2, s2 = wp2_bubble(alist[:])
assert bb == b1 == b2
print('bogo_bubble: {} cmp, {} swap'.format(cb, sb))
print('wp1_bubble : {} cmp, {} swap'.format(c1, s1))
print('wp2_bubble : {} cmp, {} swap'.format(c2, s2))

典型输出：

bogo_bubble: 100619 cmp, 2250 swap
wp1_bubble : 8811 cmp, 2250 swap
wp2_bubble : 4895 cmp, 2250 swap

内容总结

以上是互联网集市为您收集整理的在python中对列表进行冒泡排序最有效吗？全部内容，希望文章能够帮你解决在python中对列表进行冒泡排序最有效吗？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---