要求：给定一个数组array[n],寻找大小排在第k的元素
思路一：最直接的思路就是先排序，这样可以直接通过数组下标找到第k大的元素，最好的快速排序时间复杂度为O(nlogn)。
思路二：我们可以在快速排序的基础上进行改进，即运用快速排序框架，不过快速排序中的基准元素，我们采用随机划分而不是快速排序那样指定为一个固定的值。此方法时间复杂度为O(n)
此思路的代码如下：
#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<time.h>
using namespace std;
int random(int p,int r)
{
return (rand()%(r-p+1)+p);
}
int partion(float a[],int p,int r)
{
int x = a[r];
int i=p-1;
for(int j = p;j<r;++j){
if(a[j]<=x){
++i;
swap(a[i],a[j]);
}
}
swap(a[i+1],a[r]);
return i+1;
}
int part(float a[],int p,int r)
{
int i=random(p,r);
swap(a[i],a[p]);
return partion(a,p,r);
}//该算法的主体框架为快速排序的框架，但与快速排序不同的是，快速排序是通过递归框架
//对数组进行排序，但此算法通过递归框架只对数组中的第k元进行筛选，所以递归的出口不同
//快速排序中的递归出口为if(high>low)，但该函数的递归出口为if(k-1==i-p)
//与快速排序相同的是都存在一个划分过程
//如果单是求第k元的话，该函数的参数可以简化，即p=0，这样j==i
float select(float a[],int p,int r,int k)
{//在数组a中从下标p到r中求第k小的元素
if(p==r)
{
return a[p];
}
int i=part(a,p,r);//对数组a随机划分
int j=i-p;//+1;//此处之所以要i-p因为该函数从数组p下标开始，而不一定从0开始
if(k-1==j)//因为数组下标从0开始，所以第k小元素下标为k-1
return a[i];//递归出口，返回该元素
else if(k-1<j)
return select(a,p,i-1,k);
else
return select(a,i+1,r,k-j-1);
}
void bubble(float a[], int n)
{
int i,flag=1;
for(i=1;i<=n-1&&flag;i++)
{
flag=0;
for(int j=0;j<n-i;j++)
{
if(a[j+1]<a[j])
{
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
flag=1;
}
}
}
}
int main()
{
int n,t,i,j=0;
cout<<"请输入元素的个数n"<<endl;
cin>>n;
// float *p=(float *)malloc(n*sizeof(float));
float *p=new float[n];
cout<<"请输入每个元素的值"<<endl;
for(i=0;i<n;i++)
{
cin>>p[i];
}
cout<<"请输入要寻找第k元的k值"<<endl;
int k;
cin>>k;
cout<<select(p,0,n-1,k)<<endl;
return 1;
}
程序运行结果如下：
