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

第一个循环与内部发生的事情无关
第二个循环完成了所有繁重的工作。您可以使用 enumerate

count

要交换元素，请使用 pythonic swap - a, b = b, a.
根据，利用提前退出。如果在内循环中的任何一点都没有进行交换，则意味着列表已排序，并且不需要进一步的迭代。这就是 changed 背后的直觉。
根据定义，外层循环第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]

请注意，这些优化中的 none 改变了 BubbleSort 的渐近 (Big-O) 复杂性（保持 O(N ** 2)），相反，仅减少了相关的常数因子。

Answer 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 次。

Answer 3

您需要了解大 Oh 表示法，以便了解您的算法在独立于计算机体系结构或时钟速率的计算资源使用方面的效率。随着输入大小的增加，它基本上可以帮助您分析算法在最坏情况下的运行时间或内存使用情况。总之，你的算法的运行时间将属于这些类别之一（从最快到最慢）；

O(1)：常数时间。发音（Oh of 1）。最快的时间。

O(lg n)：对数时间。发音（Oh of log n）。比线性时间快。传统上，它是搜索的最快时间限制。

O(n)：线性时间。发音（Oh of n，n 是您输入的大小，例如大小数组）。通常当你需要检查每一点时您的意见。

O(nlgn)：我们目前在对a执行排序时可以达到的最快时间元素列表。

O(n**2)：n 平方的 Oh。二次时间。通常这是我们有的界限嵌套循环。

O(2**n)：真的，真的很大！一个数的 n 次方比 n 的任意次幂。

在您的例子中，您使用的是 O(n2) 的嵌套循环。我编写的代码使用单个 while 循环并且具有 O(n) 的增长复杂度，这比 O(n2) 更快。我还没有真正在非常大的 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)中，我们只需要循环遍历列表3次，就可以实现升序排列。因此，如果将 while 循环更改为这行代码 while count < 4:，它仍然有效。

Python: 我怎样才能让冒泡排序的实现更有效率？

Python: How can I make my implementation of bubble sort more time efficient?

python

sorting

performance

bubble-sort

Early Exit BubbleSort