我的分析：
要对这1000000个随机数进行统计，最好先对其进行排序，排序算法我选择了快速排序，时间复杂度O(nlgn)。但是由于快速排序是内存排序法，所以要先把这1000000个16字节的数据读到内存里才能进行。1000000的数据量说大也不是很大，但说小也不小，还是会消耗很大的一块内存的，而且这是一块连续的内存。但是如果用外存排序算法的话时间复杂度又很高。

大家有没有什么好的想法或建议的一起来交流下。

P.S.这个题目有点类似于baidu招聘时候的一个面试题（大体意思如下，具体题目记不清了）：
有4G的一个日志文件，该文件中保存着人们检索的关键字记录。该文件中一行保存着一个关键字，每行最多256个字符。现在要将这个日志文件中的关键字进行一个统计，统计出检索次数最多的前100个关键字，并按检索次数将这100个关键字列出。

恩，是的。

谢谢Logician兄。

另外就是我一个同学他想到了一种方法：
先对这1000000个随机数分类，分类的方法是以随机数的第一个字节来分，若第一字节相同的就归为一类，这样分下来的结果最多可能存在256类（一个字节能表示的数最大是256）。然后在分出来的这256个子集中分别进行统计，统计方法是第 i 条记录与它后面的 n － i 条记录比较。而对于这256个子集的比较每个子集开一个线程运行。

我觉得他这个方法从算法角度分析应该还没有这种情况好——每条记录与它后面的所有记录比较，但是他说他测试的结果却是他的方法的执行速度比刚才说的那种情况的速度快很多。

Logician兄能谈谈你的看法吗？

关于实现时的速度，我觉得影响它的原因有很多。

比如：最初分类（把它划成256个子集）时，如果是要节省内存，就要在一定情况下把分好类的随机数写回硬盘。这个工作如果由操作系统来控制的话，操作系统应该会按页面进行调度。这种情况下，操作系统的具体调度策略、划分存储区时设置的存储区大小（那256个存储区的大小是静态分配还是动态增长呢？初始时设为多大呢？）、系统目前空闲的物理内存空间大小似乎对性能都会有比较大的影响。

你说的“每条记录与它后面的所有记录比较”是说：对第i条记录，把它与第i+1条直至第1000000条记录依次比较，如果有相同的，就删除那个相同的，并把该条记录的“重复度”加1。是这样吗？

如果是的话，我觉得这样似乎比较低效。因为它的渐进复杂度是O(n^2)的。

如果你同学的意思是说把它划成256块，并且只在块内逐一比较，其渐进复杂度也是O(n^2)的，只不过他的n大约是你的n的1/256。也就说是，假如你的方法需要做比较k*n^2次比较的话，他的方法大约只需要做k* 256 * (n/256)^2 = k*(n^2)/256 次。

但这种方法的话，我觉得还不如分成256组之后，逐一进行内排序，然后再数。我觉得这样应该比你同学现在的方法还要快些。

另外，你同学的方法，当待统计的随机数数量再增加几个数量级时，似乎就不适用的……
到时，为了减小每个块的尺寸（以免第二步比较时因内存不够而反复从内存中调入调出数据）就得增加块数（比如，根据前2个或3个字节分块），但这样一来，内存中的块数太多，可能导致每个块中才写了几个数就不得不写回（因为总的容量已经满了），而我们知道，往硬盘中写入一个page（往往是几KB的大小）和写入一个字节所需的时间是差不多的，一次往硬盘中写入几个字节是不划算的……

“统计方法是第 i 条记录与它后面的 n － i 条记录比较”和“每条记录与它后面的所有记录比较”指的是第一条跟他后面的N-1条比较，第二条跟他后面的N-2条比较，第三条跟他后面的N-3条比较……以此类推，一直到最后一条。这样的时间复杂度为O(n方)，而且空间也是相当耗费，所以不可取。

我同学那种开多个线程的方法在单CPU的机子上实际性能我觉得也跟上述的那种差不多甚至会更差。因为多线程在指令级上仍然是顺序执行的，而且他的那种方法还涉及到线程的切换等，也要消耗CPU时间。但是他说他的时间比上述方法快得多我就有点不大明白了。。。。

我觉得如果一个一个开的话，效果应该会好一些。（不太清楚Windows在线程调度方面的策略，不知道对于256个线程同时开、内存空间又有限的情况下，Windows是不是有什么好的调度方法保证一定的效率）

但正如我刚才分析过的，他的方法需要的总比较次数你的少很多。所以，只要Windows能有效地避免因多线程争用内存空间而造成的“颠簸”（我觉得是可能的，因为你的数据总共才16MB而已，腾出10来兆的物理内存空间并不是难事，至于线程切换的开销，一般也就是总CPU时间的百分之几甚至千分之几，实在算不上什么的），速度快一些是自然的（我们前面算过了，他的方法需要做的比较数是你的方法的1/256，这种几百倍的差距，绝对不是那一点线程调度开销能弥补的）。

简单地说，我觉得如果要测试这种External算法（外排序、外查找等）的话，得要数据量足够大（最好是拿不同规模的数据多次测试），而且注意监控（最好是能手动控制）内存使用量，测出来的数据才有意义。你这里用固定的16MB数据进行测试，很难说它代表了External算法的优劣……

明白了。3q!^_^