文档介绍：线性时间选择问题:给定线性序集中n个元素和一个整数k,1≤k≤n,要求找出这n个元素中第k小的元素,(这里给定的线性集是无序的)。
       1、随机划分线性选择
       线性时间选择随机划分法可以模仿随机化快速排序算法设计。基本思想是对输入数组进行递归划分,与快速排序不同的是,它只对划分出的子数组之一进行递归处理。
       程序清单如下:
[cpp] view plain copy
//2d9-1 随机划分线性时间选择  
#include ""  
#include <iostream>   
#include <ctime>  
using namespace std;   
  
int a[] = {5,7,3,4,8,6,9,1,2};  
  
template <class Type>  
void Swap(Type &x,Type &y);  
  
inline int Random(int x, int y);  
  
template <class Type>  
int Partition(Type a[],int p,int r);  
  
template<class Type>  
int RandomizedPartition(Type a[],int p,int r);  
  
template <class Type>  
Type RandomizedSelect(Type a[],int p,int r,int k);  
  
int main()  
{  
    for(int i=0; i<9; i++)  
    {  
        cout<<a[i]<<" ";  
    }  
    cout<<endl;  
    cout<<RandomizedSelect(a,0,8,3)<<endl;  
}  
  
template <class Type>  
void Swap(Type &x,Type &y)  
{  
    Type temp = x;  
    x = y;  
    y = temp;  
}  
  
inline int Random(int x, int y)  
{  
     srand((unsigned)time(0));  
     int ran_num = rand() % (y - x) + x;  
     return ran_num;  
}  
  
template <class Type>  
int Partition(Type a[],int p,int r)  
{  
    int i = p,j = r + 1;  
    Type x = a[p];  
  
    while(true) &