C#快速排序不好實(shí)現(xiàn)？

前一段時(shí)間有朋友問我，以下這段Haskell快速排序的代碼，是否可以轉(zhuǎn)化成C#中等價(jià)的Lambda表達(dá)式實(shí)現(xiàn)：

qsort [] = []  
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs) 

我當(dāng)時(shí)回答，C#中缺少一些基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，因此不行。經(jīng)過補(bǔ)充之后，就沒有任何問題了。后來，我覺得這個(gè)問題挺有意思，難度適中，也挺考察“基礎(chǔ)編程”能力的，于是就自己寫了一個(gè)。如果您感興趣的話，也不妨一試。

這段代碼是經(jīng)典的，常用的體現(xiàn)“函數(shù)式編程”省時(shí)省力的例子，用短短兩行代碼實(shí)現(xiàn)了一個(gè)快速排序的確了不起。您可能不了解Haskell，那么我在這里先解釋一下。

首先，這里用到了函數(shù)式編程語言中最常用的一種數(shù)據(jù)結(jié)構(gòu)：不可變的鏈表。這個(gè)數(shù)據(jù)結(jié)構(gòu)事實(shí)上是一個(gè)單向鏈表，并且是“不可變”的。這種數(shù)據(jù)結(jié)構(gòu)在F#中也有存在，它的結(jié)構(gòu)用大致是這樣的：

可見，這是一種遞歸的數(shù)據(jù)結(jié)構(gòu)。如果我們把這種數(shù)據(jù)結(jié)構(gòu)叫做是ImmutableList的話，那么每個(gè)ImmutableList對(duì)象就會(huì)包含一個(gè)元素的“值”，以及另一個(gè)ImmutableList對(duì)象（在上圖中，每個(gè)框就是一個(gè)ImmutableList對(duì)象）。對(duì)于每個(gè)ImmutableList對(duì)象來說，這個(gè)“值”便是它的“頭（Head）”，而內(nèi)部的ImmutableList對(duì)象則是它的“尾（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; }  
 
    ...  
}  

您一定意識(shí)到了，ImmutableList是一個(gè)不可變的鏈表數(shù)據(jù)結(jié)構(gòu)，一旦構(gòu)造之后就再也沒有辦法修改它的Head與Tail。此外，這里使用Empty來表示一個(gè)空鏈表1。因此，我們使用一個(gè)ImmutableList對(duì)象便可以代表整個(gè)鏈表，并可以通過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  
}  

我們?cè)賮碛^察Haskell代碼，這段代碼分為兩行：

qsort [] = []  
qsort (x:xs) = ... 

這兩行都定義了qsort函數(shù)，不過參數(shù)不同。這種做法在Haskell里被稱為“模式匹配”，qsort后面的參數(shù)即是“模式”。***行代碼的參數(shù)“指明”是一個(gè)空鏈表，因此只有為qsort傳入一個(gè)空的鏈表才會(huì)執(zhí)行等號(hào)后的邏輯。如果為qsort函數(shù)傳入的鏈表不為空，那么它即可被匹配為head和tail兩部分，這在Haskell中表示為(head:tail)。因此，在調(diào)用第二行的qsort函數(shù)時(shí)，x會(huì)自動(dòng)綁定為head元素，而xs會(huì)自動(dòng)綁定為tail——結(jié)合之前的解釋，我們可以知道x是“元素”類型，而xs是另一個(gè)鏈表（可能為空）。

C#快速排序的實(shí)現(xiàn)

由于C#沒有Haskell的模式匹配方式，因此只能在方法內(nèi)部使用if（或三元運(yùn)算符?:）進(jìn)行邏輯控制：

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的擴(kuò)展方法，接受一個(gè)比較函數(shù)，最終則返回一個(gè)排序后的新的鏈表——因?yàn)镮mmutableList是不可變的。

然后，我們?cè)倩氐紿askell的代碼，我們可以看出，***行qsort函數(shù)由于接受了一個(gè)空鏈表，因此排序后的結(jié)果自然也是一個(gè)空鏈表。而第二行qsort則是一個(gè)較為標(biāo)準(zhǔn)的快速排序?qū)崿F(xiàn)（快速排序的原理大致是：取一個(gè)元素作為pivot，先把那些比pivot小的元素放到pivot之前，再把比pivot大的放到pivot之后，然后對(duì)pivot的前后兩部分分別采取快速排序。遞歸至***，則整個(gè)鏈表排序完成）：

qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs) 

在上面這行代碼中，filter高階函數(shù)的作用是對(duì)一個(gè)鏈表進(jìn)行過濾，并返回一個(gè)新的鏈表。它的***個(gè)參數(shù)為過濾條件（如(< x)或(>= x)，它們都是匿名函數(shù)），而第二個(gè)參數(shù)則是被過濾的目標(biāo)。（這里即為xs，它是qsort參數(shù)的tail）。“++”運(yùn)算符在Haskell中的含義是連接兩個(gè)鏈表，并返回連接的結(jié)果。

因此，這行代碼的含義為：把小于x的元素使用qsort函數(shù)排序，連接上x元素，再連接上大于等于x的元素排序后的結(jié)果。于是，***的結(jié)果便是一個(gè)排好序的鏈表。

值得注意的是，由于鏈表是種不可變的數(shù)據(jù)結(jié)構(gòu)，因此無論是qsort函數(shù)，filter函數(shù)，還是++運(yùn)算符，它們都會(huì)返回一個(gè)新的鏈表，而不會(huì)對(duì)原有鏈表作任何修改。這點(diǎn)是和我們傳統(tǒng)所做的“數(shù)組排序”相比有所不同的地方。

現(xiàn)在，您就來嘗試實(shí)現(xiàn)那個(gè)QuickSort方法吧。您可以為ImmutableList補(bǔ)充所需的成員，只要保持ImmutableList的各種特性不變，并實(shí)現(xiàn)快速排序便可以了。

以上就實(shí)現(xiàn)了C#快速排序。本文來自老趙點(diǎn)滴：《趣味編程：函數(shù)式鏈表的快速排序》

【編輯推薦】

1. 理解C# String類型：特殊的引用類型
2. 關(guān)于interface繼承來源的討論
3. C#顯式實(shí)現(xiàn)接口原理淺析
4. C# interface學(xué)習(xí)經(jīng)驗(yàn)淺談
5. C# interface使用實(shí)例分析