是否有可能以线性时间排序整数数组？

Question

有一天，我正在阅读有关谷歌和微软实习的访谈博客，我读到其中一个问题是如何在线性时间内排列整数。

我认为排序东西的最佳方式是O（n日志（n））像Mergesort或Quicksort，但知道我不确定。有什么想法吗？

Answer 1

那么，这个问题一定会有更多的限制。例如，如果数组仅包含几个重复数字[1 3 2 6 3 1 2]，则可以使用counting sort在线性时间内完成此操作，但会占用更多空间。

另一种算法是Dutch National Flag算法，它可以在线性时间内对3个重复数进行排序。除此之外，我不认为（无知在这里不是幸福：P）我知道在线性时间对正常数组进行排序的方法。

即使你使用Radix sort它会占用O(m * n)但如果m <<< n你可以争辩说，它大约O(n)

Answer 2

O(n lg n)是你能为基于比较-排序，不要求你做的最好知道你正在排序的项目的任何内容，而不是你如何比较一个到另一个。对有界大小的整数列表进行排序（即每个整数至多为K，其中K独立于n）是一个更加专门的问题，因此您可以使用运行速度比O(n lg n)（例如基数排序）更快的更专用的算法， 。