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

Question

好的。我放弃。我一直试图实现中位数算法的中位数，但我不断给出错误的结果。我知道下面有很多代码，但我找不到我的错误，并且每个代码块都有相当程序设计。快速排序是我用来排序中位数中位数的中位数。应该是一个简单的quicksort实现。 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 

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

i = (7 + 1)/2 

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