在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類似的問題與偶數長度列表一部分，儘管這不應該是大的問題。