介绍：
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小的数字还慢，不知道哪里出了问题，请大家指教。
代码示例：
1<!doctype html> 2<html> 3<head> 4<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 5<title>BFPRT线性查找算法</title> 6</head> 7<body> 8<script> 9var count = 10000, 10 num = testCount = 500, 11 i, 12 exeCount, 13 exeTimeArr = [], 14 k, 15 failArr = [], 16 17 sortFn = function(a, b){ 18 return a - b; 19 }, 20 21 bfprtSearch = function(a, k){ 22 23 var arrs = [], 24 middle, 25 middleArr = [], 26 middleIndex, 27 sortedArr = [], 28 last, 29 i, j, h, len; 30 31 if(a.length <= 5){ 32 33 if(a.length == 1) return a[0]; 34 35 a.sort(sortFn); 36 return a[k-1]; 37 } 38 39 // 以5个数字为一组，排序并记录中位数 40 while(a.length >= 5){ 41 sortedArr = a.splice(0, 5).sort(sortFn); 42 middleArr.push( sortedArr[2] ); 43 arrs.push(sortedArr); 44 } 45 last = a; 46 47 a = []; 48 groupNum = arrs.length; 49 50 // 得到排序后的数组 51 while(arrs.length){ 52 a = a.concat( arrs.shift() ); 53 } 54 a = a.concat(last); 55 //console.log('得到排序后的数组', a); 56 57 // 中位数前置 58 for(i=0,len=middleArr.length;i<len;i++){ 59 middleIndex = i * 5 + 2; 60 a[i] = [ a[middleIndex], a[middleIndex] = a[i] ] [0]; 61 } 62 //console.log('中位数前置', a); 63 64 // 获取中位数数组中的中位数 65 middleArr.sort(sortFn); 66 middleIndex = Math.floor( (len - 1) / 2); 67 middle = middleArr[middleIndex]; 68 //console.log('获取中位数数组中的中位数', middle); 69 70 // 根据上一步得到的中位数对数据进行交换 71 for(i=0,j=a.length-1;j>i;j--){ 72 73 if(a[j] > middle){ 74 continue; 75 }else{ 76 while(a[i] < middle){ // 小于对比中位数则略过 77 i++; 78 79 if(i > j) break; 80 } 81 } 82 83 if(i > j){ 84 break; 85 }else{ 86 a[j] = [ a[i], a[i] = a[j] ] [0]; // 将小于对比中位数的数前置 87 } 88 } 89 //console.log('根据上一步得到的中位数对数据进行交换', a, j, k); 90 91 h = j + 1; 92 if(h+1 == k){ // 前面有ｋ－１个数，刚好获取到 93 return middle; 94 95 }else if(h+1 > k){ // 第k小的数在前段数组里 96 return bfprtSearch( a.slice(0, h), k ); 97 98 }else{ // 第N小的数在后段数组里，重置第k小的k值 99 return bfprtSearch( a.slice(h), k - h); 100 } 101 102 return a.slice(0, j); 103 104 }; 105 106var body = document.getElementsByTagName('body')[0]; 107var log = function(s){ 108 109 var p = document.createElement('p'); 110 var ps = document.getElementsByTagName('p'); 111 112 p.innerHTML = s; 113 114 ps.length ? 115 body.insertBefore(p, ps[0]) : 116 body.appendChild(p); 117 118 //document.write(s + '<br />'); 破坏文档结构 119 //firefox下使用console.log并开启firebug会影响执行 120} 121 122function exeTest( callback ){ 123 124 function test(){ 125 var cost, 126 startTime, 127 result, 128 arr = [], 129 sortArr, 130 tmp; 131 132 testCount--; 133 134 // 构建随机数组 135 for(i=0;i<count;i++){ 136 arr.push( Math.round(Math.random() * count) ); // 0 - count 137 } 138 139 k = Math.floor(Math.random() * count) + 1; 140 141 tmp = arr.slice(0); 142 sortArr = arr.slice(0).sort(sortFn); 143 144 //console.log(arr); 145 //console.log(sortArr); 146 147 startTime = + new Date(); 148 result = bfprtSearch(arr, k); 149 150 //console.log(result == sortArr[k-1], result); 151 152 if(result != sortArr[k-1]){ 153 tmp.unshift('K为'+ k + '!!!'); 154 failArr.push(tmp); 155 } 156 157 exeTimeArr.push(cost = new Date() - startTime); //花费的毫秒数 158 159 log('本次测试查找'+ (result == sortArr[k-1] ? '成功' : '失败') +' 第'+ k +'小的数，花费 '+ cost +' 毫秒, 还剩 '+ testCount +' 次测试'); 160 161 if(testCount == 0 && typeof callback == 'function'){ 162 163 callback(); 164 165 }else{ 166 167 // 预防浏览器挂起 168 setTimeout(test, 10); 169 } 170 } 171 172 test(); 173} 174 175function callback(){ 176 var sum = 0; 177 var result = '数组里有'+ count +'个随机数, 执行'+ num +'次后花费的毫秒数' + '<br />' + 178 '最大毫秒数为' + Math.max.apply(null, exeTimeArr) + '<br />' + 179 '最小毫秒数为' + Math.min.apply(null, exeTimeArr) + '<br />'; 180 181 exeTimeArr.forEach(function(value) { 182 sum += value; 183 }) 184 185 result += '平均毫秒数为' + Math.round( sum / num ) + '<br />' ; 186 result += '查找失败次数' + failArr.length ; 187 188 if(failArr.length){ 189 190 result += '<br />失败的数组为：<br />'; 191 192 failArr.forEach(function(data){ 193 result += data.join(',') + '<br />'; 194 }) 195 196 } 197 198 log(result); 199} 200 201// 开始测试 202exeTest(callback); 203 204</script> 205</body> 206</html>