题目
内存只有1G，有一个10G的文件，里面保存的是UUID（固定48位），需要对UUID排序
快速排序的空间复杂度
被快速排序所使用的空间，依照使用的版本而定。使用原地（in-place）分割的快速排序版本，在任何递归调用前，仅会使用固定的額外空間。然而，如果需要产生log n嵌套递归调用，它需要在他们每一个存储一个固定数量的信息。因为最好的情况最多需要log n次的嵌套递归调用，所以它需要log n的空间。最坏情况下需要O(n次嵌套递归调用，因此需要O(n)的空间。
拆分
- 如果不考虑快速排序的空间复杂度，每个拆成1G，如果考虑，每个拆成500M，这里没有严格的定量计算
- 是边拆边排序，还是拆完在排序，建议通过缓冲区边拆边排序
- 这两点其实都不是本题的重点，下面的合并才是重点
合并
- 很早之前我们都做个两个有序链表，合并为一个新的有序链表，但是这道题还需要我们合并设置文件的偏移量和缓冲区
- 1G的空间在不考虑临时空间的条件下，我们分成三个部署，两个250M的待合并文件的缓冲区，一个500M的合并完文件的缓冲区
- 这两个250M缓冲区的数据合并就和链表的合并是一个意思了，设置两个指针遍历就行
- 现在从20个500M的文件变成1G的文件和18个500M的文件，按照之前的步骤再次合并就行
- 是不是需要每次需要从最小的开始，完全没有必要
网友评论