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

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

你怎么知道检测代码以计算比较和交换的数量非常容易.同时,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