（开放题）100亿排序问题：内存不足，一次只允许你装载和操作1亿条数据，如何对100亿条数据进行排序

[hichannel]

难度：阿里p6+ ~ p7、腾讯t23 ~ t31

更多课程见 海畅智慧官方

这题是考察算法和实际问题结合的一个问题

众所周知，腾讯玩的是社交，用户量极大。很多场景的数据量都是百亿甚至千亿级别。

那么如何对这些数据进行高效的操作呢，可以通过这题考察出来。

以前老听说很多人问，前端学算法没有用，考算法都是垃圾，面不出候选人的能力

其实。。。老哥实话告诉你，当你在做前端需要用到crc32 、并查集、字典树、哈夫曼编码、LZ77之类东西的时候

已经是涉及到框架实现和极致优化层面了

那时你就已经到了另外一个前端高阶境界了

所以不要抵触算法，可能只是我们目前的眼界和能力，还没触及到那个层级

[hichannel]

抛个砖:

• 0. 把这100亿的int型数据以文件形式存储到100个小文件中
• 1 对这100个小文件分别读取后排序再存入
• 2遍历排序后对100个小文件，每个小文件里面取第一个数字, 组成一个100大数的堆
  • 2.1. new个空的大文件存最后的结果
• 3之后出100个数的那个堆,找到对应的小文件取数字,写入大文件, 记得flash, gc之类的
• 4循环3, 等所有的小文件都取完, 大文件就是存的最后结果

[lilili-book]

• 在前端对100亿个数字排序大多数情况下是没有意义的事情，真的遇到这种需求，应该先判断是不是对需求的理解出现问题了。例如，只是想取其中最大的1000个数字，那就不应该对100亿个数字排序，而应该使用Top K问题的解决方案，如分治、局部淘汰、Hash等。

• 不应该使用JavaScript解决这个问题，ECMA-262规定ECMAScript的数字实现为浮点数（as specified in the IEEE Standard for Binary Floating-Point Arithmetic），应该使用WASM、Native Module乃至RPC通讯。

• 之后就是正统的外排序算法上场了，要是内存足够的话直接快排也行