随机化快排查找第k小元素和随机化查找第k小元素两种方法的比较
随机化快拍查找第k小元素顾名思义是用随机化快排将序列按从小到大排序后找第k小
随机化查找第k小元素思想是在无序序列中随机找一个数为轴，从序列最后一个开始将每个数与轴比较，比轴大的放在数组右面，比轴小的放在数组前面，全部比完后查看轴是第几小的元素（设为m），比较k和m如果相等，则找到第k小元素，如果k<m，取轴前部分在进行以上操作,如果k>m，取轴后半段进行以上操作。
如图：查找第k=3小，a[]一开始存的是要查找的序列，随机取一个数，假如取第四个（注意这里数组从1开始）值为6，那么b[]存比较后各元素，再将b[]中值按位置给相对应的a[]中，此时m=5，k<m。那么将a[]的1~4中选一个，假如选a[]中第二个，值为1，则将a[]中的1~4个以1为轴排并存在b[]中，再将b[]中值按位置给相对应的a[]中，此时m=1。那么将a[]的2~4中选一个，假如选a[]中第2个，值为4，则将a[]中的2~4个以4为轴排并存在b[]中，再将b[]中值按位置给相对应的a[]中，此时m=3，即为找到。
代码：（此代码考虑序列可能有重复值，如1，1，2，那么2是第三小）
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
unsigned long long a[50000000];//带查找序列
unsigned long long b[50000000];//找到轴后分好的序列
void suiji(unsigned long long a[],unsigned long long m,unsigned longlong r)//利用随机化快排查找第k小元素
{
if(m<r)//快排循环条件，m为数组起始，r数组未结束，每次循环进行一趟快排
{
unsigned long longtemp=0,p;
p=rand()%(r-m+1)+m;//随机在数组中找一个数，与待排序列第一个交换
temp=a[m];
a[m]=a[p];
a[p]=temp;
unsigned long longi=m;
unsigned long longj=r;
while(i<j)//i为数组起始，j为数组结束，当i等于j时数组遍历结束
{
while(a[i]<a[j]&&i<j)//a[i]为标兵，当a[i]<a[j]时不交换，j向前移动，直到i>j或a[i]>a[j]时结束
{
j--;
}
if(i<j)//此时a[i]>a[j],进行交换，并将i向后移动一个
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
i++;
}
while(a[i]<a[j]&&i<j)//a[j]为标兵，当a[i]<a[j]时不交换，i向后移动，直到i>j或a[i]>a[j]
{
i++;
}
if(i<j)//此时a[i]>a[j],进行交换，并将j向前移动一个
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
j--;
}
}
if(i==j)//此时将已进行完的序列分段在进行随机化快排
{
suiji(a,m,i-1);
suiji(a,i+1,r);
}
}
}
void chazhao(unsigned long long a[],int l,int r,int k)//利用随机化查找第k小元素
{
int n=l,m=r,p,i,q=0,v=0;
p=rand()%(r-l+1)+l; //随机取数组内的 一个数
for(i=r;i>=l;i--)//从数组的最后一个开始以轴为标准进行分段
{
if(a[i]>a[p])//当数大于轴时，将其移到轴的右边
{
b[m]=a[i];
m--;
}
elseif(a[i]<a[p]) //当数小于轴时，将其移到轴的左边
{
b[n]=a[i];
n++;
}
else//当其等于时，记录相等的数的个数
{
q++;
}
}
for(i=n;i<=m;i++)//将数值等于轴的几个数加入到b数组中
{
b[i]=a[p];
n++;
}
for(i=l;i<=r;i++)//b数组此时为分好的数列将其赋值给a以便于下一次查找
{
a[i]=b[i];
}
if((k>=(n-q))&&k<n)//第 k个数值在于其相等的几个数之间，找到第k个数
{
printf("随机化查找第k个数是%d\n",a[k]);
}
else if(k<(n-q))//第k个数在轴或与轴相同的下标的左边
{
r=n-q-1;//将要查找的数列缩短
chazhao(a,l,r,k); //调用函数进行缩短后的数列的查找
}
else if(n<=k)// 第k个数在轴或与轴相同的下标的右边
{
l=n; //将要查找的数列缩短
chazhao(a,l,r,k); //调用函数进行缩短后的数列的查找
}
}
int main()
{
int n,i,k;
printf("请输入数字个数n<=50000000：");
scanf("%d",&n);
printf("请输入k：");
scanf("%d",&k);
srand(time(NULL));
for(i=1;i<=n;i++){//随机生成待排数组
a[i]=rand();
}
clock_t beg,end;//起始时间和结束时间
double time;
beg=clock();
suiji(a,1,n);
printf("随机化快排查找第k个元素是%d\n",a[k]);
end=clock();
time=(double)(end-beg)/CLOCKS_PER_SEC;
printf("随机产生成数进行随机快排查找第k小元素的运行时间：%f s\n",time);
beg=clock();
chazhao(a,1,n,k);
end=clock();
time=(double)(end-beg)/CLOCKS_PER_SEC;
printf("随机产生成数进行随机化查找第k小元素的运行时间：%f s\n",time);
return 0;
}