为什么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变量的判断、赋值代价，实测比原始冒泡排序算法要慢不少。

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