前几天，我在读关于谷歌和微软实习面试的博客，我读到其中一个问题是如何在线性时间内排列整数数组。
我认为订购东西的最佳方式是O（n-log（n）），比如Mergesort或Quicksort，但我知道我不确定。有什么想法吗？
这个问题肯定还有更多的约束。例如，如果数组仅由几个重复数字[1 3 2 6 3 1 2]组成，则可以使用counting sort在线性时间内执行此操作，但它将占用更多空间。
你可以注意的另一个算法是Dutch National Flag算法，它可以在线性时间内对3个重复数字进行排序。除此之外，我不认为（这里的无知不是幸福：P）我知道如何在线性时间内对正常数组进行排序。
即使你使用Radix sort，它也会占用O(m * n)，但如果使用m <<< n，你可以说它大约是O(n)
O(n lg n)是基于比较的排序的最佳选择，它不需要您知道任何关于正在排序的项目的信息，只需要您如何比较它们。对有界大小的整数列表进行排序（即，每个整数最多为K，其中K独立于n）是一个更专业的问题，因此可以使用比O(n lg n)运行更快的更专业的算法（例如基数排序）。