如何评估嵌套布尔值

Question

我对python相对较新，并且对基础知识感到满意，甚至可以嵌套以进行循环。我遇到了下面的功能，当我试图理解它在做什么时，我被绊倒了。它始终返回通过该函数传递的列表，并根据列表的长度分配false的布尔值为" x"的布尔值案子。我不明白的是第一个元素在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迭代中停止第二个循环，但它有助于减少您执行的比较数量，从而提高算法的效率，已经具有N ^ 2的时间复杂性在较大的列表上表现不佳。

如果您追踪执行，您会意识到，在外部循环的每一次迭代之后，另一个元素都到达了确切的位置，它将位于排序的数组中，最好不要在随后的迭代中考虑该元素。

因此，您的程序知道最后一个x元素已经被分类，因此您的程序会尽早停止内部循环。

涉及布尔值时，它会进一步降低您执行的比较。例如，当您通过排序列表时：在外循环的第一次迭代中，x = 0。然后，内部循环会迭代size - 1次比较相邻元素，但由于元素已经按顺序排列，因此不执行交换。一旦内部循环完成了外循环的第一次迭代（x = 0）的所有迭代，它就毫无意义地进行了进一步的迭代，并且最好停止该算法。休息声明确保了这种情况。

因此，在最好的情况下，算法的时间复杂性将是n（O(n)）的顺序，它比O(n^2)