QuickSort

Haskell:

quicksort [] = []
quicksort (x:xs) = quicksort [y | y <- xs, y<x ]
                   ++ [x]
                   ++ quicksort [y | y <- xs, y>=x]

Python:

def qsort(L):
    if not L : return L
    return qsort([i for i in L[1:] if i < L[0]]) + \
                 L[0:1] + \
                 qsort([i for i in L[1:] if i >=L[0]])

C++ :
template<T>
vector<T> qsort(vector<T> L){
    if (L.size()==0) return L;
    less = vector<T>;
    greater = vector<T>;
    me = vector<T>;
    me.push_back(L[0]);
    for(int i = 1 ; i < L.size(); i++){
        if (L[i] < L[0]){ less.push_back(L[i]) ;}
        else { greater.push_back(L[i]) ; }
    }
    /* 如果 vector 支持 + 操作符号话。*/
    return qsort(less) +  me + qsort(greater)
}

Java : 我不是太熟悉，写出大概

Interface Comparable{
....
};
list_of_compareable qsort( list_of_comparable L){
}

当然，不能单单以程序长短论英雄，本质上，他们的算法都一模一样。

比较：
1. Java 和其他相比，在 type 的多态支持最为不好，他的参数必须是
一定的类型 compareable ，而且一定所有的使用 qsort 的，都要继承
(或者叫做实现接口) comparable. 这样类型就非常多了。

Haskell, C++, Python 都支持的比较好。任何支持 < >= 的类型，都可以
作为参数，传递给 qsort

2. Haskell 和 C++ 都支持编译类型检查。Python 不支持。
这样 Python 也是最灵活的，在 Python 中, func(a) ，如果在
func 中只使用了 a.printme() ，那么凡是带有 printme 的 attribute 的对象
都可以作为 func 的参数，不必特别要求 a 一定要是哪一个 class 的 instance.

Python 为如此灵活的处理，付出了代价，就是不支持静态类型检查。

3. Haskell 和 C++ 都支持静态类型检查，编译的时候就能够指出类型错误。
这限制了灵活性，减少了程序员犯错的机会，但是他们已经够灵活的了。

为了实现这一点， Haskell 和 C++ 都付出了代价。
Haskell 的编译器的实现要复杂的多，要支持类型的自动推导。

C++ 的代价就是，要注意 T 类型的赋值操作符重载函数，和赋值构造函数的操作符
重载，这样就不可避免的要注意深拷贝和浅拷贝的问题，还要注意大于等于号的操作
符重载。

4. 单从效率上讲，四种算法都不是 in place 的，都要拷贝数据，入栈出栈，都不怎么样
，
其他书上还有 C 语言的例子，是效率最高的，不用多余的内存空间，但是他和上面四种

语言的区别太大了，因为 C 中没有高级数据结构，还有很多，例如没有类型多态的概念，

除非用 macro 的方法，但是 macro 是天使也是魔鬼，会让源程序看起来很丑，会带来太
多
问题。

由于区别太大，可比性不强，故没有列出来。



结论：
从比较中看到四种语言在处理 type 的多态的不同处理。
其中 java 最弱， C++ 和 Haskell的实现很不错，但是代价是复杂的编译器实现，
python 的最强，代价是编译期不检查动态类型(只有杀人的想法没有成为事实，就不是错)
而是运行期检查(只有真正杀人成为事实的时候才是错)

我对 java 不熟，欢迎熟悉 java 的人为我指出错误。

下面是 scheme 的实现

(define (filter alist pred)
  (cond
   ((null? alist) '())
   ((pred (car alist))
    (cons (car alist) (filter (cdr alist) pred)))
   (t (filter (cdr alist) pred))))


(define (quick-sort alist)
  (if (null? alist)
      alist
      (append (quick-sort (filter (cdr alist)
                                  (lambda (x) (<= x (car alist)))))
              (cons (car alist) '())
              (quick-sort (filter (cdr alist)
                                  (lambda (x) (> x (car alist) )))))))