今晚上电面腾讯的一道算法题,求解

如果是 utf-8 字符串表示的浮点数，那么如果全装进内存有没有可能加起来小于 1t，已知市面上比较好买的内存最大是单条 128g，这样一台 epyc 或者白金至强服务器带起 1t 内存就可以进行内存排序

腾讯么，不差钱

个人提供一种思路，假设可用内存为 1G，那先对依次对每个 1G 文件内的浮点数进行快排，这样得到 1000 个已经排序的大小为 1G 的文件。然后依次扫描每个已经排序的文件，每个文件取出 1M 的内容，这样合起来大概是 1G，再对这些内容进行归并排序，结果写入硬盘，这样依次进行，其实是一种外排序的思路。

先对每个文件排序，再读取每个文件的第一行，对这 1000 个数字进行排序，把最小的那个数字进行 pop，再继续读取 pop 出来的数字的那个文件下一行放到那 1000 个数字里，继续 pop，如此循环，每次 pop 出来的数字写到输出文件里。

这个问题的结果会生成一个 1T 的 .txt 文件？

大概想一下，应该要先估算数量。
float 32 位，最多 4294967296(2^32)个数字，建立一个 unint32 的数组（计数上限不能低于 2^32 ），这样内存占用 4294967296 * 4byte = 16G，这样就不用写出写入了。
比较 float 时，直接进行位比较，想等的话对应位数字++，最后完成排序后可以，按对应数字输出一边 就好了？ 细节实现可能有问题，IEEE 具体都忘了

@across
这样问题可以转化成，将所有 float 数字按顺序一边吧。

看题目就是外归并了，反正万能算法：不论大文件去重还是排序，答案都是外归并

外排序，一般标答都是纯归并，文件数不多的情况下也可以也可以基于堆做外排序的归并，1000 还是没问题的，嗯大概就是 3 楼那个意思，不过用堆比有序数组更正统，3 楼相当于插入排序了，复杂度还是有区别的。

@jinhao7773 你这方法复杂度爆表了，因为“对这 1000 个数字进行排序”重复了 n/1000 次。整体复杂度是 n^2 。

贱指 offer 貌似有这题

@xupefei 但整体不还是 nlogn 么……

@fline 就算 1000 个文件是排过序的，把他们 merge 起来已经是 nlogn 了。

@xupefei 仔细想了想，3L 如果是用最小堆进行 merge 的时候，最后的复杂度是 2*nlogn，的确是 nlogn 复杂度。

@xupefei 但是每次 pop add 一个是插入排序 logn 整体依旧是 nlogn

这不是经典的 merge sort 吗

昨天才看的排序，咋今天就有题了。典型的外排序，归并算法

@xupefei 1000 个数字只需要刚读出来的排一次就行，后面 pop 之后依然是有序的。

经典的外部排序问题。

把所有行写入数据库(sqlite ），排序导出，根据实际情况分批处理