"median of medians"算法的Python实现

Question

我已经在 python 中编写了这个中位数算法的实现，但它似乎没有输出正确的结果，而且它对我来说似乎也不是线性复杂度，知道我在哪里偏离轨道了吗？

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

这个函数是这样调用的:

L = list(range(100))
shuffle(L)
print(select(L))

LE:对不起。 GetMed 是一个简单地对列表进行排序并返回 len(list) 处的元素的函数，它应该在那里被选择，我现在修复了它，但我仍然得到错误的输出。至于缩进，代码没有错误，我看不出有什么问题:-??

LE2:我期望 50(对于当前的 L)，它给我的输出从 30 到 70，不多也不少(还)

LE3:非常感谢，现在已经成功了。虽然我很困惑，但我正在尝试比较这种方法和天真的方法，我只是对数组进行排序并输出结果。现在，根据我目前的阅读，select 方法的时间复杂度应该是 O(n) Deterministic Selection .虽然我可能无法与 python 开发人员所做的优化竞争，但我确实期望得到比我得到的更接近的结果，例如，如果我将列表的范围更改为 10000000，则选择在 84.10837116255952 秒内输出结果，而排序和返回方法在 18.92556029528825 中执行。有哪些好的方法可以使该算法更快？

Answer 1

1) 你的代码缩进是错误的，试试这个:

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 = []