有没有运行时间为O(n)并且可以原地排序的排序算法？
最佳答案
有一些最佳情况是 O(n)，但这可能是因为项目集合已经排序。您正在查看一些更好的平均 O(n log n)。
话虽如此，关于排序算法的 Wiki 还是相当不错的。有一张表格比较了流行的算法，说明了它们的复杂性、内存要求(表明算法是否可能“就位”)，以及它们是否将等值元素保留在其原始顺序(“稳定性”)。
此表(来自上述 Wiki)提供了一些更有趣的性能观察:
有些显然比其他的更容易实现，但我猜测值得实现的那些已经在您选择的库中完成了。
关于algorithm - 在时间 O(n) 中运行并就地排序的排序算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5688484/