给定1到10,000的数字范围，输入是随机顺序 . 约束：任何时候只能将1000个数字加载到内存中 .
假设：假设唯一的数字 .
我提出了以下有效的“When-Required-sort算法” .
我们将数字写入指定为包含特定数字范围的文件中 . 例如，File1将具有0 - 999，File2将具有1000 - 1999，依此类推 .
如果正在搜索特定数字，即“2535”，那么我们知道该数字在文件3中（在范围内进行二进制搜索以查找文件） . 然后将file3加载到内存并使用说快速排序（在数组大小较小时优化添加插入排序）进行排序，然后使用二进制搜索搜索此排序数组中的数字 . 搜索完成后，我们会回写已排序的文件 .
因此，从长远来看，所有数字都将被排序 .
请对此提案发表评论 .
5 回答
它被称为Bucket sort .
主内存有限时的另一种方法是使用Merge sort .
根据需要对每个桶进行排序的设计部分可能更好地描述为“按需”，“及时”或“懒惰” . 人们已经熟悉了重用命名法，而不是发明术语“何时需要排序” .
您是否考虑过如何处理其他输入？如果某些存储桶已经排序，然后添加更多数字会发生什么？
我假设最终目标是确定数字是否包含在集合中，而不是生成排序列表 . 如果经常这样做，则对分拣桶的初始开销有好处 . 如果不经常，对适当的桶进行线性扫描就足够了 .
还有一个选择 . 存储桶排序可以被认为是一个简单的哈希表 . 哈希函数是
n/1000. 由于可以在每个桶中散列大量值（最多1000个），因此预计会发生冲突 . 您可以使用更复杂的哈希并获得O（1）搜索性能，而不是使用按需排序（然后使用二进制搜索）来解决冲突 .每个数字可以是1到10000.这意味着每个数字至少占用14位（213 = 8192,214 = 16384） .
您可以将1000个数字加载到内存中 . 这意味着您可以使用位掩码，因为您已声明数字是唯一的 . 设置10000位的位掩码，每个位数为14位，只有715个数字（如果每个数字的位数超过14位，则最多为少） .
最初清除位以指示不存在数字，然后一次读取一个数字，设置相关位以指示它存在 . 这是O（n）操作 .
然后，一旦设置了该位数组，就可以进行O（1）操作来查看是否设置了某个位 .
即使是最好的排序算法也不会比随机数据上的O（n）更好 .
上一张海报的描述是正确的 - 这是一个桶排序 .
一些密切相关的种类是Radix种类 . 这些是O（1），但取决于范围内相当均匀的值分布 .
使用mergesort：
http://en.wikipedia.org/wiki/Sorting_algorithm
mergesort的内存消耗为n，而bucketsort为n * k .
对于bucketsort最坏的情况是n ^ 2 * k，而mergesort是n * ln（n）
请注意：在几乎任何必须对大量数字进行排序的情况下，mergesort是该任务最有效的排序算法 .
我给你读了这样的问题“如果从域D输入n个数字，那么写下这些n个数字的排序输入的最快方法是什么，前提是你只能在内存中存储k个数字（k <n）？提供算法n = 10000，k = 1000 . “
请注意，在您的问题中，您说域D的范围是1到10000.我认为这是过于简单化 . 当n = 10000且输入为范围（无重复）时，这将成为 trivial ，因为您将准确知道每个数字应在排序文件中写入的位置 . 此外，您确切知道该文件的内容是什么，并且您不必阅读输入 . ：d
现在如果N（D）不等于n或者你允许重复那么问题会变得有趣 .
如果内存有限，我认为直观的方法是这样做：
1st approach
读取输入后，您可以在写入之前对大多数k1元素进行排序，其中k1是需要对内存中的k个元素进行排序的元素数 .
最终会得到内部排序的f =（n div k1）1个文件 .
然后，您需要从f文件中读取并合并部分排序的数据，将它们写入最终文件 .
不同的排序具有不同的内存要求，并将生成不同数量的必须合并的部分排序的文件 .
合并更多文件将需要更多内存，因为您不知道在哪个文件中可以找到下一个数字 .
2nd approach
如您所知，另一种方法是知道您可以在哪个文件中找到下一个数字 . 这就像放它们在桶中根据它们的大小（通过分类来分配排序），但问题在于，除非您知道如何分发数据，否则很难确定每个桶的范围 .
对于最少数量的文件，每个桶的大小应该是k1 .
假设您对数据分布有所了解，可以这样做，否则您需要对数据进行另一次传递以 Build 切割点 .
对于不知道存储桶大小的一般数据，您不能先将所有数据传递给您（例如，如果您输入的数据必须为数据保留某种排序结构，那么您就不会我知道接下来会发生什么）你基本上必须保留一个索引，比如B树，但这不是最佳的 . 索引针对快速检索进行了优化，并且（其中一些）用于插入少量新元素 .
3rd approach
拥有这么小的域允许简单地计算数字并将其频率写下来 . 如果你可以随机访问输出文件，文件系统缓冲可以处理效率（缓冲是一种算法，可以有效地限制内存使用的磁盘写入，唯一的问题是如果缓冲区的大小小于k数如果选择的位图像结构是最有效的） .
直觉上我会说最好的选择是首先计算分布并计算每个桶的大小和限制 . 然后将文件分成多个桶 . 然后对每个桶进行排序我想通过至少部分地对数据进行排序，同时将数据写入存储桶，可以挤出一些性能 .