Python 中的就地快速选择（又名线性时间选择）错误

Question

我正在学习斯坦福大学的课程 "Algorithms: Design and Analysis, Part 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 还是基于开始。

大部分代码使用基于 0 的索引，除了递归调用 random_selection:

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

将第 i 个索引调整为 i - start（即假设索引基于开始）。

将其更改为：

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

应该给出预期的结果。

Python 中的就地快速选择（又名线性时间选择）错误

Bug with in-place quick selection (aka linear time selection) in Python

python

algorithm

quicksort