span stylecolor:#333333span stylebackground-color:#ffffffqsort [] [] qsort (x:xs) qsort (filter ( x) xs) [x] qsort (filter ( x) xs)/span/span我当时回答C#中缺少一些基础的数据结构因此不行。经过补充之后就没有任何问题了。后来我觉得这个问题挺有意思难度适中也挺考察“基础编程”能力的于是就自己写了一个。如果您感兴趣的话也不妨一试。这段代码是经典的常用的体现“函数式编程”省时省力的例子用短短两行代码实现了一个快速排序的确了不起。您可能不了解Haskell那么我在这里先解释一下。首先这里用到了函数式编程语言中最常用的一种数据结构不可变的链表。这个数据结构事实上是一个单向链表并且是“不可变”的。这种数据结构在F#中也有存在它的结构用大致是这样的可见这是一种递归的数据结构。如果我们把这种数据结构叫做是ImmutableList的话那么每个ImmutableList对象就会包含一个元素的“值”以及另一个ImmutableList对象在上图中每个框就是一个ImmutableList对象。对于每个ImmutableList对象来说这个“值”便是它的“头Head”而内部的ImmutableList对象则是它的“尾Tail”。如果用C#来表示的话ImmutableList在C#中的定义可能就是这样的span stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#0000ffpublic class /spanspan stylecolor:#2b91afImmutableList/spanT : span stylecolor:#2b91afIEnumerable/spanT { span stylecolor:#0000ffpublic readonly static /spanspan stylecolor:#2b91afImmutableList/spanT Empty span stylecolor:#0000ffnew /spanspan stylecolor:#2b91afImmutableList/spanT(span stylecolor:#0000ffdefault/span(T)); span stylecolor:#0000ffprivate /spanImmutableList(T head, span stylecolor:#2b91afImmutableList/spanT tail) { span stylecolor:#0000ffthis/span.Head head; span stylecolor:#0000ffthis/span.Tail tail; } span stylecolor:#0000ffpublic /spanT Head { span stylecolor:#0000ffget/span; span stylecolor:#0000ffprivate set/span; } span stylecolor:#0000ffpublic /spanspan stylecolor:#2b91afImmutableList/spanT Tail { span stylecolor:#0000ffget/span; span stylecolor:#0000ffprivate set/span; } ... } /span/span您一定意识到了ImmutableList是一个不可变的链表数据结构一旦构造之后就再也没有办法修改它的Head与Tail。此外这里使用Empty来表示一个空链表1。因此我们使用一个ImmutableList对象便可以代表整个链表并可以通过Tail来遍历链表上所有的元素span stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#0000ffpublic class /spanspan stylecolor:#2b91afImmutableList/spanT : span stylecolor:#2b91afIEnumerable/spanT { ... span stylecolor:#0000ff#region /spanIEnumerableT Members span stylecolor:#0000ffpublic /spanspan stylecolor:#2b91afIEnumerator/spanT GetEnumerator() { span stylecolor:#0000ffvar /spancurrent span stylecolor:#0000ffthis/span; span stylecolor:#0000ffwhile /span(current ! Empty) { span stylecolor:#0000ffyield return /spancurrent.Head; current current.Tail; } } span stylecolor:#0000ff#endregion #region /spanIEnumerable Members span stylecolor:#2b91afIEnumerator IEnumerable/span.GetEnumerator() { span stylecolor:#0000ffreturn this/span.GetEnumerator(); } span stylecolor:#0000ff#endregion /span} /span/span我们再来观察Haskell代码这段代码分为两行span stylecolor:#333333span stylebackground-color:#ffffffqsort [] [] qsort (x:xs) .../span/span这两行都定义了qsort函数不过参数不同。这种做法在Haskell里被称为“模式匹配”qsort后面的参数即是“模式”。第一行代码的参数“指明”是一个空链表因此只有为qsort传入一个空的链表才会执行等号后的逻辑。如果为qsort函数传入的链表不为空那么它即可被匹配为head和tail两部分这在Haskell中表示为(head:tail)。因此在调用第二行的qsort函数时x会自动绑定为head元素而xs会自动绑定为tail——结合之前的解释我们可以知道x是“元素”类型而xs是另一个链表可能为空。由于C#没有Haskell的模式匹配方式因此只能在方法内部使用if或三元运算符?:进行逻辑控制span stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#0000ffpublic static class /spanspan stylecolor:#2b91afImmutableListExtensions /span{ span stylecolor:#0000ffpublic static /spanspan stylecolor:#2b91afImmutableList/spanT QuickSortT(span stylecolor:#0000ffthis /spanspan stylecolor:#2b91afImmutableList/spanT list, span stylecolor:#2b91afFunc/spanT, T, span stylecolor:#0000ffint/span compare) { span stylecolor:#0000ffif /span(list span stylecolor:#0000ffnull/span) span stylecolor:#0000ffthrow new /spanspan stylecolor:#2b91afArgumentNullException/span(span stylecolor:#a31515list/span); span stylecolor:#0000ffif /span(compare span stylecolor:#0000ffnull/span) span stylecolor:#0000ffthrow new /spanspan stylecolor:#2b91afArgumentNullException/span(span stylecolor:#a31515compare/span); span stylecolor:#0000ffif /span(list span stylecolor:#2b91afImmutableList/spanT.Empty) { ... } span stylecolor:#0000ffelse /span{ ... } } } /span/span我们将QuickSort定义为ImmutableList的扩展方法接受一个比较函数最终则返回一个排序后的新的链表——因为ImmutableList是不可变的。然后我们再回到Haskell的代码我们可以看出第一行qsort函数由于接受了一个空链表因此排序后的结果自然也是一个空链表。而第二行qsort则是一个较为标准的快速排序实现快速排序的原理大致是取一个元素作为pivot先把那些比pivot小的元素放到pivot之前再把比pivot大的放到pivot之后然后对pivot的前后两部分分别采取快速排序。递归至最后则整个链表排序完成span stylecolor:#333333span stylebackground-color:#ffffffqsort (x:xs) qsort (filter ( x) xs) [x] qsort (filter ( x) xs)/span/span在上面这行代码中filter高阶函数的作用是对一个链表进行过滤并返回一个新的链表。它的第一个参数为过滤条件如( x)或( x)它们都是匿名函数而第二个参数则是被过滤的目标。这里即为xs它是qsort参数的tail。“”运算符在Haskell中的含义是连接两个链表并返回连接的结果。因此这行代码的含义为把小于x的元素使用qsort函数排序连接上x元素再连接上大于等于x的元素排序后的结果。于是最后的结果便是一个排好序的链表。值得注意的是由于链表是种不可变的数据结构因此无论是qsort函数filter函数还是运算符它们都会返回一个新的链表而不会对原有链表作任何修改。这点是和我们传统所做的“数组排序”相比有所不同的地方。现在您就来尝试实现那个QuickSort方法吧。您可以为ImmutableList补充所需的成员只要保持ImmutableList的各种特性不变并实现快速排序便可以了。