作者：jostree 转载请注明出处 http://www.cnblogs.com/jostree/p/4046399.html
使用分治算法，首先选择随机选择轴值pivot，并使的序列中比pivot小的数在pivot左边，比pivot大的数在pivot右边，即快速排序算法中的partition的过程，可以参考：快速排序算法 Quick sort。
进行partition过程后，我们随机选择的轴值为序列的第j个，且其左边有a个数，右边有b个数。
如果j=k，那么说明该轴值就是第k小个数。
如果j>k，说明第k小的数一定在轴值的左边，我们可以递归的查找左侧a个数中的第k大个数。
如果j<k，说明第k小的数一定在轴值的右侧，且其左侧的a+1个数都小于第k小的数，所以我们可以递归的查找右侧b个数中的第k-a-1小的数。
由于每次规模缩小一半，且每次处理的时间为O(n)，那么我们可以得到其平均复杂度为:T(n)=T(n/2)+n
根据主定理我们可以得到算法的复杂度为O(n)
代码如下：
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <ctime>
using namespace std;
void swap(int &a, int &b)
{
int tmp = a;
a = b;
b = tmp;
}
int partation(vector<int> &vec, int begin, int end, int pivot)
{
swap(vec[pivot], vec[begin]);
int tmp = vec[begin];
int p = begin, q = end;
while( p < q )
{
while( p < q && vec[q] >= tmp) q--;
if( p < q ) vec[p++] = vec[q];
while( p < q && vec[p] < tmp ) p++;
if( p < q ) vec[q--] = vec[p];
}
vec[p] = tmp;
return p;
}
int FindKMin(vector<int> & vec, int begin, int end, int k)
{
srand(time());
int piovt = rand()%(end-begin+)+begin;
int pos = partation(vec, begin, end, piovt);
if( pos-begin+ == k )
{
return vec[pos];
}
else if( pos-begin+ > k )
{
return FindKMin(vec, begin, pos-, k);
}
else
{
return FindKMin(vec, pos+, end, k-(pos-begin+));
}
}
int main(int argc, char *argv[])
{
int n;
vector<int> vec;
while( cin >> n )
{
vec.clear();
int k;
cin>>k;
int tmp;
for( int i = ; i < n ; i++ )
{
cin>>tmp;
vec.push_back(tmp);
}
cout<<FindKMin(vec, , vec.size()-, k)<<endl;
}
}
该方法的最坏复杂度为$O(n^2)$，最坏情况是第一阶段每次选择的轴都为最大的数，并递归计算前n-1个数的第k小数，直到第k小数为这个序列的最大值为止。第二阶段每次选择的轴为最小的数，直到只剩下第k小数这一个数。那么该复杂度为$O(n^2)$。
我们可以使用另一种方法来替代随机选择轴值，并使得该算法的最坏情况的复杂度也为O(n)，选择轴值方法如下：
1. 将输入数组的n个元素划分为$\lfloor n/5 \rfloor$，每组5个元素，至多只有一组由剩下的nmod5个元素组成。
2. 寻找$\lceil n/5 \rceil$个组中每组的中位数，即对其进行排序，从而找到$\lceil n/5 \rceil$个中位数，并对这$\lceil n/5 \rceil$个中位数组成的数组继续递归调用找出其轴值。
使用该方法找到的轴值并不是数组真正的中位数。但是它具有一定的性质，在大于轴值的那些中位数的组且不包括最后个数少于5的那个组中，每组至少有3个数大于轴值。不计算这两个组，大于轴值的元素个数至少为：
\begin{equation} 3(\lceil \frac{1}{2}\lceil \frac{n}{5}\rceil\rceil -2) \geq \frac{3n}{10}-6 \end{equation}
从而时间复杂度为：$T(n) \leq T(\lceil n/5 \rceil ) + T(7n/10+6) + O(n) = O(n)$
选择轴值的代码，需要建立一个类unit来保存第i个数的值和其位置，并且最终返回轴值的位置。main函数包括了数组长度为4-6的数全排列的测试。
代码如下：
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class unit
{
public:
int x, num;
unit(int xx=, int nn=)
{
x = xx;
num = nn;
}
bool operator < (const unit &a) const
{
return this->x < a.x;
}
};
int getp(vector<unit> vec)
{
if( vec.size() <= )
{
sort(vec.begin(), vec.end());
return vec[vec.size()/].num;
}
vector<unit> small;
unit tmp;
for( int i = ; i < vec.size()-vec.size()% ; i+= )//i is the start index in the team
{
sort(vec.begin()+i, vec.begin()+i+);
// for( int j = 0 ; j < 5 ; j++ )
// {
// cout<<vec[i+j].x<<" ";
// }
// cout<<endl;
tmp.x = vec[i+].x;
tmp.num = vec[i+].num;
small.push_back(tmp);
}
int remain = vec.size()%;
int teamnum = vec.size()/;
if( remain != )
{
sort(vec.begin()+teamnum*, vec.end());
tmp.x = vec[teamnum*+remain/].x;
tmp.num = vec[teamnum*+remain/].num;
small.push_back(tmp);
}
// for( int i = 0 ; i < small.size() ; i++ )
// {
// cout<<small[i].x<<" ";
// }
// cout<<endl;
return getp(small);
}
int getpivot(const vector<int> vec)
{
vector<unit> vecunit;
unit tmp;
for( int i = ; i < vec.size() ; i++ )
{
tmp.x = vec[i];
tmp.num = i;
vecunit.push_back(tmp);
}
return getp(vecunit);
}
int main(int argc, char *argv[])
{
vector<int> a;
for( int i = ; i < ; i++ )
{
a.clear();
for( int j = ; j < i ; j++ )
{
a.push_back(j);
}
cout<<endl;
do{
cout<<"array is ";
for( int k = ; k < a.size() ; k++ )
{
cout<<a[k]<<" ";
}
cout<<endl;
cout<<"result "<<getpivot(a)<<endl;
}while(next_permutation(a.begin(), a.end()));
}
}