基于Python的quickselect实现导致错误

问题描述

我有一个小的python代码，可实现在此处中讨论的quickselect.

I have small python code that implements the quickselect discussed here.

import random
def Quickselect(A, k):
    if not A:
        return
    pivot = random.choice(A)

    i = 0
    A1 = []
    A2 = [] # Two new arrays A1, A2 to store the split lists
    for i in range(len(A)):
        if A[i] < pivot :
            A1.append(A[i])
        else:
            A2.append(A[i])

    if k < len(A1):
        return Quickselect(A1, k)
    if k > len(A) - len(A2):
        return Quickselect(A2, k-(len(A) - len(A2)))
    else:
        return pivot
pass
def main():
    A = [45,1,27,56,12,56,88]
    print(Quickselect(A,2))
pass

我似乎遇到了randrange错误.有什么不对吗?

I seem to be getting an randrange error. Is something amiss?

实现了random.choice而不是random.randint.上面的代码似乎工作正常.感谢User Blender.

Implemented random.choice instead of random.randint.The above code seems to work fine. Thanks to User Blender.

推荐答案

您的错误发生是因为当范围为空(即randrange(1, 1))时randrange会中断.

Your error occurs because randrange breaks when the range is empty (i.e. randrange(1, 1)).

改为使用random.choice，然后将k <= len(A1)更改为k < len(A1):

Use random.choice instead and change k <= len(A1) to k < len(A1):

def quick_select(A, k):
    pivot = random.choice(A)

    A1 = []
    A2 = []

    for i in A:
        if i < pivot:
            A1.append(i)
        elif i > pivot:
            A2.append(i)
        else:
            pass  # Do nothing

    if k <= len(A1):
        return Quickselect(A1, k)
    elif k > len(A) - len(A2):
        return Quickselect(A2, k - (len(A) - len(A2)))
    else:
        return pivot

这篇关于基于Python的quickselect实现导致错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！