python - 在Python中实现中值选择算法的中值

Question

好的。我放弃。我一直在尝试实现中位数算法的中位数，但我不断得到错误的结果。我知道下面有很多代码，但我找不到我的错误，而且每一 block 代码都有一个相当流程化的设计。快速排序是我用来对从中位数枢轴选择的中位数中获得的中位数进行排序的方法。应该是一个简单的快速排序实现。 getMean 只是返回给定列表的平均值。

getPivot 是我用来选择枢轴的方法。它遍历列表，一次取 5 个整数，找到这些整数的平均值，将平均值放入列表 c，然后找到 c 的中值。这是我用于 dSelect 算法的基准。

dSelect算法理论上很简单。当列表长度为 1 项时，基本情况返回一个项目。否则，就像在 quickSort 中一样，我遍历列表。如果我当前所在的数字 j 小于主元，我将它移到列表 i 的左侧并递增 i。如果它更大，我将它移到列表的右侧，i + 1，并且不增加 i。在循环遍历整个列表之后，我应该在其正确的索引中找到主元，打印语句表明我这样做了。此时，我根据枢轴是大于还是小于我要查找的位置向左或向右递归。

我不确定此时要测试哪些其他打印语句，所以我求助于任何足够专注于尝试这段代码的人。我知道有相关主题，我知道我可以做更多的打印语句，但请相信我，我已经尝试过了。什么应该是一个简单的算法让我很困惑。

def quickSort(m, left, right):
    if right - left <= 1:
        return m
    pivot = m[left]
    i = left + 1
    j = left + 1
    for j in range(j, right):
        if m[j] < pivot:
            m[j], m[i] = m[i], m[j]
            i += 1
        elif m[j] == pivot:
            m[j], m[i] = m[i], m[j]
    print m
    m[left], m[i-1] = m[i-1], m[left]
    m = quickSort(m, left, i-1)
    m = quickSort(m, i, right)
    print m
    return m
def getMedian(list):
    length = len(list)
    if length <= 1:
        return list[0]
    elif length % 2 == 0:
        i = length/2
        return list[i]
    else:
        i = (length + 1)/2
        return list[i]
def getPivot(m):
    c = []
    i = 0
    while i <= len(m) - 1:
        tempList = []
        j = 0
        while j < 5 and i <= len(m) - 1:
            tempList.append(m[i])
            i = i + 1
            j = j + 1
        tempList = quickSort(tempList, 0, len(tempList) - 1)
        c.append(getMedian(tempList))
    c = quickSort(c, 0, len(c) - 1)
    medianOfMedians = getMedian(c)
    return medianOfMedians

def dSelect(m, position):
    pivot = getPivot(m)
    i = 0
    j = 0
    if len(m) <= 1:
        return m[0]
    for j in range(0, len(m)):
        if m[j] < pivot:
            m[j], m[i] = m[i], m[j]
            i += 1
        elif m[j] == pivot:
            m[j], m[i] = m[i], m[j]
        print "i: " + str(i)
        print "j: " + str(j)
    print "index of pivot: " + str(m.index(pivot))
    print "pivot: " + str(pivot) + " list: " + str(m)
    if m.index(pivot) == position:
        return pivot
    elif m.index(pivot) > position: 
        return dSelect(m[0:i], position)
    else:
        return dSelect(m[i:], position - i)

Answer 1

最大的问题是这里的这一行:

i = (length + 1)/2

如果 list = [1, 2, 3, 4, 5, 6, 7] 答案应该是 4，即 list[3]。您的版本如下所示:

i = (7 + 1) / 2

因此 i 等于 4 而不是 3。与偶数长度列表部分有类似的问题，尽管这应该不是什么大问题。