0

我正在尝试实现此算法（来自此站点：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| < K-1 则 K 中值位于 B 中的某个位置。递归调用 FindKMedian( B, K - |S| - 1 )
  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 从 quickselect 的返回中出来（所以 quick_select(A, 5, 0, 9) 意味着“一旦子数组 A[0,...,5] 被排序或一次就找到 A[5] A[5,...,9] 已排序")。我可能没有明白这段代码的语义应该是什么。

谢谢

4

2 回答 2

1

您忘记return在“else”分支中添加语句：

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)
于 2019-06-03T09:45:34.813 回答
0

我认为我犯的唯一错误是没有考虑数组长度为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)
于 2019-06-03T12:22:53.067 回答