首页 > 代码库 > BFPRT线性查找算法

BFPRT线性查找算法

2024-07-15 01:10:47   225人阅读

介绍：

BFPRT算法解决的问题十分经典，即从某n个元素的序列中选出第k大（第k小）的元素，通过巧妙的分 析，BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似，当然，为使得算法在最坏情况下，依然能达到o(n)的时间复杂 度，五位算法作者做了精妙的处理。

时间复杂度

O(N)

算法步骤：

1. 将n个元素每5个一组，分成n/5(上界)组。

2. 取出每一组的中位数，任意排序方法，比如插入排序。

3. 递归的调用selection算法查找上一步中所有中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个。

4. 用x来分割数组，设小于等于x的个数为k，大于x的个数即为n-k。

5. 若i==k，返回x；若i<k，在小于x的元素中递归查找第i小的元素；若i>k，在大于x的元素中递归查找第i-k小的元素。

终止条件：n=1时，返回的即是i小元素。


测试结果：

数组里有10000个随机数, 执行500次后花费的毫秒数
最大毫秒数为208
最小毫秒数为86
平均毫秒数为102
查找失败次数0

疑问：

这里的代码示例耗时过长，高达100ms，比排序获取第k小的数字还慢，不知道哪里出了问题，请大家指教。

代码示例： 

<!doctype html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>BFPRT线性查找算法</title>
</head>
<body>
<script>
var count = 10000,
	num = testCount = 500,
    i,
    exeCount,
	exeTimeArr = [],
	k,
	failArr = [],

	sortFn = function(a, b){
		return a - b;
	},

    bfprtSearch = function(a, k){

		var arrs = [],
			middle,
			middleArr = [],
			middleIndex,
			sortedArr = [],
			last,
			i, j, h, len;

		if(a.length <= 5){

			if(a.length == 1) return a[0];

			a.sort(sortFn);
			return a[k-1];
		}
		
		// 以5个数字为一组，排序并记录中位数
		while(a.length >= 5){
			sortedArr = a.splice(0, 5).sort(sortFn);
			middleArr.push( sortedArr[2] );
			arrs.push(sortedArr);
		}
		last = a;
	
		a = [];
		groupNum = arrs.length;

		// 得到排序后的数组
		while(arrs.length){
			a = a.concat( arrs.shift() );
		}
		a = a.concat(last);
		//console.log(‘得到排序后的数组‘, a);

		// 中位数前置
		for(i=0,len=middleArr.length;i<len;i++){
			middleIndex = i * 5 + 2;
			a[i] = [ a[middleIndex], a[middleIndex] = a[i] ] [0];
		}
		//console.log(‘中位数前置‘, a);

		// 获取中位数数组中的中位数
		middleArr.sort(sortFn);
		middleIndex = Math.floor( (len - 1) / 2);
		middle = middleArr[middleIndex];
		//console.log(‘获取中位数数组中的中位数‘, middle);

		// 根据上一步得到的中位数对数据进行交换
		for(i=0,j=a.length-1;j>i;j--){

			if(a[j] > middle){
				continue;
			}else{
				while(a[i] < middle){ // 小于对比中位数则略过
					i++;

					if(i > j) break;
				}
			}

			if(i > j){
				break;
			}else{
				a[j] = [ a[i], a[i] = a[j] ] [0]; // 将小于对比中位数的数前置
			}
		}
		//console.log(‘根据上一步得到的中位数对数据进行交换‘, a, j, k);

		h = j + 1;
		if(h+1 == k){ // 前面有ｋ－１个数，刚好获取到
			return middle;

		}else if(h+1 > k){ // 第k小的数在前段数组里
			return bfprtSearch( a.slice(0, h), k );

		}else{ // 第N小的数在后段数组里，重置第k小的k值
			return bfprtSearch( a.slice(h), k - h);
		}

		return a.slice(0, j);
 
    };

var body = document.getElementsByTagName(‘body‘)[0];
var log = function(s){

	var p = document.createElement(‘p‘);
	var ps = document.getElementsByTagName(‘p‘);

	p.innerHTML = s;

	ps.length ?
		body.insertBefore(p, ps[0]) :
		body.appendChild(p);

	//document.write(s + ‘<br />‘); 破坏文档结构
	//firefox下使用console.log并开启firebug会影响执行
}

function exeTest( callback ){

	function test(){
		var cost,
			startTime,
			result,
			arr = [], 
			sortArr,
			tmp;

		testCount--;

		// 构建随机数组
		for(i=0;i<count;i++){
			arr.push( Math.round(Math.random() * count) ); // 0 - count
		}

		k = Math.floor(Math.random() * count) + 1;

		tmp = arr.slice(0);
		sortArr = arr.slice(0).sort(sortFn);

		//console.log(arr);
		//console.log(sortArr);
		
		startTime = + new Date();
		result = bfprtSearch(arr, k);

		//console.log(result == sortArr[k-1], result);

		if(result != sortArr[k-1]){
			tmp.unshift(‘K为‘+ k + ‘!!!‘);
			failArr.push(tmp);
		}

		exeTimeArr.push(cost = new Date() - startTime); //花费的毫秒数

		log(‘本次测试查找‘+ (result == sortArr[k-1] ? ‘成功‘ : ‘失败‘) +‘ 第‘+ k +‘小的数，花费 ‘+ cost +‘ 毫秒, 还剩 ‘+ testCount +‘ 次测试‘);

		if(testCount == 0 && typeof callback == ‘function‘){

			callback();

		}else{

			// 预防浏览器挂起
			setTimeout(test, 10);
		}
	}

	test();
}

function callback(){
	var sum = 0;
    var result = ‘数组里有‘+ count +‘个随机数, 执行‘+ num +‘次后花费的毫秒数‘ + ‘<br />‘ +
					  ‘最大毫秒数为‘ + Math.max.apply(null, exeTimeArr) + ‘<br />‘ +
					  ‘最小毫秒数为‘ + Math.min.apply(null, exeTimeArr) + ‘<br />‘;

	exeTimeArr.forEach(function(value) {
		sum += value;
	})

	result += ‘平均毫秒数为‘ + Math.round( sum / num ) + ‘<br />‘ ;
	result += ‘查找失败次数‘ + failArr.length ;

	if(failArr.length){

		result += ‘<br />失败的数组为：<br />‘;

		failArr.forEach(function(data){
			result += data.join(‘,‘) + ‘<br />‘;
		})

	}

	log(result);
}

// 开始测试
exeTest(callback);

</script>
</body>
</html>


联系
我们