C#快速排序的趣味实现：从Haskell说起
C#快速排序不好实现？
前一段时间有朋友问我，以下这段Haskell快速排序的代码，是否可以转化成C#中等价的Lambda表达式实现：
qsort [] = [] qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
我当时回答，C#中缺少一些基础的数据结构，因此不行。经过补充之后，就没有任何问题了。后来，我觉得这个问题挺有意思，难度适中，也挺考察“基础编程”能力的，于是就自己写了一个。如果您感兴趣的话，也不妨一试。
这段代码是经典的，常用的体现“函数式编程”省时省力的例子，用短短两行代码实现了一个快速排序的确了不起。您可能不了解Haskell，那么我在这里先解释一下。
首先，这里用到了函数式编程语言中最常用的一种数据结构：不可变的链表。这个数据结构事实上是一个单向链表，并且是“不可变”的。这种数据结构在F#中也有存在，它的结构用大致是这样的：
可见，这是一种递归的数据结构。如果我们把这种数据结构叫做是ImmutableList的话，那么每个ImmutableList对象就会包含一个元素的“值”，以及另一个ImmutableList对象（在上图中，每个框就是一个ImmutableList对象）。对于每个ImmutableList对象来说，这个“值”便是它的“头（Head）”，而内部的ImmutableList对象则是它的“尾（Tail）”。如果用C#来表示的话，ImmutableList在C#中的定义可能就是这样的：
public class ImmutableList<T> : IEnumerable<T>
{
public readonly static ImmutableList<T> Empty = new ImmutableList<T>(default(T));
private ImmutableList(T head, ImmutableList<T> tail)
{
this.Head = head;
this.Tail = tail;
}
public T Head { get; private set; }
public ImmutableList<T> Tail { get; private set; }
...
} 您一定意识到了，ImmutableList是一个不可变的链表数据结构，一旦构造之后就再也没有办法修改它的Head与Tail。此外，这里使用Empty来表示一个空链表1。因此，我们使用一个ImmutableList对象便可以代表整个链表，并可以通过Tail来遍历链表上所有的元素：
public class ImmutableList<T> : IEnumerable<T>
{
...
#region IEnumerable<T> Members
public IEnumerator<T> GetEnumerator()
{
var current = this;
while (current != Empty)
{
yield return current.Head;
current = current.Tail;
}
}
#endregion
#region IEnumerable Members
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
#endregion
} 我们再来观察Haskell代码，这段代码分为两行：
qsort [] = [] qsort (x:xs) = ...
这两行都定义了qsort函数，不过参数不同。这种做法在Haskell里被称为“模式匹配”，qsort后面的参数即是“模式”。第一行代码的参数“指明”是一个空链表，因此只有为qsort传入一个空的链表才会执行等号后的逻辑。如果为qsort函数传入的链表不为空，那么它即可被匹配为head和tail两部分，这在Haskell中表示为(head:tail)。因此，在调用第二行的qsort函数时，x会自动绑定为head元素，而xs会自动绑定为tail――结合之前的解释，我们可以知道x是“元素”类型，而xs是另一个链表（可能为空）。
C#快速排序的实现
由于C#没有Haskell的模式匹配方式，因此只能在方法内部使用if（或三元运算符?:）进行逻辑控制：
public static class ImmutableListExtensions
{
public static ImmutableList<T> QuickSort<T>(this ImmutableList<T> list, Func<T, T, int> compare)
{
if (list == null) throw new ArgumentNullException("list");
if (compare == null) throw new ArgumentNullException("compare");
if (list == ImmutableList<T>.Empty)
{
...
}
else
{
...
}
}
} 我们将QuickSort定义为ImmutableList的扩展方法，接受一个比较函数，最终则返回一个排序后的新的链表――因为ImmutableList是不可变的。
然后，我们再回到Haskell的代码，我们可以看出，第一行qsort函数由于接受了一个空链表，因此排序后的结果自然也是一个空链表。而第二行qsort则是一个较为标准的快速排序实现（快速排序的原理大致是：取一个元素作为pivot，先把那些比pivot小的元素放到pivot之前，再把比pivot大的放到pivot之后，然后对pivot的前后两部分分别采取快速排序。递归至最后，则整个链表排序完成）：
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
在上面这行代码中，filter高阶函数的作用是对一个链表进行过滤，并返回一个新的链表。它的第一个参数为过滤条件（如(< x)或(>= x)，它们都是匿名函数），而第二个参数则是被过滤的目标。（这里即为xs，它是qsort参数的tail）。“++”运算符在Haskell中的含义是连接两个链表，并返回连接的结果。
因此，这行代码的含义为：把小于x的元素使用qsort函数排序，连接上x元素，再连接上大于等于x的元素排序后的结果。于是，最后的结果便是一个排好序的链表。
值得注意的是，由于链表是种不可变的数据结构，因此无论是qsort函数，filter函数，还是++运算符，它们都会返回一个新的链表，而不会对原有链表作任何修改。这点是和我们传统所做的“数组排序”相比有所不同的地方。