提问
我正在尝试实现我刚刚在课堂上学习的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都不熟悉,对我在哪里出错的任何帮助将不胜感激.
编辑：每次运行代码时,我会为ith顺序统计获取不同的值,这是我的问题
例如,下面的代码每次运行都会给出
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!!
为了获得正确的o / p,对如何处理枢轴元素的位置的任何帮助都将有所帮助.设置赏金,以清楚地说明我做错了什么地方以及如何纠正它的答案(欢迎提供很好的提示,因为我希望学习:)).期待很好的答案！
最佳答案
我不认为存在任何主要错误(关于如何返回数据透视图或其他方式),这只是很多(一甚至两个)的混乱,而且我想您的意思是要与i进行比较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