得到第K个大的数算法研究

本文为原创，如需转载，请注明作者和出处，谢谢！

第一种算法是最容易想到的，就是利用快速排序的思想，将一个数组分成以某一个数X为轴，左边的所有的数都比X小，而右边的数都比X大。但我快速排序不同的是，在这个算法中只考虑X的一边，而不是两边都考虑。

如果X的位置是i,那么要得到第k个数，如果k<=i, 那么这个数一定在i的左边，否则在i的右边。

源码如下：

<!--<br /> <br /> Code highlighting produced by Actipro CodeHighlighter (freeware)<br /> http://www.CodeHighlighter.com/<br /> <br /> -->#include<stdio.h>
#include<stdlib.h>
intnew_random(intmin,intmax)
{
return(min+(int)(((float)rand()/RAND_MAX)*(max-min)));
}
voidswap(int*a,int*b)
{
intc=*a;
*a=*b;
*b=c;
}

intpartition(intA[],intp,intr)
{
inti=p-1,j;
for(j=p;j<r;j++)
{
if(A[j]<=A[r])
{
i++;
swap(&A[i],&A[j]);
}
}
swap(&A[i+1],&A[r]);
returni+1;
}

intrandomize_partition(intA[],intp,intr)
{
inti=new_random(p,r);
swap(&A[i],&A[r]);
returnpartition(A,p,r);
}

//第一种算法
intrandomized_select(intdata[],intp,intr,intk)
{
if(k>(r-p+1))return0;
if(p==r)returndata[p];
inti=randomize_partition(data,p,r);
//inti=partition(data,p,r);//不好使，死循环,必须用随机数，在第二步时总是在最大数处划分

intcount=i-p+1;
if(k<=count)
returnrandomized_select(data,p,i,k);
else
returnrandomized_select(data,i+1,r,k-count);
}

另外一种对这种算法做了一下改进，即将数组每5个数一组进行排序，然后取得它的中位数，再对这些中位数进行排序。然后先出的轴X最比较好的，因此X的左边和右边的数总是很平均，所以平均查找速度更快。算法如下：

<!--<br /> <br /> Code highlighting produced by Actipro CodeHighlighter (freeware)<br /> http://www.CodeHighlighter.com/<br /> <br /> -->voidquicksort(intdata[],intb,inte)
{
if(b<e)
{
intk=partition(data,b,e);
quicksort(data,b,k-1);
quicksort(data,k+1,e);
}
}

intpartition1(intA[],intp,intr,intx)
{
inti=p-1,j;
for(j=p;j<=r;j++)
{
if(A[j]<=x)
{
i++;
swap(&A[i],&A[j]);
}
}
A[i+1]=x;
returni+1;
}
//第二种算法
intselect_new(intdata[],intp,intr,intk)
{
if(r-p<75)
{
quicksort(data,p,r);
returndata[p+k-1];
}
inti;
for(i=0;i<=(r-p-4)/5;i++)
{
quicksort(data,p+5*i,p+5*i+4);
swap(&data[p+5*i+2],&data[p+i]);
}
intx=select_new(data,p,p+(r-p-4)/5,(r-p-4)/10);//得到更好的轴X
i=partition1(data,p,r,x);
intcount=i-p+1;
if(k<=count)
returnselect_new(data,p,i,k);
else
returnselect_new(data,i+1,r,k-count);
}

intmain()
{
intdata[]={3,1,7,34,8,11,678,12,-1,100};
printf("%d\n",randomized_select(data,0,9,2));
intdata1[]={3,1,7,34,8,11,678,12,-1,100};
printf("%d\n",select_new(data1,0,9,2));

return0;
}

国内最棒的Google Android技术社区（eoeandroid），欢迎访问！

《银河系列原创教程》发布

《Java Web开发速学宝典》出版，欢迎定购