jaskell/haskelll/python/java/c 中的quicksort

敝帚自珍，这个是jaskell的：
[code:1]
qsort [] = []
| h:tl = qsort smaller ++ [h] ++ qsort bigger where
smaller = filter(\x->x<h, tl);
bigger = filter(\x->x>=h, tl);
filter = jaskell.prelude.filter;
;
[/code:1]
它使用了预定义的filter函数。

下面是haskell的版本：

[code:1]qsort [] = []
qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_ge_x
where
elts_lt_x = [y | y <- xs, y < x]
elts_ge_x = [y | y <- xs, y >= x] [/code:1]
haskell有语言内建的list comprehension，所以少调用一个filter函数。

这个是python的版本

[code:1]def qsort(L):
if len(L) <= 1: return L
return qsort([lt for lt in L[1:] if lt < L[0]]) + L[0:1] + \
qsort([ge for ge in L[1:] if ge >= L[0]]) [/code:1]

然后是java版本，这个版本还只能做整数排序，一点范型都没有

[code:1]void quickSort(int[] Array, int p, int r){
if(p < r){
int q = partition(Array, p, r);
quickSort(Array, p, q - 1);
quickSort(Array, q + 1, r);
}
}

int partition(int[] Array, int p, int r){
int x = Array[r];
int i = p - 1;

for(int j = p; j <= r - 1; j++){
if(Array[j] <= x){
i++;
int t1 = Array[i]; Array[i] = Array[j];
Array[j] = t1;
}
}
int t2 = Array[i+1]; Array[i+1] = Array[r]; Array[r] = t2;
return i + 1;
}[/code:1]

下面是C的

[code:1]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);

t = a[l];
a[l] = a[hi];
a[hi] = t;

qsort( a, lo, l-1 );
qsort( a, l+1, hi );
}
} [/code:1]

综合比较下来，个人感觉还是haskell和jaskell的版本最易懂，python次之，java和c这种命令式就显得复杂多了。

当然，不同的语言有不同的应用场合，我举这个例子不是偏颇地说java/c不好，而是给大家一个fp可以简洁成什么样子的感性的认识。

Java 和 C看上去比较繁琐，
30%原因是它们是强类型语言，类型声明就占了很多代码量；这和是否支持FP无关；
另30%原因是其他语言提供了简洁的语法(比如for in)，又减掉了很多代码；这也和是否支持FP无关。

10%的原因才是FP的好处，比如python的内建函数filter, map提供了很强大的功能。不过嘛在你的示例中并没有用到，所以只能占10%。

结论：FP是好东西，但你的举例不够具有说服力。

1。只怕上面几个例子里的类型声明占不到30%这么夸张吧？而且，haskell也是静态强类型的呀。
2。简洁的语法，不错啊。我现在要说明的就是语法。这也是针对在另一个帖子里面大家对haskell式的语法不认可。我要说明的是，haskell/jaskell式的语法是可以很易懂的。
3。python例子没有用filter, map也仍然比java/c简洁很多，这说明什么呢？
4。java/c这种命令式里面的各个赋值，循环难道不是造成代码难懂的原因之一？

qsort :: [a] -> [a]
qsort [] = []
qsort (x: xs) = qsort [y| y <- xs, y < x] ++ x ++ qsort [y| y <- xs, y >= x]
这是我见过的世界上最美丽的语言
虽然这个版本的qsort效率超低
高效的那个没看懂 ft

支持 list ++ 操作符 和 list comprehension 的语言都能写成这个样子。

list 的 ++ 操作符，list comprehension.使得 list 操作简单。

我也对 Haskell 很有兴趣。就是难度太高。

还不如看这篇文章，04年就翻译好了.
http://wiki.woodpecker.org.cn/moin/PyCkBk-2-12

fp的性能是老大难了，连ocaml都有人说得用imperative方式写才能达到最快的速度。
好在速度很多时候不是主要的衡量标准。

补充一个一行的 python 解法：

sort=lambda ary:{False:lambda:ary,True:lambda:sort([x for x in ary[1:] if x<=ary[0]]) + [ary[0]] + sort([x for x in ary[1:] if x > ary[0]])}[len(ary)>1]()

举QSort这个例子显然不够有说服力。
看看这个用Ruby作的，可与Haskell的版本相媲美：

 def qsort(list)
   return [] if (x,*xs=*list).empty?
   less, more = xs.partition{|y| y < x}
   qsort(less) + [x] + qsort(more)
 end

Block比List Comprehensions好用多了。

x, *xs = list亦可