algorithm - 如何有效地计算冒泡排序迭代的次数？

Question

典型的冒泡排序(复杂度为 N^2)看起来像这样(来自维基百科):

procedure bubbleSort( A : list of sortable items )
n = length(A)
repeat
    swapped = false
    for i = 1 to n-1 inclusive do
        if A[i-1] > A[i] then
            swap( A[i-1], A[i] )
            swapped = true

如何确定外层循环在 O(N^2) 内迭代的次数？ (如下图，太慢了):

procedure bubbleSort( A : list of sortable items )
n = length(A)
count = 0
repeat
    count += 1
    swapped = false
    for i = 1 to n-1 inclusive do
        if A[i-1] > A[i] then
            swap( A[i-1], A[i] )
            swapped = true

Answer 1

每次迭代都会将最大的元素移动到数组的末尾(让我们从左到右)；每个较小的元素将最多向左移动 1 个位置。所需外环的数量是任何数量在该方向上的最大位移。

更详细地说，您需要找到数组中左侧较大元素数量最多的元素。这个数量(“最大数量”)就是您的答案。

你能从那里拿走它吗？