Haskell的快速排序 - 它到底是什么？

Question

正如他们所说，"真正的快速排序是原地排序"。因此，快速排序的标准Haskell代码为：

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
  where
    lesser  = filter (< p) xs
    greater = filter (>= p) xs

它到底描述了什么算法/计算过程？

毫无疑问，它不是Tony Hoare 设计的算法，缺少其最显著的特征——原地分区算法。

（答案可能已经众所周知，但在 SO 上还没有。）

---

更正：事实上，这个问题是一个重复的问题：答案在SO上已经被知道了：参见Pseudo-quicksort time complexity。

- Will Ness

---

这是在描述快速排序算法。 - Thomas

在你提供的文章中没有证据表明 Hoare 认为如果不是原地排序就不算快速排序。 - AndrewC

@AndrewC 是的，那篇文章可能不是支持我的观点的最佳选择。但这就是 WP。我的意思是（我看到很多人都这样认为），在原始论文中它是如何描述的 - 那里的分区算法非常具体，有交换和移动边界。根据那种观点，对于（不可变的）链接列表，不存在快速排序这样的东西。（对于可变的列表，我们可以制作一个单元地址数组并交换单元内容 - （当然不是在 Haskell 中））。 - Will Ness

相关：伪快速排序时间复杂度 - jfs

根据您提供的维基百科文章中的文字描述，该代码是快速排序算法的实现。 - jfs

请参考以下链接，了解Haskell快速排序的效率：https://stackoverflow.com/questions/23318948/haskell-quicksort-efficiency - Will Ness

Answer 1

这是链表的快速排序算法。

没错，这就是快速排序算法，只不过不是in-place（原地排序）。它匹配快速排序的高级算法，同时改变了低级实现以适应链表这种数据结构。这就是为什么它被称为链表的快速排序。

我更愿意说“快速排序最初是为了in-place排序而开发的”而不是“真正的快速排序是in-place排序”。有许多快速排序的变体，包括随机选择枢轴来避免最坏情况等。这是链表的明智、清晰的快速排序定义。

这个定义与我们在英国教16岁数学学生快速排序的方式完全一致。（我们教授算法，而不是编程。）In-place非常模糊了目的和设计，这就是为什么我们不教授这个细节，尽管离函数式编程或链表相差甚远。（尽管如此，使用破坏性更新数组的对换技巧in-place算法在你有时会是最好的选择。）

对于这个定义，存在时间惩罚，因为它需要遍历两次列表来切割成两个子列表。重写这个算法以进行分区而不是筛选肯定是可行的，但我断言这是优化而不是改变基本算法，即快速排序。

- AndrewC

---

即使是只遍历列表一次的重写，它们仍然没有原地分区，而是通过创建中间列表来实现。... partition 仍然在执行相同的操作 - 它将一个列表分成两个新列表。 - Will Ness

我认为如果你问托尼·霍尔(Tony Hoare)，“你能在链表上执行快速排序吗？”，他会说类似于“嗯...原地更新会太慢，但你可以为递归应用创建新的链接列表。” - AndrewC

@MariusKavansky "In-place" 的意思是在不创建列表的新副本的情况下进行操作。如果您在内存较小的计算机上有大量数据，则这一点非常重要。 - AndrewC

@AndrewC，我把它和稳定混淆了。默认情况下它不稳定，对吗？ - Alan Coromano

@MariusKavansky 在这个版本中是稳定的，因为 filter 保留了顺序，并且枢轴值 p 仍然在原始列表中跟随它的任何元素的前面。 - AndrewC

Answer 2

所有原地算法在 Haskell 中都需要一些“仪式”，其中可变状态被隐藏在一个单子中。上述算法是快速排序，只不过不是原地排序。

- Landei

---

快速排序是由Tony Hoare定义的，其特点是采用原地分区算法。很抱歉没有更加强调这一点，我已经编辑了问题。 - Will Ness

如果你已经知道你想听到什么（“这不是Tony Hoare定义的快速排序”），那你为什么要问呢？然而，由于你无法使用Haskell列表编写原地算法，因此在选择数据结构的情况下，你的代码尽可能接近快速排序的思想。 - Landei

我并没有看到矛盾之处。问题是这样问的，“它不是X，但是它是什么？”据我所知，在SO上提出一个问题时，即使你认为自己已经知道答案，也可以在SO上公开发表。我真的没想到会有争议。 - Will Ness

Answer 3

预期的答案（来自这里）是这是“真正的森林砍伐树种排序”。事实证明，它也在haskellwiki上提到。

- Will Ness

---

如果你把树从树排序中移除，那么使用“树排序”这个名称的理由肯定比把交换从快速排序中移除少。按照这种逻辑，你可以称之为去交换化的快速排序。 - AndrewC

@AndrewC，我真的不知道该怎么办，安德鲁。我应该取消接受吗？Reddit讨论中的论点对我有些吸引力。但是你看，我认为它是这样的：我们可以将类型视为带标签的列表（来自Lisp角度）。树只是一个标签；当我们创建树时，较小的放在左边，较大的放在右分支上。因此，当我们将其分成两组时，本质上与将它们放入树的两个分支 - 左侧和右侧 - 相同。换句话说，树与三元组“同构”。 - Will Ness

@AndrewC 但在原始算法中，分区是通过交换完成的。在树排序的任何步骤中，我们都不考虑将较小的元素放在右侧，然后将它们交换到左侧 - 当我们创建树时，首先为空，然后当我们逐个插入元素时，每个元素要么进入左侧，要么进入右侧。...顺便说一句，去除交换的快速排序名称实际上非常好，我认为。顺便说一句，很高兴你回来了。 :) - Will Ness

我并不真的反对称其为"被砍伐的树排序"，因为它具有诱人的表面讽刺意味，并在概念上起作用，但我认为它与树排序的相似度并不比与数组交换快速排序更高。 - AndrewC

我猜这更多是一种观点的问题。就是这样。 - Will Ness