博客

问题

之前有朋友问了一个问题，说



10

10






1


0





万个手机号怎么排序。我说



10

10






1


0





万个太少了，读到数组中，直接排就行了。

今天突然想到一个问题，如果是1亿个手机号怎么排序呢？

分析

先来理清一下需求：

有1亿个不重复的手机号，按行存放在一个大文件

mobiles_in.txt

中，要求将手机号由小到大排好序的结果输出到另一个文件

mobiles_sorted.txt

中。

1个手机号11位数字，再加上换行符(\r\n)，一行是13个byte，1亿个手机号的文件大小是13亿byte，大概是1.2G。其实也不算多大个文件。

处理“大”问题的基本思路：分治。

本问题中，可以借鉴

归并排序

的思路，将大文件拆成100个小文件，小文件内部排好序，然后进行100路的归并操作。

步骤

1. 将
   
   
   
   1.2

   G

   1.2G
   
   
   
   
   
   
   1
   
   
   .
   
   
   2
   
   
   G
   
   
   
   
   
   的大文件，经过一遍按行读写的方式（迭代器模式）进行处理，拆成
   
   
   
   100

   100
   
   
   
   
   
   
   1
   
   
   0
   
   
   0
   
   
   
   
   
   个小文件，每个小文件中存放
   
   
   
   100

   100
   
   
   
   
   
   
   1
   
   
   0
   
   
   0
   
   
   
   
   
   万个手机号。

2. 分别将
   
   
   
   100

   100
   
   
   
   
   
   
   1
   
   
   0
   
   
   0
   
   
   
   
   
   个小文件读进内存，将手机号从小到大排序，排序结果写回对应的小文件中。

3. 通过一个小顶堆形式的优先级队列（
   
PriorityQueue

   ）进行归并操作。堆中的元素是一个二元组：
   
(手机号, 该手机号对应的小文件编号)

   。
   • 一开始，将每个文件的第一个手机号读出来放到小顶堆中。由于这
     
     
     
     100

     100
     
     
     
     
     
     
     1
     
     
     0
     
     
     0
     
     
     
     
     
     个手机号分别是各个子文件中最小的，因此，此时小顶堆堆顶的手机号就是全局最小的手机号。因此可以将堆顶元素弹出，写到最终的输出文件
     
mobiles_sorted.txt

     中。

   • 每次从堆顶弹出一个元素后，如果该元素所对应的小文件还没被处理完，就从相应小文件中读入下一个手机号，补充到堆中。
   • 所有手机号都各自加入和弹出小顶堆一次后，排序完成，此时的
     
mobiles_sorted.txt

     文件就是最终结果。