#include <ctime>
#include <iostream>
using namespace std; template <class Type>
void Swap(Type &x,Type &y); inline int Random(int x, int y); template <class Type>
void BubbleSort(Type a[],int p,int r); template <class Type>
int Partition(Type a[],int p,int r,Type x); template <class Type>
Type Select(Type a[],int p,int r,int k); void main()
{
//初始化数组
int a[]; //必须放在循环体外面
srand((unsigned)time()); for(int i=; i<; i++)
{
a[i] = Random(,);
cout<<"a["<<i<<"]:"<<a[i]<<" ";
}
cout<<endl; cout<<"第23小元素是"<<Select(a,,,)<<endl; //重新排序，对比结果
BubbleSort(a,,);
for(i=; i<; i++)
{
cout<<"a["<<i<<"]:"<<a[i]<<" ";
}
cout<<endl;
} template <class Type>
void Swap(Type &x,Type &y)
{
Type temp = x;
x = y;
y = temp;
} inline int Random(int x, int y)
{
int ran_num = rand() % (y - x) + x;
return ran_num;
} //冒泡排序
template <class Type>
void BubbleSort(Type a[],int p,int r)
{
//记录一次遍历中是否有元素的交换
bool exchange;
for(int i=p; i<r;i++)
{
exchange = false ;
for(int j=; j<=r-i; j++)
{
if(a[j]<a[j-])
{
Swap(a[j],a[j-]);
exchange = true;
}
}
//如果这次遍历没有元素的交换,那么排序结束
if(false == exchange)
{
break ;
}
}
} template <class Type>
int Partition(Type a[],int p,int r,Type x)
{
int i = p-,j = r + ; while(true)
{
while(a[++i]<x && i<r);
while(a[--j]>x);
if(i>=j)
{
break;
}
Swap(a[i],a[j]);
}
return j;
} template <class Type>
Type Select(Type a[],int p,int r,int k)
{
if(r-p<)
{
BubbleSort(a,p,r);
return a[p+k-];
}
//(r-p-4)/5相当于n-5
for(int i=; i<=(r-p-)/; i++)
{
//将元素每5个分成一组，分别排序，并将该组中位数与a[p+i]交换位置
//使所有中位数都排列在数组最左侧，以便进一步查找中位数的中位数
BubbleSort(a,p+*i,p+*i+);
Swap(a[p+*i+],a[p+i]);
}
//找中位数的中位数
Type x = Select(a,p,p+(r-p-)/,(r-p-)/);
i = Partition(a,p,r,x);
int j = i-p+;
if(k<=j)
{
return Select(a,p,i,k);
}
else
{
return Select(a,i+,r,k-j);
}
}
提醒：此篇需要先理解快速排序。
[图解+例子]
一、建立随机数组
（共27个数）（代码中为100个数，为了放得下举的例子改为27个）
二、给线性时间选择函数Select()传参
Type a[] 数组a
int p 起始位置
int r 结束位置
int k 查找第k小
三、判断
元素个数<75 不需要线性选择--》直接进行冒泡排序返回a[p+k-1](第k小元素)
元素个数>75 进行线性选择 --》进行下一步
四、线性时间选择
1- 分组并取各组中位数 （将元素每5个分成一组，分别排序，并将该组中位数与a[p+i]交换位置 ）【图中绿线12345表示要交换的一对对数据】
for(int i=0; i<=(r-p-4)/5; i++)
{
BubbleSort(a,p+5*i,p+5*i+4);
Swap(a[p+5*i+2],a[p+i]);
}
目的：使所有组的中位数都排列在数组最左侧，以便进一步查找中位数的中位数
2- 查找中位数的中位数
Type x = Select(a , p , p+(r-p-4)/5 , (r-p-4)/10 );
p到p+(r-p-4)/5为中位数的范围，p+(r-p-4)/5 ÷ 2 = (r-p-4)/10-->中位数的中位数
----------------------------------------------------------------------------------------------------------
3-用找到的中位数的中位数做为快速排序的标准进行一趟快速排序（前面有篇讲的快速排序为了方便直接用第一个做标准，也有用随机数做标准的）
i = Partition(a,p,r,x);
排序结束后，标准元素将数组分为三部分：左，标准元素，右。
快排讲过啦，这里快速排序省略图解啦 ！想看点这里 快速排序
------------------------------------------------------------------------------------------------------------
4-判断
快速排序后看成三部分：左，标准元素，右。
左都比标准元素小，右都比它大；（此时左右还是乱序，只有标准元素找到了它最终应该排的位置，这里不清晰先看快速排序那篇文章）
所以判断下我们要找的第k小是比它大（在右）还是比它小（在左）；
int j = i-p+1;
if(k<=j)
{
return Select(a,p,i,k);
}
else
{
return Select(a,i+1,r,k-j);
}
i为快速排序返回值，j = i - 起始位置 + 1;
小于或者等于，对左半段重复上述操作（递归）；
反之，对右半段。
-----------------------------------------------------------------------------------------------------------------
[特例]
有空更新。。。
[总结]
线性时间选择其实就是————>>快速排序的加强版，
快速排序中的标准元素变为————>>分组后取得的各组中位数的中位数。
所以多了一步取中位数的操作而已。
本人保留解析著作权。
算法引用自 王晓东. 计算机算法设计与分析[M]. 电子工业出版社, 2012.