def select(L):
if len(L) < 10:
L.sort()
return L[int(len(L)/2)]
S = []
lIndex = 0
while lIndex+5 < len(L)-1:
S.append(L[lIndex:lIndex+5])
lIndex += 5
S.append(L[lIndex:])
Meds = []
for subList in S:
print(subList)
Meds.append(select(subList))
L2 = select(Meds)
L1 = L3 = []
for i in L:
if i < L2:
L1.append(i)
if i > L2:
L3.append(i)
if len(L) < len(L1):
return select(L1)
elif len(L) > len(L1) + 1:
return select(L3)
else:
return L2
2)您使用的方法不会返回中位数,而只是返回一个与中位数相差不远的数字。要获得中位数,您需要计算出比伪中位数大多少个数,如果多数更大,则用大于伪中位数的数字重复该算法,否则用其他数字重复。
def select(L, j):
if len(L) < 10:
L.sort()
return L[j]
S = []
lIndex = 0
while lIndex+5 < len(L)-1:
S.append(L[lIndex:lIndex+5])
lIndex += 5
S.append(L[lIndex:])
Meds = []
for subList in S:
Meds.append(select(subList, int((len(subList)-1)/2)))
med = select(Meds, int((len(Meds)-1)/2))
L1 = []
L2 = []
L3 = []
for i in L:
if i < med:
L1.append(i)
elif i > med:
L3.append(i)
else:
L2.append(i)
if j < len(L1):
return select(L1, j)
elif j < len(L2) + len(L1):
return L2[0]
else:
return select(L3, j-len(L1)-len(L2))
警告:L = M = []
不是L = []
和M = []