第k元素代码,C/C++代码库,德仔网

代码语言

代码分类

【C/C++】第k元素

作者:昊强 / 发布于2016/4/21/ 517

//取第k个元素,k=0..n-1
//平均复杂度O(n)
//注意a[]中的顺序被改变

#define _cp(a,b) ((a)<(b))
typedef int elem_t;

elem_t kth_element(int n,elem_t* a,int k){
	elem_t t,key;
	int l=0,r=n-1,i,j;
	while (l<r){
		for (key=a[((i=l-1)+(j=r+1))>>1];i<j;){
			for (j--;_cp(key,a[j]);j--);
			for (i++;_cp(a[i],key);i++);
			if (i<j) t=a[i],a[i]=a[j],a[j]=t;
		}
		if (k>j) l=j+1;
		else r=j;
	}
	return a[k];
}

评论列表

本站所提供的代码，版权归原作者所有，若有侵犯作者版权，请与我们联系，我们将立即删除或修改。谢谢!
本站所有代码发布及提供者。

　　

试试其它关键字

　第k元素　

同语言下

可能有用的

昊强贡献的其它代码(14)