我正在尝试实现我刚在课堂上学到的rselect算法。然而，似乎无法找出我在实现中的错误所在这是我的密码。*编辑*
：我试着使用david的答案中提供的信息，但我的代码仍然很奇怪。以下是修订后的代码：
def rselect(seq,length,i):# i is the i'th order statistic.
if len(seq)<=1:return seq
lo,pi,hi,loc_pi= random_partition(seq
if loc_pi==i:return pi
if loc_pi>i:return rselect(lo,loc_pi-1,i)
elif loc_pi<i:return rselect(hi,length-loc_pi,i-loc_pi)#
from random import choice
def random_partition(seq):
pi =choice(seq)
#print 'pi',pi
loc_pi=seq.index(pi)
print 'Location',loc_pi
lo=[x for x in seq if x<=pi]
hi=[x for x in seq if x>pi]
return lo,pi,hi,len(lo)+1 #--A
def test_rselect(seq,i):
print 'Sequence',seq
l=len(seq)
print 'Statistic', rselect(seq,l,i)
然而，输出在不同的时间是不同的，甚至有时是正确的！。我对算法和python都一窍不通，任何关于我哪里出错的帮助都非常感谢。
编辑：每次运行代码时，我都会得到第i个订单统计的不同值，这是我的问题
例如，下面的每一段代码
Revised Output:
/py-scripts$ python quicksort.py
Sequence [54, -1, 1000, 565, 64, 2, 5]
Statistic Location 1
-1
@ubuntu:~/py-scripts$ python quicksort.py
Sequence [54, -1, 1000, 565, 64, 2, 5]
Statistic Location 5
Location 1
Location 0
-1
期望输出：我期望在这里找到第i个顺序统计。
因此
test_rselect([54,-1,1000,565,64,2,5],2)应始终返回5作为统计值。如果我在这个实现中出错，任何帮助都会有帮助。谢谢！啊！
编辑2：在尝试分析算法时，我认为错误在于我如何返回标记为A的行中的轴位置（loc_pi）。考虑到上述程序的以下事件序列。
test_rselect( [ 55, 900, -1,10, 545, 250], 3) // call to input array
calls rselect ([ 55, 900, -1,10, 545, 250],6,3)
1st call to random_partition:
pi=545 and loc_pi=4
lo=[55,-1,10,250,545]
hi=[900]
return to rselect function (lo,545,hi,6)
here loc_pi>i: so rselect(lo,5,3)// and discard the hi part
2nd recursive call to rselect:
2nd recursive call to random_partition:
call random_partition on (lo) // as 'hi' is discarded
pi=55 loc_pi=0
lo=[-1,10,55]
hi=[250,545]
return to rselect(lo,55,hi,4)
here loc_pi>i: rselect(lo,3,3)// The pivot element is lost already as it is in 'hi' here!!
关于如何处理返回pivot元素的位置以获得正确的o/p的任何帮助都是有帮助的设立一个悬赏，为一个答案，清楚地解释我在哪里做错事，我如何可以纠正它（伟大的提示是受欢迎的，因为我期待学习：））。期待伟大的答案！
最佳答案
我不认为有任何主要的错误（在你如何返回轴或其他方面），这只是一个（或甚至两个）的混乱，加上我认为你的意思是比较我在第一行的rselect，而不是1。
这是我的看法，尽可能少地改变：
def rselect(seq,length,i):# i is the i'th order statistic.
if len(seq)<=i:return seq
lo,pi,hi,loc_pi= random_partition(seq)
if loc_pi==i:return pi
if loc_pi>i:return rselect(lo,loc_pi,i)
elif loc_pi<i:return rselect(hi,length-(loc_pi+1),i-(loc_pi+1))
from random import choice
def random_partition(seq):
pi =choice(seq)
lo=[x for x in seq if x<=pi]
hi=[x for x in seq if x>pi]
return lo,pi,hi,len(lo)-1
编辑：如果有重复的元素，这里有一个版本应该可以工作。现在，我不得不再换一些，所以我拿出一些我觉得很混乱的东西，以便让自己更容易。
def rselect(seq,i):# i is the i'th order statistic.
if len(seq)<=i:return seq
lo,pi,hi= random_partition(seq)
if i < len(lo):return rselect(lo,i)
if i < len(seq)-len(hi): return pi
return rselect(hi,i-(len(seq)-len(hi)))
from random import choice
def random_partition(seq):
pi =choice(seq)
lo=[x for x in seq if x<pi]
hi=[x for x in seq if x>pi]
return lo,pi,hi
def test_rselect(seq,i):
print 'Sequence',seq
stat=rselect(seq,i)
print 'Statistic', stat