python - Python 中的就地快速选择(又名线性时间选择)的错误

Question

我正在学习斯坦福大学类(class)“算法:设计与分析，第 1 部分”，同时尝试在 Python 中实现就地随机选择算法(即基于快速排序的选择)，我相信我的分区函数是正确的，但我只是不明白为什么选择部分总是失败，任何建议都将不胜感激。我的代码如下:

import random
def random_selection(nums, start, end, i):   
    if end == start:
        return nums[start]
    elif start < end:       
        pivot = partition(nums, start, end)        
        if pivot == i:            
            return nums[pivot]
        elif pivot < i:
            # original code suffering from logic error with indices, fixed by changing 'i - pivot' into 'i' 
            # return random_selection(nums, pivot + 1, end, i - pivot)
            return random_selection(nums, pivot + 1, end, i)
        elif pivot > i:
            return random_selection(nums, start, pivot - 1, i)
    else:       
        return False        


def partition(nums, start, end):
    pivot_value = nums[start]
    left = start + 1
    right = end
    done = False
    while not done:
        while left <= right and nums[left] < pivot_value:
            left += 1

        while left <= right and nums[right] > pivot_value:
            right -= 1

        if left > right:
            done = True
        else:
            nums[left], nums[right] = nums[right], nums[left]
    nums[start], nums[right] = nums[right], nums[start]
    return right  

test = range(10)
for i in range(10):
    random.shuffle(test)
    print random_selection(test, 0, len(test)-1, i)

以下是我收到的测试用例结果:

0
1
None
3
4
None
5
4
8
None

Answer 1

问题是你需要决定你的索引是基于 0 还是基于 start。

大多数代码使用基于 0 的索引，除了对 random_selection 的递归调用:

return random_selection(nums, pivot + 1, end, i - pivot)

将 i 索引调整为 i - start (即假设索引基于 start)。

将其更改为:

return random_selection(nums, pivot + 1, end, i)

应该给出预期的结果。