为什么shortBubbleSort反倒比BubbleSort慢?

来自宋欣源同学的问题:

我试了一下排序算法,发现shortBubbleSort比BubbleSort慢很多啊(每组数据运行10次取平均),算法就是照着幻灯片上写的,为什么呢?

代码如下:


def BubbleSort(alist):
    passnum = len(alist) - 1
    while passnum > 0:
        for i in range(passnum):
            if alist[i] > alist[i + 1]:
                alist[i],alist[i + 1] = alist[i + 1],alist[i]
        passnum -= 1
    return alist
        
def ShortBubbleSort(alist):
    exchanges = True
    passnum = len(alist) - 1
    while passnum > 0 and exchanges:
        exchanges = False
        for i in range(passnum):
            if alist[i] > alist[i + 1]:
                exchanges = True
                alist[i],alist[i + 1] = alist[i + 1],alist[i]
        passnum -= 1
    return alist

测试数据是这样的:

alist = [i for i in range(100) for j in range(50)]
random.shuffle(alist)

回答:

这是个很好的问题!涉及到算法性能的比较问题,如何选择一个好的算法?

实际上,ShortBubbleSort的“短路”优势高度依赖于数据的初始布局,如果数据布局的随机度很高,基本上每趟都会交换的话,ShortBubbleSort就完全没有优势了,还要额外付出一个exchanges变量和相应赋值语句的代价,反倒比原始的冒泡排序要慢。

宋同学的代码没有问题,问题在于排序对象,其数据是经过random.shuffle来乱序的,首先,alist是用range嵌套生成的,生成后的数据从小到大排列,非常整齐;而这个shuffle会尽量把数据打乱到最混乱的程度,造成数据布局随机度很高,这样,ShortBubbleSort的短路特性就完全失效,还要付出exchanges变量的判断、赋值代价,实测比原始冒泡排序算法要慢不少。

所以排序算法有时候并不能讲绝对的优劣,尤其是时间复杂度相同的算法们,要在特定的应用场合取得最高排序性能的话,还是需要对数据本身进行分析,针对数据的特性来选择相应排序算法。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

*

*

code