2

我正在尝试编写自己的 hoare 分区函数以更好地理解它。我以为我很好地遵循了它的定义和伪代码，但即使它在很多情况下似乎都按预期工作，但当传入多个值等于 pivot 的列表时，它会崩溃并进入无限循环。我的错误在哪里，我应该如何修改它以修复错误？

def partition(lst, left_index, right_index):
    pivot = lst[right_index]


    while True:
        #Increment left index until value at that index is greater or equal to pivot
        while True:
            if lst[left_index] >= pivot: break
            left_index += 1

        #Increment right index until value at that index is less or equal to pivot
        while True:
            if lst[right_index] <= pivot: break
            right_index -= 1

        if left_index < right_index:
            lst[left_index], lst[right_index] = lst[right_index], lst[left_index]
        else:
            return right_index

return partition(0, end)
4

1 回答 1

2

lst[left_index] >= pivot您正在测试和中的枢轴值是否相等lst[right_index] <= pivot。这有效地防止了两个索引跳过枢轴值元素。因此，当两个或多个具有枢轴值的元素被推向列表的中间时，left_index并被right_index不可逾越的障碍隔开。删除其中一个 ing 行中的等号break，非停止问题将消失。

但是，由于这种变化，移动的循环left_index可能会将其推高一个位置，甚至在停留在其初始位置right_index时超出范围。right_index类似地，移动的循环right_index可能会将其推下一个位置，甚至在其初始位置停留时left_index会超出范围。left_index为防止这种情况发生，您必须将while True:这些循环更改为while left_index < right_index:.

请注意，分区会略有不同，具体取决于您是否删除left_index或的相等性检查right_index。当枢轴元素变成列表中的最小值或最大值时，这对于边界情况很重要。考虑到一开始right_index表示相对于输入范围的内部位置并left_index指向边界位置，您必须允许left_index跳过枢轴值，而right_index必须指示在枢轴值处停止（相反的逻辑将允许left_index停留在其初始位置直到算法结束，而right_index可以一直向下推到left_index，不会产生任何分区）。

因此，更正后的代码将是这样的：

def partition(lst, left_index, right_index):
    pivot = lst[right_index]

    while True:
        while left_index < right_index and lst[left_index] <= pivot:
            left_index += 1

        while left_index < right_index and lst[right_index] > pivot:
            right_index -= 1

        if left_index < right_index:
            lst[left_index], lst[right_index] = lst[right_index], lst[left_index]
        else:
            return right_index
于 2016-07-10T00:23:51.780 回答