双向气泡排序证明

Question

我要上算法入门课。作为家庭练习的一部分，我需要证明给定的双向气泡排序算法是正确的。我们必须遵循以下算法(在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 (之前的退出一个内部返回语句)的程度？

Answer 1

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

left和right被初始化为数组的最左和最右的索引，每一次迭代都无条件地向右和左方向移动，不管接下来的两个循环会发生什么。所以很明显，left >= right会发生并退出循环。

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

调试，您将得到它自己。

编辑

我需要证明给定的双向气泡排序算法是正确的。

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

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