为何添加标志位的冒泡排序并没有提高实际效率？

Question

刚开始学习Python，就想用它简单实现一下以前学习过的数据结构与算法，一上来就遇到了冒泡排序的问题，因为冒泡排序常见的有两种，普通的以及使用标志位减少比较次数的，下面是我用Python3对它们的实现：

@time_usage
def bubdle_sort1(lists):
    """冒泡排序"""
    if list_check(lists) is False:
        return lists

    for i in range(len(lists) - 1):
        for j in range(len(lists) - i - 1):
            if lists[j] > lists[j + 1]:
                lists[j], lists[j + 1] = lists[j + 1], lists[j]
    return lists


@time_usage
def bubdle_sort2(lists):
    """冒泡排序添加标志位版本"""

    if list_check(lists) is False:
        return lists

    for i in range(len(lists) - 1):
        flag = True
        for j in range(len(lists) - i - 1):
            if lists[j] > lists[j + 1]:
                lists[j], lists[j + 1] = lists[j + 1], lists[j]
                flag = False
        if flag:
            return lists
    return lists

其中time_usage是用来计算函数执行时间的装饰器，list_check是参数检查用的，理论上第二种冒泡排序的效率会高一些，但是实际执行时却并非如此，下面是在0~20000中取10000个随机整数的排序时间:

多次比较之后，第二种总是比第一种慢一点点。为了参照，我又用c++实现后作为对比，结果依然如此，这是30000个随机整数的排序时间：

多次排序后的结果依然如此，和预期结果并不相符，请问问题出在哪里呢？

Answer 1

你那个flag，只有当大部分数都排好序的时候才用得上。随机取10000个数的话不太可能遇到这种情况。相反每次循环都要花时间判断flag，所以总体是得不偿失。