排序

归并排序 属于分治策略，先分割成小数组，再合并有序数组，类似于二叉树的后续遍历 稳定排序 最好、最坏、平均时间复杂度都相同 o(nlogn) Arrays.sort()，优化的归并排序

1，找出两个大文件相同的URL？ 大文件不能讲全部数据加载到内存中操作，采用分治的思想解决 第一步，对大文件a，对a的每个URL取 hash(url)/1000，这样大文件中的数据就被分到了1000个小文件中，而且小文件中的url hash值是 相同的（hash后可能会存在文件不均衡的情况，此时需要继续换一种hash算法再次分割） 第二步，对大文件b，进行同样的操作，也得到了1000个小文件 第三步，逐个对比ab中的小文件，hash值相同不一定值相同，所以需要对比两个小文件中的值，具体可以将每个url放到set中，判断是否重复 第四步，归并1000个小文件的结果

如果允许有一定的错误率，可以使用Bloom filter，4G内存大概可以表示340亿bit。 将其中一个文件中的url使用Bloom filter映射为这340亿bit，然后挨个读取另外一个文件的url，检查是否与Bloom filter。 如果是，那么该url应该是共同的url（注意会有一定的错误率）。

2，找出一个大文件中出现频率最高的top 100 url？ 第一步，对大文件中的每个url取 hash(url)/1024，这样就分成了1024个小文件，而且每个小文件的所有url的hash值相同 第二步，遍历每个小文件，按每个url的出现次数取top100，把url及其出现次数存入文件 第三步，归并排序这些小文件