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. 第二个循环完成所有繁重的工作。你可以使用count摆脱enumerate
3. 要交换元素，请使用pythonic swap - a, b = b, a。
4. 根据this comment，使用提前退出。如果在内循环中的任何点都没有进行交换，则表示列表已排序，并且不需要进一步迭代。这是changed背后的直觉。
5. 根据定义，在外部循环的第i次迭代之后，最后的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]

请注意，这些优化都不会改变冒泡排序（仍为qazxsw poi）的渐近（Big-O）复杂度，相反，只会减少相关的常数因子。

Answer 2

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

O(N ** 2)

由于您已经将所有内容排序到索引i，因此无需再次迭代它。这可以为您节省超过50％的比较 - 在​​这种情况下，它在原始算法中为10比25。

Answer 3

为了理解算法在独立于计算机体系结构或时钟速率的计算资源使用方面的效率，您需要了解大哦符号。它基本上可以帮助您分析算法的最坏情况运行时间或内存使用情况，因为输入的大小会增加。总之，算法的运行时间将属于以下类别之一（从最快到最慢）;

O（1）：恒定时间。发音（Oh of 1）。最快的时间。

O（lg n）：对数时间。发音（日志的哦）。比线性时间更快。传统上，它是搜索的最快时间。

O（n）：线性时间。发音（哦，n，n是输入的大小，例如数组的大小）。通常需要检查输入的每一位。

O（nlgn）：在元素列表上执行排序时我们当前可以实现的最快时间。

O（n ** 2）：n平方的哦。二次时间。当我们有嵌套循环时，这通常是绑定。

O（2 ** n）：真的，非常棒！提升到n的幂的数字比提高到任何幂的n慢。

在您的情况下，您使用的是嵌套循环，即O（n2）。我编写的代码使用单个while循环，其增长复杂度为O（n），比O（n2）快。我没有真正尝试过一个非常大的

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

，但在你的情况下它似乎工作。尝试一下，让我知道它是否按预期工作。

array

注意：在示例列表（k）中，我们只需要遍历列表三次，以便按升序排序。因此，如果你将while循环更改为这行代码

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

，它仍然可以工作。