我得到了一个集合{0,1，…，n}中的整数数组，其中我需要在时间O(n(中对数组进行排序。但我不确定是否要对这个问题进行基数/计数排序。有人能对此提出建议吗？
如果需要在O(n)时间内排序，则计数排序是唯一的选项。它具有Θ(n)的时间复杂度和Θ(n)的空间复杂度。
在最坏的情况下，基数排序需要O(n log(n))时间(因为在您的情况下键的长度是log(n)(，而快速排序在平均情况下是O(n log(n))，在最坏情况下可以是O(n²)，具体取决于实现。
如果n足够小，n个元素的数组可以容纳在内存中，那么计数排序将是最快的。
对于较大的n，需要基数排序。如果密钥存储在32位或64位整数中，则以256为基数的排序将对32位进行4次遍历，对64位进行8次遍历。由于时间复杂度忽略了常数，因此从技术上讲，这样的基数排序具有时间复杂度O(n(。然而，如果基数排序使用最大键值来减少通过次数，则时间复杂度将为O(n-log(n(((实际复杂度将是n-ceil(log256(n(。(。