Python:如何使我的气泡排序实现更省时? [英] Python: How can I make my implementation of bubble sort more time efficient?

问题描述

这是我的代码-一种气泡排序算法，用于按升序对列表元素进行排序:

Here is my code - a bubble sort algorithm for sorting list elements in asc order:

foo = [7, 0, 3, 4, -1]
cnt = 0
for i in foo:
    for i in range(len(foo)-1):
        if foo[cnt] > foo[cnt + 1]:
            temp = foo[cnt]
            c[cnt] = c[cnt + 1]
            c[cnt + 1] = temp
        cnt = cnt + 1
    cnt = 0

我一直在修改自己的代码，但对于在线法官而言，效率仍然太低.一些帮助将不胜感激！

I've been revising my code, but it is still too inefficient for an online judge. Some help would be greatly appreciated!

推荐答案

提早退出 BubbleSort

1. 第一个循环与内部发生的事情无关
2. 第二个循环完成所有繁重的工作.您可以使用enumerate
摆脱count
3. 要交换元素，请使用pythonic交换-a, b = b, a.
4. 按照

1. The first loop has no bearing on what happens inside
2. The second loop does all the heavy lifting. You can get rid of count by using enumerate
3. To swap elements, use the pythonic swap - a, b = b, a.
4. As per this comment, make use of an early exit. If there are no swaps to be made at any point in the inner loop, that means the list is sorted, and no further iteration is necessary. This is the intuition behind changed.
5. By definition, after the i^th iteration of the outer loop, the last i elements will have been sorted, so you can further reduce the constant factor associated with the algorithm.

foo = [7, 0, 3, 4, -1]
for i in range(len(foo)):
    changed = False
    for j, x in enumerate(foo[:-i-1]):
        if x > foo[j + 1]:
            foo[j], foo[j + 1] = foo[j + 1], foo[j]
            changed = True

    if not changed:
        break

print(foo)
[-1, 0, 3, 4, 7]

请注意，这些优化都无法改变BubbleSort的渐近(Big-O)复杂度(仍为O(N ** 2))，而只会降低相关的常数.

Note that none of these optimisations change the asymptotic (Big-O) complexity of BubbleSort (which remains O(N ** 2)), instead, only reduces the constant factors associated.

这篇关于Python:如何使我的气泡排序实现更省时?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！