算法导论第九章——中位数和顺序统计量

在由n个元素组成的集合中，第i个顺序统计量是该集合第i小的元素。当n为奇数时，中位数唯一，当n为偶数时，存在两个中位数，分别位于 $i = n/2$ 和 $i=(n+1)/2$ 处。我们取较小的下中位数作为我们讨论的中位数。

本章将讨论从从n个元素中选择第i个顺序统计量的问题，并假设所有元素都是互异的。
我们将这一问题形式化定义为如下的选择问题：

输入：一个包含n个数的集合A和一个整数i， $1<=i<=n$
输出:元素 $x∈A$ ,且A中恰有i-1个元素属于他。
我们可以再 $O(nlgn)$ 的时间内解决这个选择问题，但我们会有一些更快的算法。

1. 最小值和最大值

在一个n个元素的集合中，我们很容易发现要做n-1次比较才能得到最小元素，并且这是最优算法。

同时找到最大值和最小值

在某些应用中，我们必须找出一个包含n个元素集合中的最大值和最小值。
我们可以用渐进最优的 $Θ(n)$ 次比较，分别独立求出最小值和最大值，共需要2n-2次比较。
事实上，我们只需要至多 $3int(n/2)$ 次比较就可以同时找到最大值和最小值。
我们取两个输入元素，相互比较，将较小的与最小值比较，较大的与最大值比较，这样每两个元素可以进行三次比较。

2.期望时间为线性的选择算法

我们本节将给出渐进运行时间为 $Θ(n)$ 的选择算法，该算法已快速排序为原型，对数组进行递归划分，但不同的是，快排会递归处理划分的两边，而该算法只处理划分的一边。
python代码描述

def randomSelect(A,p,r,i):
    if p==r:
        return A[p]
    q = randomPartition(A,p,r)
    if i==q:
        return A[q]
    elif i<q:
        return randomSelect(A,p,q-1,i)
    else:
        return randomSelect(A,q+1,r,i)

该算法的运行过程如下：
第一行检查递归的基本情况，即此时只包括一个元素，那么这个元素即为所求的第i小数
递归情况下，调用划分算法得到两个子数组， $A[p..q-1]和A[q+1..r]$ ，使得左数组每个元素都小于 $A[q]$ ，而右边的数组每个元素都大于 $A[q]$ 。
与快速排序一样，我们称这个元素为主元。
随后检查 $A[q]$ 是否为第i小的元素，如果是，则返回 $A[q]$ ,否则，算法要确定第i小的元素落在哪一个区间之中。并进入相应的区间进行递归查找。
该算法的最坏运行时间为 $Θ(n^2)$ ,但由于该算法是随机化的，所以该算法有线性的期望运行时间，不存在能导致最坏情况的输入。
为了分析该算法的期望运行时间，我们设该算法在n个元素上的运行时间为 $T(n)$ ,是一个随机变量。

稍后证明，看完随机化一章后。暂且跳过。

3. 最坏情况为线性时间的选择算法

像随机选择算法一样，该算法通过对数组的递归划分来找出所需要素，但是，该算法能够得到对数组的一个好的划分。该算法使用的也是快排的partition算法，但做了修改，把划分的主元也作为输入参数。
执行步骤如下：
1 .将输入的n个元素划分为 $int(n/5)$ 组，每组5个元素，且至多有一组由剩下的 $n$ $mod$ $5$ 个元素组成。

寻找所有组中每一组的中位数——即对每组元素进行排序，然后确定每组有序元素的中位数。
对于第二步找出的所有中位数，递归调用select以找出其中的中位数x
利用修改过的partition版本，按中位数的中位数x对输入数组进行划分，让x成为第k小的数。
如果i=k，返回x，否则，在低区调用select找出第i小的元素，若i>k，则在高区递归查找第i小的元素

待续