如何使用1M的内存排序100万个8位数
这篇讲的是如何在仅有1MB内存的约束下，对100万个8位整数进行排序的经典算法难题。问题最初源于Stack Overflow，看似无解——毕竟100万个数直接存储就需要超过1MB的空间。文章介绍了一种巧妙的解法核心：不直接存储排序后的每个数字本身，而是利用它们已排序这一特性，转而记录相邻数字之间的差值。由于这些差值平均很小，理论上可以用大约7位（bit）来表示一个差值，总计约0.875MB，从而在1MB内存内完成编码存储。实现上采用了高效的归并排序，并利用算数编码或哈夫曼编码对差值进行压缩编码。作者还分享了完整的339行实战代码，并提到了其他程序员的不同解题思路，展现了算法在极端约束下化不可能为可能的魅力。