这是一个创建于 367 天前的主题，其中的信息可能已经有所发展或是发生改变。
如给定无序数组 arr ，长度为 100w ，但是机器可用内存只有 5w 数组长度，如何排序并写入文件 我的思路是类似归并排序 1.每次取数组 2.5w 长度排序，写入文件 file1 2.循环步骤 1 ，此时会有排序好的文件为 file1 至 fileN 3.合并 file$i 和 file$(i+1)，此时会有一个 5w 长度的排序数组
问题是第 3 步后，如果处理接下来的文件？？因为内存只能容纳 5w 长度的数组，怎么将 10w 长度数组合并呢
 |
1
julyclyde 2024-01-17 19:37:52 +08:00
用交换类排序呗，对内存（几乎）没需求
|
 |
2
liuhan907 2024-01-17 19:47:56 +08:00
这不就是外部排序+多路归并排序么
|
 |
3
Tanix2 2024-01-17 19:59:29 +08:00
如果每次取 2.5w 长度形成一个有序的 chunk 的话，共有 100w/2.5w=40 个 chunk ，之后使用 40 路归并排序，40 个 chunk 里每个先取比如说 0.5k 个元素（减少 I/O ，最好能达到一个 page 的大小，但是这里应该达不到），每次选出其中最大的一个元素放到缓冲区（大小为一个 page ）。如果某个 chunk 在内存里没有元素了，那么从磁盘里再取 0.5k 个；如果输出缓冲区满了，写到磁盘里。
以上是二阶段多路归并排序，如果第一阶段形成的 chunk 数过多（比如大于 2.5w 了），可以考虑更多阶段。 |
 |
4
changnet 2024-01-17 20:01:07 +08:00  1
交换类排序冒泡排序这种，只需要一个原始数组，在原始数组上交换排序，不需要额外的内存。但 op 这明显原始数组都加载不进来，所以是不行的。
你用文件来排序是对的，但你排序好的 file1 和 file2 合并后并不是按顺序的啊，比如 file1 中最大的那个比 file2 中的那个还大。 要先把 100w 数据读出来，按排序因子分成 20 段写入 20 个文件，比如文件 1 只写入大小为 1~50000 ，文件 2 只写入 50001~100000 ，然后分别对这些文件进行排序，再把文件拼起来就行。 当然如果无法预估排序因子的大小，拆分不会那么顺利。因为是无序的，没法预知该拆成多少个文件，那就先拆成 2 个，对大于 5W 的文件继续拆分，直到所有文件都小于 5w 再排序 |
|
5
Tanix2 2024-01-17 20:04:10 +08:00
有数据库的话，也可以考虑存到数据库里，让数据库给你排
|
 |
6
BBCCBB 2024-01-17 20:34:13 +08:00
比如每 1000 个数字加载出来, 排序, 写到一个小文件里, 然后每次合并两个有序文件. 归并排序这种思想. 比较两个文件的队头数字, 小的写到新的文件里.
最后比如留下了 20 个 5w 数字的有序文件.. 然后继续 merge.. 得到 10 个 10w 有序的. ... 以此类推. ... 得到 2 个 50w 数字的有序文件, 最后 得到了 1 个 100w 数字的有序文件. 每次只读文件的第一个数字, 需要的内存很低的. |
 |
7
iOCZS 2024-01-17 21:21:23 +08:00
既然不能整体读取到内存，为何要合并呢？
直接每 5W 存一个文件得了，虽然说追加写入也是可以，但你又不能整体读取。。。。 |
 |
8
zhuangzhuang1988 2024-01-17 21:30:46 +08:00
直接 sqlite 就可以了
|
 |
9
eote 2024-01-17 22:00:51 +08:00
|
 |
10
darling19961030 2024-01-17 22:28:03 +08:00
1. 将 100w 数据以 5w 大小分 20 组写入文件
2. 将这 20 组数据分别读到内存中排序 3. 读取 20 组数据的最小值到内存，比较出最小值写入文件，再从最小值所在组读入一个新数据 4. 再比较出最小值写入文件，再从最小值所在组读入新值 5. 直到读完 20 组数据，那写入的文件也是 100w 排序后的数据了 |
 |
11
verrickt 2024-01-17 23:42:25 +08:00 via Android
外部排序+流式处理
|
 |
12
nuk 2024-01-18 00:12:43 +08:00
随机从数组中取出 5w 个元素，排序后塞回原来的位置。当随机足够多次，排序稳定后，再检查一遍，如果没排序完，就接着循环。
|
 |
13
hefish 2024-01-18 08:55:11 +08:00
大学课本 《数据结构》 里面有详细描述。
|
 |
14
LindsayZhou 2024-01-18 09:00:37 +08:00
桶排序，每个桶做成一个文件。
|
 |
15
LGA1150 2024-01-18 13:00:48 +08:00 via Android
mmap 然后原地排序，剩下的交给操作系统
|
 |
16
liguangsheng 2024-01-18 14:31:13 +08:00
归并的时候被归并的两个文件都是有序状态的，不需要全部读到内存里再合并，两个文件指针，每次至少读一个数字就可以归并了
|
 |
17
NASK 2024-01-18 19:28:04 +08:00
外部排序+归并排序，也许是这样
|
Select Language