Python实现“中位数中位数”算法

一尘不染

Python实现“中位数中位数”算法

algorithm

我已经在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）确定性选择。尽管我可能无法与python开发人员进行的优化竞争，但我确实希望获得比我更接近的结果，例如，如果我将列表的范围更改为10000000，则选择输出结果的时间为84.10837116255952秒，而sort和return方法在18.92556029528825中完成。有什么好的方法可以使该算法更快？

阅读 286

2020-07-28

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

2020-07-28