为什么极简主义，例如 Haskell 快速排序不是“真正的"?快速排序? [英] Why is the minimalist, example Haskell quicksort not a "true" quicksort?

问题描述

Haskell 的网站引入了一个非常有吸引力的 5 行 quicksort 函数，如下所示.

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 代码那样针对更长的列表进行缩放.'

A link below the C version directs to a page that states 'The quicksort quoted in Introduction isn't the "real" quicksort and doesn't scale for longer lists like the c code does.'

为什么上面的 Haskell 函数不是真正的快速排序?它如何无法扩展更长的列表?

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

推荐答案

真正的快速排序有两个美丽的方面:

The true quicksort has two 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!

这篇关于为什么极简主义，例如 Haskell 快速排序不是“真正的"?快速排序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！