为什么是极简主义，例如哈斯克尔快速排序不是＆QUOT;真＆QUOT;快速排序？ [英] Why is the minimalist, example Haskell quicksort not a "true" quicksort?

问题描述

Haskell的网站引入了一个非常有吸引力的5行快速排序函数，如下所示。

Haskell's website introduces a very attractive 5-line quicksort function, as seen below.

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

，还包括一个的真用C快速排序的。

// To sort array a[] of size n: qsort(a,0,n-1)

void qsort(int a[], int lo, int hi) 
{
  int h, l, p, t;

  if (lo < hi) {
    l = lo;
    h = hi;
    p = a[hi];

    do {
      while ((l < h) && (a[l] <= p)) 
          l = l+1;
      while ((h > l) && (a[h] >= p))
          h = h-1;
      if (l < h) {
          t = a[l];
          a[l] = a[h];
          a[h] = t;
      }
    } while (l < h);

    a[hi] = a[l];
    a[l] = p;

    qsort( a, lo, l-1 );
    qsort( a, l+1, hi );
  }
}

下面的C版本的链接定向到各国的页在引言中引用的快速排序是不是真正的快速排序，并不能扩展为象C code较长的列表呢。 的

为什么上面的Haskell功能不是真正的快速排序？它是如何失败，以规模求较长的列表？

Why is the above Haskell function not a true quicksort? How does it fail to scale for longer lists?

编辑：这里是指这个快速排序定义可以找到的链接。
<一href=\"http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell\">http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell

Here is the link at which this quicksort definition can be found. http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell

推荐答案

真正的快速排序有2个漂亮的方面：

The true quicksort has 2 beautiful aspects:

1. 分而治之;把问题分解成两个较小的问题。


2. 分区就地元素。

短的Haskell实施例证明（1），但不（2）。如何（2）完成可能不是很明显，如果你还不知道的技术！

The short Haskell example demonstrates (1), but not (2). How (2) is done may not be obvious if you don't already know the technique!

这篇关于为什么是极简主义，例如哈斯克尔快速排序不是＆QUOT;真＆QUOT;快速排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！