I阶统计Python的确定性快速选择(中位数方法)

Question

dselect

在O(n(时间内的给定未排序整数(无重复(列表中找到第i阶统计量，捎带快速排序原理。 第 i 阶统计量定义为给定列表上排序版本中的第 i 个最小元素。所以一阶统计量将是最小的元素，n阶统计量将是最大的元素，依此类推......

在运行时，我在dselect函数结束时IndexError: list index out of rangereturn arr[l]。我认为错误是由于我对列表mediansdselect函数上的递归调用中0l进行硬编码而出现的。(第 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有时会返回一个空列表： 如果l >= r-3最终会发生，就会发生这种情况。 我建议您向createMedianList添加一些内容，以确保它不会返回空列表。 例如：if medians==[]:medians=[arr[0]]或类似的东西(取决于你想要中位数的属性(。