有1000万个随机的整数中想实现尽可能快的查找，有什么高效的算法？（平均查找时间要近可能的快，单个数据查找最坏比较次数不能超过12次。

Question

有1000万个随机的整数中想实现尽可能快的查找，有什么高效的算法？（平均查找时间要近可能的快，单个数据查找最坏比较次数不能超过12次。内存使用不能超过512M）

Answer 1

Quick Sort应该比较快。比堆排序，Shell快得多！

Answer 2

楼上的：
Quick sort排序1000万个数？
并且即便是已经排序了，使用折半查找，也无法算法楼主的最多12次比较的要求呀。

Answer 3

这个用常规办法是不可能行得通的。我考虑到使用稀疏矩阵的相关算法，也就是创建一个64K*64K的矩阵，矩阵内元素的值只有两种，要么是0要么是1（Cell[Row][Col]=1, Row=N/(64K),Col=N%(64K),其中N为给定的数据中的任意一个），由于只有1000万（10M）个数据，而矩阵的容量为4KM，也就是只有0.25%的元素非零，很明显这是一个典型的稀疏矩阵。伪代码为//初始化，把给定的数组(ValueArray)中的数据填到稀疏矩阵中
void Init()
{
   for(UINT i=0;i<COUNT;i++)
   {
       UINT Row = ValueArray[i]/(64K);
       UINT Col = ValueArray[i]%(64K);       SetCellValue(Row, Col, 1);
   }
}//查找，把欲查找的值转化成坐标，取得矩阵中的值
bool Find(DWORD dwValue)
{
    UINT Row=dwValue/(64K);
    UINT Col=dwValue%(64K);
    
    return GetCellValue(Row, Col)==1;
}关于稀疏矩阵的知识，请参考相关资料。

Answer 4

单个数据查找最坏比较次数不能超过12次 ??
不要做梦了。
《计算机程序设计艺术》
第3卷《排序与查找》
第5章《排序》
5.2节《内部排序》引理M:
任何以比较元素对偶为基础的在n个元素中寻找极大者的算法，必须至少做n-1次比较。即使是已经排好序的数，最快的折半查找，1000万的数据，也要比较24次。

Answer 5

#include <afxtempl.h>#define  AL_HASH_TABLE_SIZE       11
#define  CT_HASH_TABLE_SIZE       1000000typedef CMap<int, int, int, int> Int2IntMAP;
Int2IntMAP          m_map;map.RemoveAll();
map.InitHashTable();
....
m_mapCT.Lookup(index, sVal);