python-3.x - 冒泡排序大大优于选择排序

Question

我目前正在尝试了解排序算法，并且一直在查看伪代码并将其转换为 python(使用 python 3.6，IDE 是 Spyder 3.1.2)。我写了一个简单的冒泡排序:

def BubbleSort(array_to_sort):
    n = len(array_to_sort) - 1
    swapped = True
    while (swapped):
        swapped = False
        for i in range(n):
             if array_to_sort[i] > array_to_sort[i+1]:
                array_to_sort[i+1], array_to_sort[i] = array_to_sort[i], array_to_sort[i+1] 
                swapped = True
    return array_to_sort

还有一个简单的选择排序:

def SelectionSort(array_to_sort):
    n = len(array_to_sort)
    for i in range(n):
        minPos = i
        for j in range(i+1, n):
            if array_to_sort[j] < array_to_sort[minPos]:
                minPos=j

        if minPos != i:
            array_to_sort[i], array_to_sort[minPos] = array_to_sort[minPos], array_to_sort[i] 

    return array_to_sort

我正在尝试像这样给它们计时:

def main():
    array = RandomNumberArray()
    a = timeit.Timer(functools.partial(BubbleSort, array)) 
    print(a.timeit(1000))
    b = timeit.Timer(functools.partial(SelectionSort, array)) 
    print(b.timeit(1000))

RandomNumberArray 只生成一个我想要排序的数字列表:

def RandomNumberArray():
    return random.sample(range(0, 1000), 1000)

因为它们都具有相同的时间复杂度 O(n²)，我原以为它们花费的时间大致相同，但我发现我的选择排序的性能相对较差到我的冒泡排序，例如对于包含 1000 个数字的数组超过 1000 次迭代 -
BS 结果:0.390 s
SS 结果:63.618 秒

以及经过 10000 次迭代的 1000 个数字的数组 -
BS 结果:2.074 秒
SS 结果:645.944 秒

这些算法的实现是否存在问题，或者是否存在如此大的差异？我知道还有其他更快的分类，实际上没有人会真正使用 BS 或 SS，但我只是想了解为什么 SS 看起来比 BS 慢得多？

Answer 1

这不是一个公平的比较，因为 array 由第一次调用排序，然后传递给第二次调用。有几种排序算法，已经排序的输入是最坏的情况。

冒泡排序也有 O(n) 最佳情况时间复杂度，而选择有 O(n^2) 最佳情况。