(我原来的答案是错误的，对不起，数学不好，见下面的休息。)

这个怎么样?

前27位存储您所看到的最小数字，然后是与下一个数字的差值，编码如下:5位存储用于存储差值的位数，然后是差值。使用00000表示您再次看到了该数字。

这是因为插入的数字越多，数字之间的平均差值就越小，所以当你添加更多的数字时，你用更少的比特来存储差值。我想这叫做增量表。

我能想到的最糟糕的情况是所有数字都等距(以100为间隔)，例如假设0是第一个数字:

000000000000000000000000000 00111 1100100
                            ^^^^^^^^^^^^^
                            a million times

27 + 1,000,000 * (5+7) bits = ~ 427k

Reddit来拯救你!

如果你要做的只是把它们排序，这个问题就简单了。它需要122k(100万比特)来存储你看到的数字(如果看到0，则第0位，如果看到2300，则第2300位，等等。

读取数字，将它们存储在位域中，然后在保持计数的同时将位移出。

但是，你必须记住你看过多少。我受到上面的子列表答案的启发，想出了这个方案:

用2位或27位代替1位:

00表示你没有看到这个数字。 01表示你看过一次 1表示你看过，接下来的26位是看了多少次。

我认为这是可行的:如果没有重复，你就有一个244k的列表。 在最坏的情况下，你看到每个数字两次(如果你看到一个数字三次，它会缩短列表的其余部分)，这意味着你不止一次看到了50,000个，你0次或1次看到了950,000个项目。

50,000 * 27 + 950,000 * 2 = 396.7k.

如果你使用以下编码，你可以做进一步的改进:

0表示你没有看到这个数字 10表示你看过一次 11是你计数的方式

这将导致平均280.7k的存储空间。

编辑:我周日早上的数学算错了。

最坏的情况是，我们两次看到50万个数字，所以数学就变成了:

500,000 *27 + 500,000 *2 = 1.77M

交替编码导致平均存储为

500,000 * 27 + 500,000 = 1.70M

: (

我有一台有1M内存的电脑，没有其他本地存储

另一种作弊方法:你可以使用非本地(网络)存储代替(你的问题不排除这一点)，调用一个网络服务，它可以使用直接的基于磁盘的归并排序(或者只需要足够的RAM来在内存中排序，因为你只需要接受1M的数字)，而不需要(公认非常巧妙的)已经给出的解决方案。

这可能是作弊，但不清楚你是在寻找一个现实问题的解决方案，还是一个让人扭曲规则的谜题……如果是后者，那么简单的欺骗可能比复杂但“真实”的解决方案(正如其他人指出的那样，后者只能用于可压缩输入)得到更好的结果。

您只需要按顺序存储数字之间的差异，并使用编码来压缩这些序列号。我们有2^23位。我们将它分成6位块，让最后一位表示这个数字是否扩展到另外6位(5位加上扩展块)。

因此，000010是1,000100是2。000001100000表示128。现在，我们考虑用最坏的类型来表示不超过10,000,000的数字序列的差异。可能有10000000 /2^5的差异大于2^5,10000000 /2^10的差异大于2^10,10000000 /2^15的差异大于2^15，等等。

所以，我们把表示这个序列所需要的比特数相加。我们有1,000,000*6 +汇总(10,000,000/2^5)*6+汇总(10,000,000/2^10)*6+汇总(10,000,000/2^15)*6+汇总(10,000,000/2^20)*4=7935479。

2^24 = 8388608。由于8388608 > 7935479，我们应该很容易有足够的内存。我们可能还需要一点内存来存储插入新数字时的和。然后我们遍历这个序列，找到插入新数字的位置，如果必要的话减少下一个差值，并将它之后的所有内容都右移。

如果输入流可以接收几次，这就容易多了(没有关于这方面的信息，想法和时间性能问题)。然后，我们可以数小数。有了计数值，就很容易生成输出流。通过计算值来压缩。 这取决于输入流中的内容。

Gilmanov的答案在假设上是非常错误的。它开始基于毫无意义的一百万个连续整数进行推测。这意味着没有差距。这些随机的间隙，不管有多小，真的是一个糟糕的主意。

你自己试试。获得100万个27位随机整数，对它们排序，用7-Zip, xz压缩，任何你想要的LZMA。结果超过1.5 MB。上面的前提是连续数字的压缩。即使是增量编码也超过1.1 MB。没关系，这使用了超过100 MB的RAM进行压缩。因此，即使压缩的整数也不适合这个问题，更不用说运行时RAM的使用了。

让我难过的是，人们竟然投票支持漂亮的图像和合理化。

#include <stdint.h>
#include <stdlib.h>
#include <time.h>

int32_t ints[1000000]; // Random 27-bit integers

int cmpi32(const void *a, const void *b) {
    return ( *(int32_t *)a - *(int32_t *)b );
}

int main() {
    int32_t *pi = ints; // Pointer to input ints (REPLACE W/ read from net)

    // Fill pseudo-random integers of 27 bits
    srand(time(NULL));
    for (int i = 0; i < 1000000; i++)
        ints[i] = rand() & ((1<<27) - 1); // Random 32 bits masked to 27 bits

    qsort(ints, 1000000, sizeof (ints[0]), cmpi32); // Sort 1000000 int32s

    // Now delta encode, optional, store differences to previous int
    for (int i = 1, prev = ints[0]; i < 1000000; i++) {
        ints[i] -= prev;
        prev    += ints[i];
    }

    FILE *f = fopen("ints.bin", "w");
    fwrite(ints, 4, 1000000, f);
    fclose(f);
    exit(0);

}

现在用LZMA压缩ints.bin…

    $ xz -f --keep ints.bin       # 100 MB RAM
    $ 7z a ints.bin.7z ints.bin   # 130 MB RAM
    $ ls -lh ints.bin*
        3.8M ints.bin
        1.1M ints.bin.7z
        1.2M ints.bin.xz

下面是一些可以解决这个问题的c++代码。

满足内存约束的证明:

编辑:无论是在这篇文章中还是在他的博客中，都没有作者提供的最大内存要求的证据。由于编码值所需的比特数取决于先前编码的值，因此这样的证明可能不是简单的。作者指出，根据经验，他可能遇到的最大编码大小是1011732，并任意选择了1013000的缓冲区大小。

typedef unsigned int u32;

namespace WorkArea
{
    static const u32 circularSize = 253250;
    u32 circular[circularSize] = { 0 };         // consumes 1013000 bytes

    static const u32 stageSize = 8000;
    u32 stage[stageSize];                       // consumes 32000 bytes

    ...

这两个数组总共占用1045000字节的存储空间。剩下1048576 - 1045000 - 2×1024 = 1528字节作为剩余变量和堆栈空间。

它在我的至强W3520上运行大约23秒。您可以使用以下Python脚本验证程序是否工作，假设程序名称为sort1mb.exe。

from subprocess import *
import random

sequence = [random.randint(0, 99999999) for i in xrange(1000000)]

sorter = Popen('sort1mb.exe', stdin=PIPE, stdout=PIPE)
for value in sequence:
    sorter.stdin.write('%08d\n' % value)
sorter.stdin.close()

result = [int(line) for line in sorter.stdout]
print('OK!' if result == sorted(sequence) else 'Error!')

该算法的详细解释可以在以下一系列帖子中找到:

1MB排序说明 算术编码与1MB排序问题 使用定点数学的算术编码