依赖于数据初始组织的排序算法

Question

我目前正在研究排序算法。我研究过快速排序算法依赖于数据的初始组织。如果对数组进行排序，则快速排序将变得更慢。是否还有其他类型的数据依赖于最初的数据组织？

Answer 1

当然了。插入排序将是具有降序排序输入的O(n)：

define selection_sort (arr):
  out = []
  while not (arr.is_empty()):
      x = arr.pop()
      out = insert x out
  return out

因为每个insert调用都是O(1)。如果使用pop_last()而不是pop()，那么在排序的升序输入上它将是最快的(这假设pop()和/或pop_last()本身是O(1)本身)。

Answer 2

所有快速排序算法都尽量减少比较和移动操作。最小化移动操作取决于初始元素排序。我假设您是指初始组织的初始元素排序。

此外，最快的现实世界算法利用参考地点，这也显示了依赖于初始排序。

如果您只感兴趣于一个显著减缓或加速排序的依赖项，例如，气泡排序将在一次传递排序数据时完成。

最后，许多排序算法的平均时间复杂度O(N log N)，但最坏的情况复杂度O(N^2)。这意味着这些O(N^2)算法存在特定的输入(例如排序或反向排序)，这些输入会引发不良的运行时行为。一些快速排序版本就是这些算法的例子。

Answer 3

如果你要问的是“我是否应该担心我应该在一个案例的基础上选择哪种排序算法？”，除非你正在处理成千上万的运算，否则简单的回答是“不”。大多数情况下，快速排序将是很好的(使用计算的枢轴进行快速排序，比如Java)。

在一般情况下，快速排序已经足够了。

另一方面，如果您的系统总是以一致的初始排序方式期望源数据，而且每次都需要长的CPU时间和功率，那么您肯定会为这种角点情况找到正确的算法。