Haskell的快速​​排序 - 什么是真的吗？ [英] Haskell's quicksort - what is it really?

问题描述

正如他们所说，真正的快速排序排序就地。因此，标准的短哈斯克尔code 获得的快速排序，

As they say, "true quicksort sorts in-place". So the standard short Haskell code for quicksort,

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

哪种算法/计算过程的的是的这说明，毕竟？

what algorithm/computational process is it describing, after all?

这肯定不是<一个href="http://books.google.com/books?id=NLngYyWFl_YC&pg=PA160&lpg=PA160&dq=Hoare+partition&source=bl&ots=BxTmEA2mE5&sig=zQNbUb5jLURNaFmNwdyKvyskMU4&hl=en&sa=X&ei=MmsWUaSsJOfX0QXBmIHACQ&ved=0CGcQ6AEwCA"相对=nofollow>托尼·霍尔设计，缺乏其最本质的特征，就地划分算法。

It surely isn't what Tony Hoare devised, lacking its most defining feature, the in-place partitioning algorithm.

（答案可能是众所周知的，但尚未在这里SO）。

(the answer might be well known, but not yet here on SO).

修正：这个问题其实是一个重复：答案的的是的称的上SO毕竟：比照伪快速排序的时间复杂度。

correction: this question is in fact a duplicate: the answer is known on SO after all: cf. Pseudo-quicksort time complexity .

推荐答案

是啊，这是快速排序，只是没有在原地。它对于快速排序匹配高级算法，而改变低级实现匹配链表的数据结构。这就是为什么它是快速排序的链表。

It's quicksort for linked lists.

Yup, this is quicksort, just not in-place. It matches the high-level algorithm for quicksort whilst changing the low-level implementation to match the data structure of linked lists. That's why it's quicksort for linked lists.

我preFER说快速排序最初开发工作，就地不是真正的快速排序完成就地。有快速排序的许多变种，包括采摘随机转动，以避免更坏情况下的行为等。这是快速排序的链表一个合理的，明确的定义。

I'd prefer to say "quicksort was originally developed to work in-place" than "true quicksort is done in-place". There are many variants of quicksort including picking pivots randomly to avoid worse-case behaviour etc.. This is a sensible, clear definition of quicksort for linked lists.

这个定义完全一致，我们怎么教快速排序至16岁学生的数学在英国。 （我们教的算法，而不是编程。）就地非常模糊的目的而设计的，这就是为什么我们不教这个细节，尽管从教函数式编程或链表是一百万英里。 （这并不能改变一个事实，即对-交换伎俩原地算法是最好的，当你有破坏性的更新阵列。）

This definition exactly matches how we teach quicksort to 16 year-old maths students in the UK. (We're teaching algorithms, not programming.) In-place very much obscures the purpose and design, which is why we don't teach that detail, despite being a million miles from teaching functional programming or linked lists. (That doesn't change the fact that the pair-swapping trick in-place algorithm is best when you have destructive update arrays.)

有一个时间损失这个定义，因为它遍历该列表的两倍的两个子列表。这当然有可能改写这个来分区，而不是过滤器，但我断言，这是优化，而不是在这里改变的基本算法，快速排序。

There is a time penalty to this definition, since it traverses the list twice for the two sublists. It's certainly possible to rewrite this to partition rather than filter, but I assert that that's optimising rather than changing the fundamental algorithm here, quicksort.

这篇关于Haskell的快速​​排序 - 什么是真的吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！