冒泡排序优于选择排序大幅度

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秒
SS结果:63.618秒

并且10000次迭代的1000个数字的数组 -
BS结果:2.074秒
SS结果:645.944秒

这些算法的实施是否存在问题,或者预计存在如此大的差异？我知道还有其他更快的排序,在实践中没有人会真正使用BS或SS,但我只是想了解为什么SS看起来比BS慢得多？

Answer 1

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

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