python - 如何评估嵌套的 boolean 值？

Question

我是 python 的新手，已经熟悉了基础知识，例如嵌套 for 循环。我遇到了下面的函数，当我试图理解它在做什么时，我被绊倒了。它总是返回通过函数传递的列表，并且似乎根据传入的列表的长度将 boolean 值 False 分配给元素“x”，最终在 false 的值不是时打破循环案子。我不明白的是 for 循环中第一个元素相对于第二个 for 循环的作用(它从大小中减去)。如果有什么可以帮助我更好地理解此功能的作用，我们将不胜感激。

def myfunc(list):

    size = len(list)

    for x in range(0, size):
        foo = False

        for x2 in range(0, size - x - 1):
            if list[x2] > list[x2 + 1]:
                list[x2], list[x2 + 1] = list[x2 + 1], list[x2]
                foo = True

        if not foo: break

    return list

Answer 1

您编写的函数是一种称为冒泡排序的排序技术的实现。它只是比较相邻的元素来对列表进行排序。

虽然您不必在 size - x - 1 次迭代时停止第二个 for 循环，但它有助于减少您执行的比较次数，从而提高已有算法的效率n ^ 2 数量级的时间复杂度，在较大的列表上表现不佳。

如果跟踪整个执行过程，您会发现在外循环的每次迭代之后，都会有一个元素到达它在排序数组中的确切位置，最好不要在后续迭代中考虑该元素。

因此您的程序提前停止内部循环，知道最后的 x 元素已经排序。

当涉及到 boolean 值时，它会进一步减少您执行的比较次数。例如，当你传入一个排序列表时:在外循环的第一次迭代中，x = 0。然后内部循环迭代 size - 1 次比较相邻元素但不执行交换，因为元素已经按顺序排列。一旦内循环完成了外循环第一次迭代的所有迭代 (x = 0)，继续进行进一步的迭代就没有意义了，此时最好停止算法。 break 语句确保这种情况发生。

因此，在最好的情况下，您的算法的时间复杂度将是 n 阶 (O(n))，这优于 的平均或最坏情况复杂度O(n^2)