從一個亂序數(shù)組A[1....n]中選擇排第i的數(shù)，就是經(jīng)典的選擇select問題
最Naive的辦法就是先對整個數(shù)組進行排序（可以使用quicksort/merge sort/heap sort）但是其算法復(fù)雜度為O(nlogn)，如果使用quicksort的partition的變種的話，其最差復(fù)雜度為O(n^2)，但是平均復(fù)雜度為O(n).其核心算法如下：
int randselect(int p,int r,int i)
{
if(p==r)
return arr[p];
int q = partition(p,r);//調(diào)用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;
}