algorithm - 是否需要时间复杂度为 O(n) 的更好的排序算法？

Question

我正在开发一个程序，它只使用一个 for 循环 N 次并对 N 个元素进行排序。只想问，值不值？因为我知道它会起作用，因为它在纸上运行得很好。它还使用比较。我还想知道 Radix Sort 是否有任何缺点。干杯。

Answer 1

您的帖子提到您正在使用比较。基于比较的排序算法需要对平均输入进行至少 O(n log n) 次比较。请注意，比较排序算法的 Ω(n log n) 下限已使用信息论在数学上得到证明。您只能实现 O(n) 是输入数据已经排序的最佳情况。Wikipedia上有更多关于排序算法的详细信息。

我只会将您的排序算法实现为具有挑战性的编程练习。大多数现代语言已经提供了经过彻底测试的快速排序算法。