python - 双向冒泡排序证明

Question

我正在学习算法入门类(class)。作为家庭练习的一部分，我需要证明给定的双向冒泡排序算法是正确的。我们必须遵循以下算法(在 python 中实现):

def bidirectional_bubble_sort(a):
left = -1
right = len(a)
while left < right:
    swap = False
    left += 1
    right -= 1
    for i in xrange(left, right):
        if a[i] > a[i + 1]:
            t = a[i]
            a[i] = a[i + 1]
            a[i + 1] = t
            swap = True
    if not swap:
        return
    else:
        swap = False
    for i in xrange(right - 1, left - 1, -1):
        if a[i] > a[i + 1]:
            t = a[i]
            a[i] = a[i + 1]
            a[i + 1] = t
            swap = True
    if not swap:
        return

我对主循环条件有点困惑。算法是否曾经到达 left>=right 的点(before 在内部 return 语句之一退出)？

Answer 1

while left < right:
    swap = False
    left += 1
    right -= 1

left 和 right 被初始化为数组的最左边和最右边的索引，并且对于每次迭代，它无条件地向右和向左方向移动 - 无论如何将在接下来的两个循环中发生。所以很明显 left >= right 会发生并退出循环。

对于偶数长度的数组，left > right，对于奇数长度的数组，left == right 将到达并退出循环。

调试一下，自己搞定。

编辑

I need to prove that a given bidirectional bubble sort algorithm is correct

你能试试这个片段吗？上面的实现似乎不正确。

def bidirectional_bubble_sort(a):
    left = -1
    right = len(a)
    while left < right:
        swap = False
        left += 1
        right -= 1
        for i in xrange(left, right):
            if a[i] > a[i + 1]:
                t = a[i]
                a[i] = a[i + 1]
                a[i + 1] = t
                swap = True
        if not swap:
            return
        else:
            swap = False
        for i in xrange(right, left, -1):
            if a[i] < a[i - 1]:
                t = a[i]
                a[i] = a[i - 1]
                a[i - 1] = t
                swap = True
        if not swap:
            return