如何计算嵌套布尔值？

Question

我对python还比较陌生，对基础知识也很熟悉，比如嵌套for循环。我遇到了下面的函数，当我试图理解它在做什么时，我被绊倒了。它总是返回通过函数传递的列表，并根据传递的列表的长度为元素“x”指定一个布尔值False，最终在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元素已经被排序。你知道吗

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

因此，在最佳情况下，算法的时间复杂度为n（O(n)），这比平均或最坏情况下的复杂度O(n^2)要好