0

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

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

dSelect 算法在理论上很简单。当列表长度为 1 时，基本案例返回一个项目。否则，就像在快速排序中一样，我遍历列表。如果我当前所在的数字 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)
4

1 回答 1

1

最大的问题是这里的这条线：

i = (length + 1)/2

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

i = (7 + 1) / 2

所以 i 等于 4 而不是 3。偶数长度列表部分的类似问题，尽管这不应该是一个大问题。

于 2012-11-15T05:24:40.123 回答