线性时间选择问题：

给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素，（这里给定的线性集是无序的）。      

1、随机划分线性选择        

线性时间选择随机划分法可以模仿随机化快速排序算法设计。基本思想是对输入数组进行递归划分，与快速排序不同的是，它只对划分出的子数组之一进行递归处理。

利用随机函数产生划分基准，将数组a[p:r]划分成两个子数组a[p:i]和a[i+1:r]，使a[p:i]中的每个元素都不大于a[i+1:r]中的每个元素。接着"j=i-p+1"计算a[p:i]中元素个数j.如果kj，则第k小元素在子数组a[i+1:r]中。注意：由于已知道子数组a[p:i]中的元素均小于要找的第k小元素，因此，要找的a[p:r]中第k小元素是a[i+1:r]中第k-j小元素。       在最坏的情况下，例如：总是找到最小元素时，总是在最大元素处划分，这是时间复杂度为O(n^2)。但平均时间复杂度与n呈线性关系，为O(n) 。

Type RandomizedSelect(Type a[],int p,int r,int k)
{
      if (p==r) return a[p];
      int i=RandomizedPartition(a,p,r),
      j=i-p+1;
      if (k<=j) return RandomizedSelect(a,p,i,k);
      else return RandomizedSelect(a,i+1,r,k-j);
}

2、利用中位数线性时间选择

中位数：是指将数据按大小顺序排列起来，形成一个数列，居于数列中间位置的那个数据。

例子：

•按递增顺序，找出下面29个元素的第18个元素：8,31,60,33,17,4,51,57,49,35,11,43,37,3,13,52,6,19,25,32,54,16,5,41,7,23,22,46,29.

•(1)把前面25个元素分为5=floor(29/5)组； (8,31,60,33,17),(4,51,57,49,35),(11,43,37,3,13),(52,6,19,25,32),(54,16,5,41,7).

•(2)提取每一组的中值元素，构成集合{31,49,13,25,16}；

•(3)递归地使用算法求取该集合的中值，得到m=25；

•(4)根据m=25,把29个元素划分为3个子数组：

–P={8,17,4,11, 3,13,6,19,16,5,7,23,22}

–Q={25}

–R={31,60,33,51,57,49,35,43,37,52,32,54,41,46,29}

•(5)由于|P|=13,|Q|=1,k=18，所以放弃P,Q，使k=18-13-1=4，对R递归地执行本算法；

•(6)将R划分成3(floor(15/5))组：{31,60,33,51,57},{49,35,43,37,52},{32,54,41,46,29}

•(7)求取这3组元素的中值元素分别为：{51,43,41}，这个集合的中值元素是43;

•(8)根据43将R划分成3组：

–{31, 33, 35,37,32, 41, 29},{43},{60, 51,57, 49, 52,54, 46}

•(9) 因为k=4，第一个子数组的元素个数大于k，所以放弃后面两个子数组，以k=4对第一个子数组递归调用本算法；

•(10) 将这个子数组分成5个元素的一组：{31,33,35,37,32}，取其中值元素为33；

•(11) 根据33，把第一个子数组划分成{31,32,29},{33},{35,37,41};

•(12) 因为k=4,而第一、第二个子数组的元素个数为4，所以33即为所求取的第18个小元素。

Type Select(Type a[], int p, int r, int k)
{
      if (r-p<75) {
        用某个简单排序算法对数组a[p:r]排序;
        return a[p+k-1];
        };
      for ( int i = 0; i<=(r-p-4)/5; i++ )
         将a[p+5*i]至a[p+5*i+4]的第3小元素
         与a[p+i]交换位置;
      //找中位数的中位数，r-p-4即上面所说的n-5
      Type x = Select(a, p, p+(r-p-4)/5, (r-p-4)/10);
      int i=Partition(a,p,r, x),
      j=i-p+1;
      if (k<=j) return Select(a,p,i,k);
      else return Select(a,i+1,r,k-j);
}

实现步骤：

算法思路：

如果能在线性时间内找到一个划分基准使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的ε倍(0<ε<1),那么就可以在最坏情况下用O(n)时间完成选择任务。例如，当ε=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递推式T(n)<=T(9n/10)+O(n)。由此可得T(n)=O(n)。