Python:如何使我的冒泡排序实现更省时？

Question

这是我的代码 - 用于按 asc 顺序对列表元素进行排序的冒泡排序算法:

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

我一直在修改我的代码，但对于在线法官来说，它仍然太低效了。一些帮助将不胜感激!

Answer 1

Early Exit BubbleSort

1. 第一个循环与内部发生的事情无关
2. 第二个循环完成所有繁重的工作。您可以使用 enumerate
摆脱 count
3. 要交换元素，请使用 pythonic swap - a, b = b, a。
4. 根据 this comment ，利用提前退出。如果在内循环中的任何一点都没有进行交换，则意味着列表已排序，并且不需要进一步的迭代。这就是 changed 背后的直觉。
5. 根据定义，在外层循环的第 i^th 次迭代之后，最后的 i 个元素将被排序，因此您可以进一步减少与算法。

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))，相反，只会减少相关的常数因子。