了解中位数选择算法？

Question

我目前在业余时间学习算法,但在学习第3章select()算法时遇到以下问题.

我知道如果我使用从A到n的数组,我可以使用select()算法来查找中位数(第n/2个最小数字).

1)但这是我正在努力理解的一点.A = [3,7,5,1,4,2,6,2].假设那是数组.每次调用Partition()后数组的内容是什么,以及每次递归调用Select()时的参数.

有人可以解释他们是如何解决这个问题的吗？

下面是2个算法的伪代码.

Select(A, p, r, k) {
    /* return k-th smallest number in A[p..r] */
    if (p==r) return A[p] /* base case */
    q := Partition(A,p,r)
    len := q – p + 1
    if (k == len) return A[q]
    else if (k<len) return Select(A,p,q-1,k)
    else return Select(A,q+1,r,k-len)
}

第二个代码是

Partition(A, p, r) { /* partition A[p..r] */
    x := A[r] /* pivot */
    i := p-1
    for j := p to r-1 {
        if (A[j] <= x) {
            i++
            swap(A[i], A[j])
        }
    }
    swap(A[i+1], A[r])
    return i+1
}

我正在使用的这本书被Anne Kaldewaij 称为算法推导.

Answer 1

该算法分两步进行.分割步骤通过拾取一些枢轴元件,然后重新排列阵列的元素使得小于枢轴的所有东西都在一侧,比枢轴更大的一切都到达另一侧,并且枢轴在正确的位置.例如,给定数组

3  2  5  1  4

如果我们选择3的枢轴,那么我们可能会像这样对数组进行分区:

2  1  3  5  4
+--+  ^  +--+
 ^    |    ^
 |    |    +--- Elements greater than 3
 |    +-------- 3, in the right place
 +------------- Elements less than 3

请注意,我们没有对数组进行排序; 我们刚刚接近排序.顺便说一下,这是quicksort的第一步.

然后该算法使用以下逻辑.假设我们想要按排序顺序(第k个最小元素)找到属于索引k的元素.然后,就我们选择的支点而言,有三种选择:

1. 枢轴位于k位置.然后,由于枢轴位于正确的位置,我们正在寻找的值必须是枢轴.我们完成了.
2. 枢轴位于大于k的位置.然后第k个最小元素必须位于数组之前的数组部分中,因此我们可以递归搜索数组中第k个最小元素的部分.
3. 枢轴位于小于k的位置.然后第k个最小元素必须位于数组上部区域的某个位置,我们可以在那里递归.

在我们的例子中,假设我们想要第二个最小的元素(位置2的元素).由于枢轴在位置3处结束,这意味着第二个最小的元素必须位于数组前半部分的某个位置,因此我们将在子阵列上进行递归

2  1

如果我们想要实际的中值元素,因为枢轴最终在数组的中间点击,我们只输出中位数为3并且完成.

最后,如果我们想要第四个最小元素之类的东西,那么由于枢轴在第4个位置之前,我们将在阵列的上半部分递归,即

5  4

并且会在这里寻找第一个最小的元素,因为在这个区域之前有三个元素.

算法的其余部分是如何进行分区步骤(可能是算法中涉及最多的部分)的详细信息,以及如何进行关于是否递归的三向选择(稍微不那么困难).但是,希望这种高级结构有助于算法更有意义.

希望这可以帮助!