从[0..k]中获取整数值的n大小数组的就地排序和O(n)时间

Question

有没有一种算法可以对n大小的数组按位置和O(n)时间进行排序，该数组从0..k的范围内取整数的值

Answer 1

是的，有！考虑使用most-significant digit radix sort，有时称为二进制快速排序。这个算法就地工作，尽管它需要O(log )个递归堆栈的辅助空间(我不知道这对你来说是不是一个破坏交易的因素)。对最大值为U的n个数字列表进行排序的运行时是O( whose )，在您的例子中，因为k是一个固定常数，所以运行时是O(n)。