因工作原因，前阵子看了MTK中关于FM搜频的代码，其中记忆犹新的是一种比较实用的查找算法，我依据它的思想对这个算法做了小小的改动。
该算法的作用是在容量加大的数据集中查找前N个最大(也可以是最小，最大和最小不是算法的关键)数字，当然，这里的N一般比较小，如在100,000,000个数中查找前10个最大的数字。传统的算法是先对这100万个数排序，再取前10个，但对这么多的数字排序相当慢，由于只需取10个数，其余数字的排序实际上是无用的，因此需要一种新的算法。下面简述本文所说的算法思路：
该算法的思路是：每次在所有数据集中选出最大的数字，并将该数字设置一个标志位，已免下次遍历最大值的时候重复选中该数字。为避免查找算法的额外开销，设置标志位的方法比较重要，如果这些数据全部是整数，我们可以用位运算处理；如果是浮点数，我们可以先将这些数据放大，在一定精度范围内将其转化为整数，再使用位运算处理（当然，应该有其他的处理方式）。
写了这么多，个人觉得还是通过程序看算法容易得多。为获取大量不同数据源，我采用随机数生成了10000个整数，并在这些数字中选前10个数字。
/***************************************************
* Name: Rapid Searching Arithmetic
*
* Author: zhouliang
* Date: 2008-10-20
* Email: zhouliang531@163.com
**************************************************/
#include "stdlib.h"
#include "stdio.h"
#include "time.h"
#define MAX_BIT 0x8000 /*屏蔽的最大比特位，也可以是0x40， 0x800等*/
#define MARK(x) ((x) |= MAX_BIT) /*即(x) | = 0x8000*/
#define IS_MARK(x) ((x) & MAX_BIT) /*即(x) & 0x8000*/
#define UNMARK(x) ((x) & (MAX_BIT-1)) /*即(x) | 0x7FFF*/
#define MAX_DATA (MAX_BIT - 1) /*即0x7FFF*/
#define TOP_NUM 10 /*找出前N个最大值*/
#define TOTAL_NUM 10000 /*总个数*/
void main( void )
{
int i, j;
int data[TOTAL_NUM]; /*存储所有数据*/
int result[TOP_NUM]; /*存储查找结果*/
int max, temp;
int index;
/*确保总个数不小于TOP个数*/
if (TOP_NUM > TOTAL_NUM){
printf("Please make sure TOP_NUM <= TOTAL_NUM");
return;
}
/*以时间为种子，生成随机数*/
srand( (unsigned)time( NULL ) );
/* 生成 TOTAL_NUM个小于MAX_DATA的随机数*/
for (i=0; i<TOTAL_NUM; i++){
do {
temp = rand();
}while(temp > MAX_DATA);
data[i] =temp;
printf("%6d/n", temp);
}
/*查找最大的TOP_NUM个数字*/
for (i=0; i<TOP_NUM; i++){
max = 0;
index = -1;
for (j=0; j<TOTAL_NUM; j++){
if (!IS_MARK(data[j])){ /*避免重复选取*/
temp = UNMARK(data[j]);
if (temp > max){
max = temp;
index = j;
}
}//end if
}//end for
if (index >= 0){ /*找到最大的，标记*/
result[i] = data[index];
MARK(data[index]);
}
else{
break;
}
}//end for
printf("Top %d Number:/n", TOP_NUM);
for (i=0; i<TOP_NUM; i++){
printf("%6d/n", result[i]);
}
} // end main
为测试数据集多变，上述程序通过时间种子生成随机数，因此每次运行的时候可以得到不同的数据集。