C#中怎么實現快速排序

本篇文章為大家展示了C#中怎么實現快速排序，內容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。

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函數，還是++運算符，它們都會返回一個新的鏈表，而不會對原有鏈表作任何修改。這點是和我們傳統所做的“數組排序”相比有所不同的地方。

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

上述內容就是C#中怎么實現快速排序，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注億速云行業資訊頻道。