algorithm - 对一个小整数数组进行排序

Question

知道所有整数只能放在一个位并且我有无限的内存可以使用，我如何在小于 O(nlogn) 的时间内对一个小整数数组进行排序？

标签： algorithmsorting

Answer 1

如果输入限制为假设您的规范（1 字节）并且您有无限的内存，则可以利用此优势进行排序而不是基于比较。一种这样的算法是具有 O(n) 复杂度的键索引计数。有关其工作原理的详细指南，请参阅此说明。