i阶统计的确定性快速选择python（中位数方法的中位数）

Question

dselect 在 O(n) 时间内在给定的未排序整数列表（无重复项）中找到第 i 个顺序统计信息，搭载快速排序的原则。第 i 个顺序统计量定义为给定列表中已排序版本中的第 i 个最小元素。因此，一阶统计量将是最小元素，n 阶统计量将是最大元素，依此类推...

在运行上，我在 dselect 函数末尾的 return arr[l] 上得到 IndexError: list index out of range。我认为错误是由于我在 dselect 函数的列表 medians 上的递归调用中将 l 硬编码为 0 引起的。（第 4 行）

我应该怎么做才能避免这个错误？我应该如何将 l 的值放入该递归调用中？这甚至是这个错误的根源吗？如果这是一个愚蠢的问题，请随时指出，我会删除这个问题。我不得不问这个，因为我已经坚持了很长一段时间了。谢谢。

def dselect(arr, l, r, i):
    if l < r:
        #finding pivot deterministically
        medians = createMedianList(arr, l, r)
        pivot = dselect(medians, 0, len(medians) - 1, len(medians) // 2) #line4

        pivot = partition(arr, l, r, pivot)
        if pivot + 1 == i:
            return arr[pivot]
        elif pivot + 1 > i:
            return dselect(arr, l, pivot - 1, i)
        else:
            return dselect(arr, pivot + 1, r, i)

    return arr[l]

def partition(arr, l, r, pivot):
    pivotIndex, i = arr.index(pivot), l
    arr[l], arr[pivotIndex] = arr[pivotIndex], arr[l]

    for j in range(l + 1, r + 1):
        if arr[j] < arr[l]:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[l], arr[i] = arr[i], arr[l]

    return i

def createMedianList(arr, l, r):
    medians = []
    for i in range(l, (r + 1) - 5 + 1):
        temp = sorted(arr[i:i + min(5, (r - l + 1) - i)])
        medians.append(temp[len(temp) // 2])

    return medians

if __name__ == '__main__':
    arr = [5, 2, 4, 3, 1, -1]
    #arr = list(map(int, open('select.txt').read().splitlines()))
    print(dselect(arr, 0, len(arr) - 1, int(input('Which order 
    statistic to find? '))))

Answer 1

问题是 createMedianList 有时 return 是一个空列表：如果 l >= r-3 最终会发生这种情况。我建议您向 createMedianList 添加一些内容以确保它不会 return 为空列表。例如：if medians==[]:medians=[arr[0]] 或类似的东西（取决于您希望中位数具有哪些属性）。

i阶统计的确定性快速选择python（中位数方法的中位数）

deterministic quickselect for ith order statistic python(medians of median approach)

python

algorithm

error-handling

implementation

quicksort