我实现了以下代码,但我不知道为什么我认为运行得更快的“快速”冒泡排序实际上运行得比预期慢。在第一个实现中,我认为我浪费了很多时间检查每个数组是否已排序,这需要 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
最佳答案
“快”的人可以做更多的工作。添加计数器以查看他们执行其他操作未执行的操作的频率:
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 次检查。
关于python - 为什么冒泡排序的实现速度明显慢于预期?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48476773/