仅用 10 万个存储单元对 100 万个数字进行排序
Sorting 1 million numbers with only 100k memory cells
在 C++ 中，假设我们知道数字的范围，仅使用 100,000 个存储单元，是否可以对 100 万个数字进行排序？
具体来说，一个.bin文件包含给定范围内的一百万个数字，需要将这些数字按降序排列到另一个.bin文件中，但我只允许使用大小为100,000的数组进行排序。有什么想法吗？
假设数字范围有 100,000 个值或更少，您可以使用 Counting Sort.
我们的想法是使用记忆单元作为范围内数字的计数。例如，如果范围是 0..99999（含），则创建一个数组 int count[100000]，并通过文件递增计数 运行：
count[itemFromFile]++;
遍历整个文件后，再次遍历范围。对于每个不为零的count[x]输出x对应的次数。结果将是按升序排序的原始数组。
您可以实现一种适用于文件而非向量的快速排序算法版本。
因此，递归地拆分低于 pivot/higer-than 主元的文件，对这些文件进行排序，然后重新组合它们。当大小低于可用内存时，只需开始在内存中工作而不是在文件中工作。
我想我在 SO 或 Quora 的某处读到了关于 map-reduce 的内容：
除以 100 万。数字分成 10 个块。读入第一个 100k 数字块，使用快速排序对其进行排序，然后将其写回原始文件。对其余 9 个块执行相同的步骤。然后对原始文件中的 10 个排序块执行 10 向合并（为此你只需要 10 个单元格）并将合并的输出写入另一个文件。您可以写入 ~100k 缓冲区，然后将其刷新到输出文件以加快写入速度。
在 C++ 中，假设我们知道数字的范围，仅使用 100,000 个存储单元，是否可以对 100 万个数字进行排序？
具体来说，一个.bin文件包含给定范围内的一百万个数字，需要将这些数字按降序排列到另一个.bin文件中，但我只允许使用大小为100,000的数组进行排序。有什么想法吗？
假设数字范围有 100,000 个值或更少，您可以使用 Counting Sort.
我们的想法是使用记忆单元作为范围内数字的计数。例如，如果范围是 0..99999（含），则创建一个数组 int count[100000]，并通过文件递增计数 运行：
count[itemFromFile]++;
遍历整个文件后，再次遍历范围。对于每个不为零的count[x]输出x对应的次数。结果将是按升序排序的原始数组。
您可以实现一种适用于文件而非向量的快速排序算法版本。
因此，递归地拆分低于 pivot/higer-than 主元的文件，对这些文件进行排序，然后重新组合它们。当大小低于可用内存时，只需开始在内存中工作而不是在文件中工作。
我想我在 SO 或 Quora 的某处读到了关于 map-reduce 的内容：
除以 100 万。数字分成 10 个块。读入第一个 100k 数字块，使用快速排序对其进行排序，然后将其写回原始文件。对其余 9 个块执行相同的步骤。然后对原始文件中的 10 个排序块执行 10 向合并（为此你只需要 10 个单元格）并将合并的输出写入另一个文件。您可以写入 ~100k 缓冲区，然后将其刷新到输出文件以加快写入速度。