了解递归函数 - 快速选择 - 查找线性时间的中位数

Question

我正在尝试实现此算法(来自此站点：https://sarielhp.org/research/CG/applets/linear_prog/median.html)。

FindKMedian( A， K ) 返回 A 中的数字，即其大小中的第 K 个。

1. 从 A = {a1， ...， an} 中随机选择一个数字 a。
2. 将 n 个数字分为两组：
   • S - 所有小于 a 的数字
   • B - 所有大于 a 的数字
3. 如果 |S|= K-1 则 a 是所需的 K 中位数。返回一个
4. 如果 |S|
5. 否则，递归调用 FindKMedian( S， K )。

@mikake回答后，我在代码末尾使用参数调用函数时出错。

import random

def quick_select(A, k, s, d):
r = random.choice(range(s, d))
pivot = partition(A, r, s, d)
if pivot == k:
return A[pivot]
elif k < pivot:
return quick_select(A, k, s, pivot-1)
else:
return quick_select(A, k, pivot + 1, d)

def partition(A, r, s, d):
j = s-1
assert s <= r
assert r <= d
temp = A[d]
A[d] = A[r]
A[r] = temp
for i in range(s, d):
if A[i] <= A[d]:
j = j+1
temp = A[j]
A[j] = A[i]
A[i] = temp
j = j+1
temp = A[j]
A[j] = A[d]
A[d] = temp
return j

random.seed(0)
A = [4, 7, 7, 2, 2, 0, 9, 8, 1, 8]
print(quick_select(A, 5, 0, 9))

我希望数字 7 从快速选择的返回中出来(所以 quick_select(A， 5， 0， 9) 意味着"一旦子数组 A[0,...,5] 被排序或一旦 A[5,...,9] 被排序，就找到 A[5]")。我可能不明白这段代码的语义应该是什么。

谢谢

Answer 1

您忘了在"else"分支中添加return语句：

def quick_select(A, k, s, d):
r = random.choice(range(s, d))
pivot = partition(A, r, s, d)
if pivot == k:
return A[pivot]
elif k < pivot:
return quick_select(A, k, s, pivot-1)
else:
return quick_select(A, k, pivot + 1, d)

Answer 2

我认为我犯的唯一错误是没有考虑数组长度为 1 的情况。所以函数"quick_select"的正确代码应该是

def quick_select(A, k, s, d):
if s == d:
return A[k]
r = random.choice(range(s, d))
pivot = partition(A, r, s, d)
if pivot == k:
return A[pivot]
elif k < pivot:
return quick_select(A, k, s, pivot-1)
else:
return quick_select(A, k, pivot + 1, d)