去哪儿网面试题:对100亿行数据排序

一个文本文件里面有100亿行无序的数据,将这些数据从小到大排列并输出前100个数据。

http://www.manong1024.com/q/205

如果用bitmap排序,那有重复数据怎么办

你只取小端的 100 个数据,所以只需开辟 100个元素的链表就可以了
遍历这100亿数据,有序的插入结果链表(溢出时丢弃)

位图隐射,然后遍历。
回或者小根堆

这是典型的bitmap排序。也就是创建一个4294967296元素的数组,然后遍历这100亿数据,如果某个数据等于12,就让数组下标为12的那个元素+1,以此类推。
最后从数组0开始输出,如果这个元素对应的值是1,就输出1次,如果是2就输出2次,直到100为止。