Haskell的网站介绍了一条非常吸引人的5行quicksort function ,如下所示。
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 代码那样针对更长的列表进行缩放。”
为什么上面的 Haskell 函数不是真正的快速排序?它如何无法扩展更长的列表?
最佳答案
真正的快速排序有两个美妙的方面:
- 分而治之:将问题分解为两个较小的问题。
- 就地对元素进行分区。
简短的 Haskell 示例演示了 (1),但没有演示 (2)。如果您还不了解该技术,则 (2) 是如何完成的可能并不明显!
关于sorting - 为什么简约的 Haskell 快速排序不是 "true"快速排序?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7717691/