时间复杂度Log(n)的排序算法

Question

有没有平均时间复杂度为log(n)的排序算法？？

示例 [8,2,7,5,0,1] 对给定数组进行排序，时间复杂度为 log(n)

Answer 1

不；事实上，这对于任意列表来说是不可能的！我们可以相当简单地证明这一点：对于排序我们必须做的绝对最少的事情是至少查看列表中的每个元素一次。毕竟，一个元素可能属于排序列表中的任何位置；如果我们不看某个元素，就不可能对数组进行排序。这意味着任何排序算法的下界为

，并且由于

n > log(n)

，

log(n)

排序是不可能的。

虽然

是下界，但大多数排序（如合并排序、快速排序）都是

n*log(n)

时间。事实上，虽然在某些情况下，我们可以使用基数排序在

时间内对纯数字列表进行排序，但我们实际上无法在小于

n*log(n)

的时间内对字符串等任意对象进行排序。

也就是说，有时该列表可能不是任意的；前任。我们有一个除了一个元素之外完全排序的列表，我们需要将该元素放入列表中。在这种情况下，像二叉搜索树这样的方法可以让您插入

log(n)

，但这只是可能的，因为我们正在操作单个元素。构建一棵树（即执行

插入）需要

n*log(n)

时间。

Answer 2

@domincm00 也提到答案是否定的。一般来说，当您看到时间复杂度为 Log N、基数为 2 的算法时，这意味着您将输入列表分为 2 组，并重复删除其中一组。在排序算法中，我们需要将所有元素放在适当的位置，如果我们在每次迭代中删除一半列表，这与排序功能无关。

最有效的排序算法的时间复杂度为 O(n)，但有一些限制。三个最著名的复杂度为 O(n) 的算法是：

计数排序，时间复杂度为 O(n+k)，其中 k 是给定列表中的最大数字。假设n>>k，你可以认为它的时间复杂度为O(n)
基数排序，时间复杂度为 O(d*(n+k))，其中 k 是输入列表的最大数量，d 是输入列表中可以拥有的最大位数。类似于计数排序，假设 n>>k && n>>d => 时间复杂度为 O(n)
桶排序时间复杂度为O(n)

但一般来说，由于这些算法的局限性，大多数实现都依赖于 O(n* log n) 算法，例如合并排序、快速排序和堆排序。

还有一些时间复杂度为 O(n^2) 的排序算法，推荐用于较小尺寸的列表，例如插入排序、选择排序和冒泡排序。

Answer 3

使用 PLA 可以对少数值范围较小的元素实现计数排序。

只有大规模并行计算才能做到这一点，通用 CPU 无法做到这一点，除非它们将其作为 SIMD 的一部分在硅中实现。

Answer 4

（答案依赖于活跃的同行评审帖子）

有更完整的答案... 重要的是，存在更优化的操作来实现排序，甚至可能比特定架构想象的排序更低。如果对输入有足够的了解，则可以部分构造具有预定义值的动态树，并且如果我的直觉是正确的，这应该允许（使用下面的算法）甚至可以使用特定架构进行 O(1) 排序。