中位数和顺序统计学

本章讨论从一个由n个不同数值构成的集合中选择其第i个顺序统计值的问题。为方便起见，假设集合中的数互异。
Input：一个包含n个（不同的）数的集合A和一个数i，Day6 - 图1.
Output：Day6 - 图2
该选择问题可以在O(nlgn)时间内解决，因为可以用堆排序或合并排序对输入数据进行排序，然后在输出数组中标出第i个元素即可。但还有其他更快的解法。

最大值和最小值

  1. public int Minmum(A){
  2.     int min = A[0];
  3.     for(int i : A){
  4.         if(min>i)
  5.             min = i
  6.     }
  7.     return min; 
  8. }

以期望线性时间做选择

介绍一种用来解决选择问题的分治算法，即RANDOMIZED-SELECT算法，以 快速排序算法 为模型。与快速排序不同的是，RANDOMIZED-SELECT 只处理划分的一边 。这一差异使得快速排序的期望运行时间是 Θ(nlgn) ,而RANDOMIZED-SELECT的期望时间是 Θ(n) 。

  1. RANDOMIZED-SELECT(A,p,r,i)
  2. if(p==r)
  3.     then return A[p]
  4. q = RANDOMIZED-PARTITION(A,p,r);
  5. k = q-p+1
  6. if i=k
  7.     then return A[q]
  8. else if i<k
  9.     then return RANDOMIZED-SELECT(A,p,q-1,i);
  10. else
  11.     then return RANDOMIZED-SELECT(A,q+1,r,i-k)

在平均情况下，任何顺序统计量（特别是中位数）都可以在线性时间内得到 ，证明略。

最坏情况线性时间的选择

现在来看一个最坏情况运行时间为O(n)的选择算法SELECT。该算法的基本思想是要 保证对数组的划分上是个好的划分 。算法通过执行下列步骤来确定一个有n>1个元素的输入数组中的第i小的元素：

  • 将输入数组的n个元素划分为n/5组，每组5个元素，且至多只有一个组由剩下的n mod 5个元素构成。
  • 寻找n/5个组中每一组的中位数，首先对每组中的元素（至多5个）进行插入排序，然后从排序过的序列中选出中位数。
  • 对第2步中找出的n/5个中位数，递归调用SELECT以找出中位数x
  • 利用修改过的PARTITION过程，按中位数的中位数x对输入数组进行划分。让k比划分低区的元素数目多1，所以x是第k小的元素。
  • 如果i==k，则返回x，否则，如果，ik，在高区递归调用SELECT。