"median of medians"算法的 Python 实现

我已经在 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))

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

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

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

最佳答案

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

关于 "median of medians"算法的 Python 实现，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10806303/