日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

RELATEED CONSULTING
相關咨詢
選擇下列產(chǎn)品馬上在線溝通
服務時間：8:30-17:00
你可能遇到了下面的問題
關閉右側工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
C#快速排序的趣味實現(xiàn)：從Haskell說起

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

創(chuàng)新互聯(lián)提供網(wǎng)站設計、成都網(wǎng)站制作、網(wǎng)頁設計，品牌網(wǎng)站設計，1元廣告等致力于企業(yè)網(wǎng)站建設與公司網(wǎng)站制作，十年的網(wǎng)站開發(fā)和建站經(jīng)驗,助力企業(yè)信息化建設，成功案例突破上千余家,是您實現(xiàn)網(wǎng)站建設的好選擇.

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

 
 
 
 
      
  
  
  
  1. qsort [] = []  
    2.   
  
  
  
  2. qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs) 
    3.

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

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

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

可見，這是一種遞歸的數(shù)據(jù)結構。如果我們把這種數(shù)據(jù)結構叫做是ImmutableList的話，那么每個ImmutableList對象就會包含一個元素的“值”，以及另一個ImmutableList對象（在上圖中，每個框就是一個ImmutableList對象）。對于每個ImmutableList對象來說，這個“值”便是它的“頭（Head）”，而內(nèi)部的ImmutableList對象則是它的“尾（Tail）”。如果用C#來表示的話，ImmutableList在C#中的定義可能就是這樣的：

 
 
 
 
      
  
  
  
  1. public class ImmutableList : IEnumerable  
    2.   
  
  
  
  2. {  
    3.   
  
  
  
  3.     public readonly static ImmutableList Empty = new ImmutableList(default(T));  
    4.   
  
  
  
  4.  
    5.   
  
  
  
  5.     private ImmutableList(T head, ImmutableList tail)  
    6.   
  
  
  
  6.     {  
    7.   
  
  
  
  7.         this.Head = head;  
    8.   
  
  
  
  8.         this.Tail = tail;  
    9.   
  
  
  
  9.     }  
    10.   
  
  
  
  10.  
    11.   
  
  
  
  11.     public T Head { get; private set; }  
    12.   
  
  
  
  12.  
    13.   
  
  
  
  13.     public ImmutableList Tail { get; private set; }  
    14.   
  
  
  
  14.  
    15.   
  
  
  
  15.     ...  
    16.   
  
  
  
  16. }  
    17.

您一定意識到了，ImmutableList是一個不可變的鏈表數(shù)據(jù)結構，一旦構造之后就再也沒有辦法修改它的Head與Tail。此外，這里使用Empty來表示一個空鏈表1。因此，我們使用一個ImmutableList對象便可以代表整個鏈表，并可以通過Tail來遍歷鏈表上所有的元素：

 
 
 
 
      
  
  
  
  1. public class ImmutableList : IEnumerable  
    2.   
  
  
  
  2. {  
    3.   
  
  
  
  3.     ...  
    4.   
  
  
  
  4.  
    5.   
  
  
  
  5.     #region IEnumerable Members  
    6.   
  
  
  
  6.  
    7.   
  
  
  
  7.     public IEnumerator GetEnumerator()  
    8.   
  
  
  
  8.     {  
    9.   
  
  
  
  9.         var current = this;  
    10.   
  
  
  
  10.         while (current != Empty)  
    11.   
  
  
  
  11.         {  
    12.   
  
  
  
  12.             yield return current.Head;  
    13.   
  
  
  
  13.             current = current.Tail;  
    14.   
  
  
  
  14.         }  
    15.   
  
  
  
  15.     }  
    16.   
  
  
  
  16.  
    17.   
  
  
  
  17.     #endregion  
    18.   
  
  
  
  18.  
    19.   
  
  
  
  19.     #region IEnumerable Members  
    20.   
  
  
  
  20.  
    21.   
  
  
  
  21.     IEnumerator IEnumerable.GetEnumerator()  
    22.   
  
  
  
  22.     {  
    23.   
  
  
  
  23.         return this.GetEnumerator();  
    24.   
  
  
  
  24.     }  
    25.   
  
  
  
  25.  
    26.   
  
  
  
  26.     #endregion  
    27.   
  
  
  
  27. }  
    28.

我們再來觀察Haskell代碼，這段代碼分為兩行：

 
 
 
 
      
  
  
  
  1. qsort [] = []  
    2.   
  
  
  
  2. qsort (x:xs) = ... 
    3.

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

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

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

 
 
 
 
      
  
  
  
  1. public static class ImmutableListExtensions  
    2.   
  
  
  
  2. {  
    3.   
  
  
  
  3.     public static ImmutableList QuickSort(this ImmutableList list, Funcint> compare)  
    4.   
  
  
  
  4.     {  
    5.   
  
  
  
  5.         if (list == null) throw new ArgumentNullException("list");  
    6.   
  
  
  
  6.         if (compare == null) throw new ArgumentNullException("compare");  
    7.   
  
  
  
  7.  
    8.   
  
  
  
  8.         if (list == ImmutableList.Empty)  
    9.   
  
  
  
  9.         {  
    10.   
  
  
  
  10.             ...  
    11.   
  
  
  
  11.         }  
    12.   
  
  
  
  12.         else 
    13.   
  
  
  
  13.         {   
    14.   
  
  
  
  14.             ...  
    15.   
  
  
  
  15.         }  
    16.   
  
  
  
  16.     }  
    17.   
  
  
  
  17. }  
    18.

我們將QuickSort定義為ImmutableList的擴展方法，接受一個比較函數(shù)，最終則返回一個排序后的新的鏈表——因為ImmutableList是不可變的。

然后，我們再回到Haskell的代碼，我們可以看出，***行qsort函數(shù)由于接受了一個空鏈表，因此排序后的結果自然也是一個空鏈表。而第二行qsort則是一個較為標準的快速排序實現(xiàn)（快速排序的原理大致是：取一個元素作為pivot，先把那些比pivot小的元素放到pivot之前，再把比pivot大的放到pivot之后，然后對pivot的前后兩部分分別采取快速排序。遞歸至***，則整個鏈表排序完成）：

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

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

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

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

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

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

【編輯推薦】

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

分享文章：C#快速排序的趣味實現(xiàn)：從Haskell說起
鏈接地址：http://www.dlmjj.cn/article/djdehdc.html