本博客日IP超过2000，PV 3000 左右，急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包，请加博主新的微信号：xttblog2，之前的微信号好友位已满，备注：返现
受密码保护的文章请关注“业余草”公众号，回复关键字“0”获得密码
所有面试题(java、前端、数据库、springboot等)一网打尽，请关注文末小程序
腾讯云】1核2G5M轻量应用服务器50元首年，高性价比，助您轻松上云
又到了一年一度的面试季，最近有网友给出一道高级java工程师的面试题。100亿个数字的大文件如何快速找出最小的值？我这里给出一些思路，提供参考！
这道题我们首先想到的是使用外部排序的方式，由于内存的原因，内部排序肯定不被允许，或者不是最佳选择！
外部排序
内存极少的情况下，利用分治策略，利用外存保存中间结果，再用多路归并来排序。
map-reduce的嫡系
分割大文件
内存中维护一个极小的核心缓冲区memBuffer，将大文件bigdata按行读入，搜集到memBuffer满或者大文件读完时，对memBuffer中的数据调用内排进行排序，排序后将有序结果写入磁盘文件bigdata.xxx.part.sorted.
循环利用memBuffer直到大文件处理完毕，得到n个有序的磁盘文件：
合并多个排序结果
现在有了n个有序的小文件，怎么合并成1个有序的大文件？
把所有小文件读入内存，然后内排？
利用如下原理进行归并排序：
我们举个简单的例子：
文件1：3,6,9
文件2：2,4,8
文件3：1,5,7第一回合：
文件1的最小值：3 , 排在文件1的第1行
文件2的最小值：2，排在文件2的第1行
文件3的最小值：1，排在文件3的第1行
那么，这3个文件中的最小值是：min(1,2,3) = 1
也就是说，最终大文件的当前最小值，是文件1、2、3的当前最小值的最小值，绕么？
上面拿出了最小值1，写入大文件.
第二回合：
文件1的最小值：3 , 排在文件1的第1行
文件2的最小值：2，排在文件2的第1行
文件3的最小值：5，排在文件3的第2行
那么，这3个文件中的最小值是：min(5,2,3) = 2
将2写入大文件.
也就是说，最小值属于哪个文件，那么就从哪个文件当中取下一行数据.（因为小文件内部有序，下一行数据代表了它当前的最小值）
最终的排序结果
less bigdata.sorted.text ... 9999966 9999967 9999968 9999969 9999970 9999971 9999972 9999973 9999974 9999975 9999976 9999977 9999978 ...
最后，欢迎关注我的个人微信公众号：业余草（yyucao）！可加作者微信号：xttblog2。备注：“1”，添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注！后续有精彩内容会第一时间发给您！原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系！
本文原文出处：业余草： » 100亿个数字的大文件如何快速找出最小的值？