Haskell的快速​​入门 - 它究竟是什么？

Question

正如他们所说,"真正的快速排序就地排序".所以标准的短Haskell代码用于quicksort,

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 上已知答案:cf.伪快速排序时间复杂度.

Answer 1

这是链接列表的快速排序.

是的,这是快速的,只是不到位.它匹配快速排序的高级算法,同时更改低级实现以匹配链接列表的数据结构.这就是为什么它是链接列表的快速排序.

我更愿意说"quicksort最初是为了原地开发的",而不是"真正的quicksort就地完成".快速排序有很多变种,包括随机选择枢轴以避免更糟糕的行为等.这是链接列表快速排序的明智,清晰的定义.

这个定义与我们在英国为16岁的数学学生教授快速入学的方式完全一致.(我们正在教算法,而不是编程.)就地非常模糊了目的和设计,这就是为什么我们不教这个细节,尽管距离教授函数式编程或链表只有一百万英里.(这并没有改变这样一个事实,即当你有破坏性的更新阵列时,对交换技巧就地算法是最好的.)

此定义存在时间损失,因为它为两个子列表遍历列表两次.当然可以将其重写为分区而不是过滤,但我断言这是优化而不是在这里更改基本算法,快速排序.