从一个乱序数组A[1....n]中选择排第i的数，就是经典的选择select问题
最Naive的办法就是先对整个数组进行排序（可以使用quicksort/merge sort/heap sort）但是其算法复杂度为O(nlogn)，如果使用quicksort的partition的变种的话，其最差复杂度为O(n^2)，但是平均复杂度为O(n).其核心算法如下：
int randselect(int p,int r,int i)
{
if(p==r)
return arr[p];
int q = partition(p,r);//调用quicksort里面的partition
int k = q-p+1;
if(i==k)
return arr[q];
if(i<k)
return randselect(p,q-1,i);
if(i>k)
return randselect(q+1,r,i-k);
}
代码如下：
#include <iostream>
#include <iterator>
#include <algorithm>
#include <cstdlib>
using namespace std;
#define MAXSIZE 100
int arr[MAXSIZE];
void fillarray()
{
for(int i=0;i<MAXSIZE;i++)
{
arr[i]=rand()%MAXSIZE;
}
}
void print(bool flag=true)
{
if(flag)
{
copy(arr,arr+MAXSIZE,ostream_iterator<int>(cout," "));
cout<<endl;
}
}
int partition(int p,int r)
{
int pivot = arr[r];
int i=p-1;
for(int j=p;j<r;j++)
{
if(arr[j]<pivot)
{
i++;
int temp = arr[j];
arr[j]=arr[i];
arr[i]=temp;
}
}
arr[r]=arr[i+1];
arr[i+1]=pivot;
return i+1;
}
void quicksort(int p,int r)
{
if(p<r)
{
int q=partition(p,r);
quicksort(p,q-1);
quicksort(q+1,r);
}
}
int randselect(int p,int r,int i)
{
if(p==r)
return arr[p];
int q = partition(p,r);
int k = q-p+1;
if(i==k)
return arr[q];
if(i<k)
return randselect(p,q-1,i);
if(i>k)
return randselect(q+1,r,i-k);
}
int main(int argc,char* argv[])
{
fillarray();
print();
//quicksort(0,MAXSIZE-1);
//print();
for(int i=0;i<MAXSIZE;i++)
cout<<randselect(0,MAXSIZE-1,i+1)<<" ";
cout<<endl;
system("pause");
return 0;
}