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

敝帚自珍，这个是jaskell的：

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;
;

它使用了预定义的filter函数。

下面是haskell的版本：

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] 

haskell有语言内建的list comprehension，所以少调用一个filter函数。

这个是python的版本

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]]); 

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

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;
}

下面是C的

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 );;
  }
} 

综合比较下来，个人感觉还是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亦可