python - 为什么冒泡排序的实现速度明显慢于预期？

Question

我实现了以下代码，但我不知道为什么我认为运行得更快的“快速”冒泡排序实际上运行得比预期慢。在第一个实现中，我认为我浪费了很多时间检查每个数组是否已排序，这需要 O(n) 时间。但在第二个实现中，我在交换数组时检查数组是否已排序，那么为什么第二个实现的运行速度比我想象的要慢？

分配是否比完全迭代列表花费更多时间？

def check_sorted(A):
    for i in xrange(1, len(A)):
        if A[i] < A[i-1]:
            return False

    return True

def bubble_sort(A):
    while not check_sorted(A):
        for i in xrange(1, len(A)):
            if A[i] < A[i-1]:
                A[i], A[i-1] = A[i-1], A[i]

    return A

def bubble_sort_fast(A):
    swap = True
    while swap:
        swap = False
        for i in xrange(1, len(A)):
            if A[i] < A[i-1]:
                A[i], A[i-1] = A[i-1], A[i]
                swap = True
    return A

A = list(reversed(range(5000)))
start_time = time.time()
A = bubble_sort(A)
print 'time_elapsed:', time.time() - start_time

A = list(reversed(range(5000)))
start_time = time.time()
A = bubble_sort_fast(A)
print 'time_elapsed:', time.time() - start_time


time_elapsed: 2.20229792595
time_elapsed (fast bubble sort): 2.38038301468

Answer 1

“快”的人可以做更多的工作。添加计数器以查看他们执行其他操作未执行的操作的频率:

def check_sorted(A):
    for i in xrange(1, len(A)):
        global slow_checks; slow_checks += 1              # <== Added this
        if A[i] < A[i-1]:
            return False
    return True

def bubble_sort_fast(A):
    swap = True
    while swap:
        swap = False
        for i in xrange(1, len(A)):
            if A[i] < A[i-1]:
                A[i], A[i-1] = A[i-1], A[i]
                swap = True
                global fast_marks; fast_marks += 1        # <== Added this
    return A

您会发现 slow_checks 最终为 9998，而 fast_marks 最终为 12497500。这要多得多。准确地说，是 5000 * 4999/2，即原始数据中的交换总数。

为什么slow_checks这么小？好吧，因为从一个气泡迭代到下一个气泡迭代，您的列表会像这样演变:

Start:                  [4999, 4998, 4997, 4996, 4995, ...
After bubbling 4999 up: [4998, 4997, 4996, 4995, 4994, ...
After bubbling 4998 up: [4997, 4996, 4995, 4994, 4993, ...
After bubbling 4997 up: [4996, 4995, 4994, 4993, 4992, ...
After bubbling 4996 up: [4995, 4994, 4993, 4992, 4991, ...
...
After bubbling 4 up:    [3, 2, 1, 0, 4, 5, 6, 7, 8, 9, ...
After bubbling 3 up:    [2, 1, 0, 3, 4, 5, 6, 7, 8, 9, ...
After bubbling 2 up:    [1, 0, 2, 3, 4, 5, 6, 7, 8, 9, ...
After bubbling 1 up:    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...

如您所见，在查看前两个值后，check_sorted 总是可以返回 False!除了你最后一次询问它之外，因为那时它会遍历整个列表并发现它已排序。因此，4999 次它只执行一项检查，然后一次执行 4999 次检查，总共 9998 次检查。

我的整个代码:https://repl.it/repls/SnarlingHotpinkNatterjacktoad