提前退出 冒泡排序冒泡排序

1. 第一个循环与内部发生的事情无关
2. 第二个回路完成所有的重物提升。你可以摆脱 count 通过使用 enumerate
3. 要交换元素,请使用pythonic交换- 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的渐进(大O)复杂性(保持不变 O(N ** 2) )相反,只会减少相关的常数因子。

一个简单的优化是从i+1索引开始第二个循环:

for i in range(0, len(foo)):
    for j in range(i+1, len(foo)):
        if (foo[i] > foo[j]):
            temp = foo[i]
            foo[i] = foo[j]
            foo[j] = temp

由于您已经将所有内容排序到索引i,因此无需再次对其进行迭代。这可以为您节省50%以上的比较—在这种情况下,原始算法中的比较是10对25。

为了了解算法在计算资源使用方面的效率,与计算机体系结构或时钟频率无关,您需要了解大Oh符号。它基本上可以帮助您分析最坏情况下,随着输入大小的增加,算法的运行时间或内存使用情况。 总之,算法的运行时间将属于以下类别之一(从最快到最慢);

O(1):恒定时间。发音为(Oh/1)。最快的时间。

O(lg n):对数时间。发音(对数n的Oh)。比线性时间快。 传统上,这是搜索的最快时限。

O(n):线性时间。发音(n的Oh,n是输入的大小,例如 阵列)。通常当你需要检查 您的输入。

O(nlgn):在 元素列表。

O(n**2):n平方的Oh。二次时间。当我们 嵌套循环。

O(2**n):真的,真的很大!升到n的幂的数字比 n升到任意幂。

在本例中,您使用的是嵌套循环,即O(n 2). 我编写的代码使用一个while循环,其增长复杂性为O(n),比O(n)快 2). 我还没有在一个很大的 array 但在你的情况下,这似乎是可行的。试试看,让我知道它是否按预期工作。

k = [7, 0, 3, 4, -1]
n = len(k)
i = 0
count = 0
while count < n**2: # assuming we wouldn't go through the loop more than n squared times
    if i == n - 1:
        i = 0
        count += 1
        swapped = False
    elif k[i] > k[i+1]:
        temp = k[i]
        k[i] = k[i+1]
        k[i+1] = temp
        i+=1
        swapped = True
    elif swapped == False:
        i += 1
    elif swapped == True and i < n - 1:
        i += 1

注意:在示例列表(k)中,我们只需在列表中循环三次,就可以按升序对其进行排序。如果将while循环更改为这行代码 while count < 4: ,它仍然可以工作。