[演算法1-排序]（.NET源碼學習）& LINQ & Lambda

說起排序演算法，在日常實際開發中我們基本不在意這些事情，有API不用不是沒事找事嘛。但必要的基礎還是需要瞭解掌握。

排序的目的是為了讓無序的數據，變得“有序”。此處的有序指的是，滿足當前使用需求的順序，除了自帶的API，我們還可以自定義比較器對象、使用LINQ語句、Lambda表達式等方式完成排序。本文將逐一介紹十大排序，並著重介紹分析基於C#的LINQ常用語句和Lambda表達式，二者對排序的實現。

【# 請先閱讀註意事項】

【註：（1）以下提到的複雜度僅為演算法本身，不計入演算法之外的部分（如，待排序數組的空間占用）且時間複雜度為平均時間複雜度

　　　（2）除特殊標識外，測試環境與代碼均為.NET 6/C#

　　　（3）預設情況下，所有解釋與用例的目標數據均為升序

　　　（4）預設情況下，圖片與文字的關係：圖片下方，是該幅圖片的解釋

　　　（5）本文篇幅較長，和主標題（排序）契合度較低，建議分期閱讀；也可能存在較多錯誤，歡迎指出並提出意見，請見諒】

一. 十大排序

這十大排序對於有基礎的程式員並不陌生，只是一些經常不用的小細節可能記憶模糊，該部分內容會對排序方法簡要分析，旨在作為筆記，需要的時候幫助回憶相關內容。

(一) 冒泡排序（BubbleSort）

名字的起源十分生動形象：氣泡從水底向上浮，隨氣壓變化氣泡體積逐漸變大最終破裂；在某一時刻讓時間靜止，可觀察到從水面到水底，氣泡體積依次減小，體積排列有序，故得此名。

1. 原理：兩兩比較，按照比較器對象進行交換。

2. 複雜度：時間O(n²)    空間O(1)

3. 實現：(C++14 GCC 9)

（指針形式）

(二) 選擇排序（SelectSort）

1.  原理：選擇——選定一個數，確定當前該數的位置後，再選擇下一個數。註意其和冒泡排序的區別。

2.  複雜度：時間O(n²)    空間O(1)

3.  實現：（C++14 GCC 9）

二者區別在於：冒泡是相鄰的數比較；選擇是每次固定一個數與其他數比較。

(三) 插入排序（InsertSort）

其操作方式類似於我們再打牌時，抽出一些牌放入合適的位置。

1.     原理：選定一個數，將該數插入合適的位置。即，若排序結果為升序，則將數b插入某一位置，使得a < b < c。

2.     複雜度：時間O(n²)    空間O(1)

3.     實現：（C++14 GCC 9）

(四) 希爾排序（ShellSort）

此排序由希爾提出，是對插入排序的改進。改進的思想是：將一整個待排序序列分割為多個組，每一次對每個組的同一位置進行插入排序。即，將第一、二、三…組的第一個元素看為一個新的序列進行插排，第二個元素看為一個新的序列進行插排……以此類推。實驗證明，該思想在一定程度上有助於加快插入排序的運行。

1.     原理：分割式插排

2.     複雜度：時間O(n1.3)    空間O(1)

3.     實現：(C++14 GCC 9)

大量數據表明，當h /= 3時可達到最優效果。

(五) 快速排序（QuickSort）

快速排序是最常用的一個排序，在之前的介紹.NET數組源碼的排序方法（[數據結構-線性表1.1] 數組 （.NET源碼學習））中也出現過，雖然其內部有三種排序方式，但主體還是快速排序。之所以稱之為快速，是因為其時間複雜度不再是n²級，而是nlog₂n級。一般地，在1s的時間範圍內，總時間複雜級數需要小於等於10⁸，快速排序的出現，解決了許多大量數據排序的問題，提高了不少效率。

1.     原理：類二分法

2.     複雜度：時間O(nlog₂n)    空間O(log₂n)

3.     實現：（C++14 GCC 9）

快速排序只是使用數組原本的空間進行排序，所以所占用的空間應該是常量級的，但是由於每次劃分之後是遞歸調用，遞歸在運行的過程中會在棧上消耗一定的空間，在一般情況下的空間複雜度為O(logn)，在最差的情況下，若每次只完成了一個元素，那麼空間複雜度為O(n)。

[# Array.Sort()源碼再讀—有關快速排序]

這是該方法中的快速排序，和我們一般的快速排序不同，其運用了SwapIfGreater()方法、三數取中法對快速排序進行了優化。

• Line 197：此處的num為數組長度。

• l  Line 198：num >> 1 相當於 num / 2，一般地，可視為中間位置索引值。

• l  Line 199~201：SwapIfGreater()方法

根據傳入的比較器對象，對兩個元素進行相應處理。

在排序前，其先把索引為0和mid的兩個元素、索引為0的元素和最後一個元素、索引為mid的元素和最後一個元素進行處理，優先保證這三個位置上的元素符合要求。

該方法即為三數取中法。

1.     方法：是知道無序數列的首和尾，便可以求出其中間位置的數，此時只需在首、中、尾這三個數中，選擇中間的這個數作為基準值，進行快速排序，即可進一步提高快速排序的效率。

最初的快速排序是選擇第一個或最後一個元素為基準值，然後將整個序列分為兩部分。但當數組本身有序度較高或完全有序時，快排會達到O(n²)的時間複雜度，因為可能會導致分完後的兩部分中，某一部分為空集。即，相當於沒有二分就開始排序。

2.     優化原理：將首、中、尾排序後，選取中間位置的元素，能有效避免“一邊倒”的問題，從而真正利用上二分思想的加速性。

• Line 202：t 即為基準值。

• Line 203：交換中間位置和末尾的元素。使得這三個元素大小變成“峰谷”狀，由於基準值是三個元素中間大小的一個，這樣相當於保證分成的兩部分不出現空集。

該源碼和本人寫的代碼格式不同，本人運用遞歸的方法，將序列無限二分至無法再分，先左後右逐步有序；源碼利用迭代方法，三數取中 + 雙向搜索，從整體到局部。雖然平均複雜度均為log級，但長遠看來源碼具有較高的優越性。

• Line 206~218：從兩端開始，以中間位置為中心、基準值為判斷依據開始交換。

當最外層while迴圈結束後，i的左側一定全都是小於基準值的元素，num3的右側一定全都是大於基準值的元素。此時，相對於基準值而言，i的左側是有序的，num3的右側是有序的。

• Line 220~223：將i位置的元素與末尾元素交換。此時i位置的元素，是大於等於末尾元素的。交換後，從開頭到i位置的元素相對於剛纔而言，更加有序。

上圖是本人手寫的一份基本流程草圖，該快速排序有別於一般形式的快速排序，但整體思想依舊不變：類二分法，從子集有序到整體有序，加上兩種方法的優化，效率已經是很高的了。

(六) 歸併排序

歸併，即合併，既然要合併，那之前就得拆開。所以，歸併排序的方法就是先把元素二分，二分後每段再二分，直到無法二分。再根據比較器對象，按一定順序合二為一，逐層回調，最後完成排序。

1.     原理：類二分法

2.     複雜度：時間O(nlog₂n)    空間O(n)

3.     實現：（C++14 GCC 9）

快速排序是先排序，使得整個序列以基準值有序，再二分；歸併排序是直接二分到底，再逐層往回排序，從局部到整體。

(七) 堆排序

堆的結構類似於二叉樹，而二叉樹的相關操作（如，查詢、插入、刪除等）的時間複雜度一般都在常數級和log級，所以堆排序的效率也比較高。

1.     原理：根據數組索引和二叉樹位置的關係，構建大/小頂堆（二叉樹）並還原。

2.     複雜度：時間O(nlog₂n)    空間O(1)

3.     實現：（C++14 GCC 9）

一般地，目標為升序數組則構建大頂堆，目標為降序數組則構建小頂堆。

[# Array.Sort()源碼再讀—有關堆排序]

該源碼與一般的堆排序寫法如出一轍，上方的HeapSort()方法用於控制每次調整堆的範圍，保證有序元素不再被調整；下方的DownHeap()方法用於構建/調整堆，將合適的元素放到合適的位置。

• Line 231~234：第一次構建堆，構建大頂堆。即，讓每一個父結點的值大於等於子結點的值。

• Line 235~239：調整堆。每次調整後，根節點總是最大的，所以將根節點與最後一個非調整好的結點（從右下角開始往前）進行交換，交換後靠近末尾的部分元素已經是有序的了，所以下一次調整堆頂時，應將其排除在外，這就是參數中j – 1的由來。

• Line 243：參數：keys為待排序元素集；i為排序起始位置的索引（由於第一次構建堆頂時，保證了父結點的值大於等於子結點的值，所以交換後0索引處的值一定是較小的值，且該位置是一個動態存儲域，所以調整的其實索引可以從1開始，這就是傳入值為1的原因）；n為排序結束的索引；lo為應當進行交換的元素的索引（堆排序在建好堆後，一般從最後一個非葉子結點開始進行判斷。即，從最後一個分支，倒著往前進行。對於數組索引即為2 * 起始索引 + 1）；

之後的過程和本人以C++語言所寫的過程大體相似。

(八) 計數排序、桶排序

理論上這兩者排序的思想是類似的：新建數組，以索引代表元素，統計每個元素出現次數，最後再輸出。

1.     原理：按索引順序，以索引值代表數組值，統計出現次數。

2.     複雜度：時間O(n + k)    空間O(n + k)（其中，k為max – min）

3.     實現：（C++14 GCC 9）

當然，從標準出發，這二者肯定是不一樣的。

對於桶排序，將待排序元素劃分到不同的痛。先掃描一遍序列求出max和min ，設桶的個數為 k ，則把區間 [min, max] 均勻劃分成 k 個區間，每個區間就是一個桶，將序列中的元素分配到各自的桶。

對於計數排序，每個數值為一個桶。計數排序本質上是一種特殊的桶排序，當桶排序的桶的個數最大的時候，就是計數排序。

(九) 基數排序

1.     原理：按照元素的每一位進行比較來排序。

2.     複雜度：時間O(n * k)    空間O(n + k) （其中，k為max – min）

3.     實現：（C++）來自（1.10 基數排序 | 菜鳥教程 (runoob.com)）

小結一

基數排序與計數排序、桶排序這三種排序演算法都利用了桶的概念，但對桶的使用上有一定差異：

（1）桶排序：每個桶存儲一定範圍的數值；

（2）計數排序：每個桶只存儲單一鍵值；

（3）基數排序：根據鍵值的每位數字來分配桶；

基數排序不是直接根據元素整體的大小進行元素比較，而是將原始列表元素分成多個部分，對每一部分按一定的規則進行排序，進而形成最終的有序列表。

LINQ語句及常用方法

LINQ（Language-Integrated Query）語言集成查詢，常用於對數據的查詢。一般地，完整的查詢操作包括創建數據源、定義查詢表達式和在foreach語句中執行查詢。

該部分將分析相關方法的源碼，以及內部的orerby與orderbyDescending排序方法。本人會儘可能的講述清楚過程的細節，但之前也沒有詳細讀過源碼，該文章也是邊讀邊學邊寫，可能存在解讀錯誤，也可能會有與讀者相矛盾的觀點，還望各位指出，請諒解。

(一) All()方法

確定序列的所有元素是否都滿足條件。

• Line 10：LINQ方法中的參數並不像一般方法中的參數一樣，各個對應。

• Line 12~15：檢查源數據是否為空，防止訪問沒有分配引用地址的對象。

• Line 16~19：檢查過濾器對象是否為空。

• Line 20~27：對每個元素根據傳入的委托表達式進行判斷。

對於這兩個參數，可以發現：

(一) 不管是在源碼還是在從元數據中，該方法均有兩個參數。但在使用時，卻只需要傳入一個參數。

(二) TSource和泛型T不是一個東西，泛型T可以容納所有類型，但需要手動指定數據類型；TSource可以容納所有類型，但可自動識別類型。

當要訪問的元素集是什麼類型時，TSource會自動分配對應的類型。

(三) 待傳入的參數Func<TSource, bool> predicate是一個方法（稱為此處過濾器），將方法作為參數，無疑用到了委托。

關鍵字in和out一般用在泛型interface和delegate中, 用來進行逆變和協變（in逆變，out協變）。（協變、逆變將在下方介紹）

Func()方法是一個有返回值的泛型委托，可包含0~16個參數T，併在最後多加一個參數，表示返回值類型。我們也可以自己定義該方法，如：

根據我們自己寫的調用的操作步驟，可以發現，我們只需傳入待處理參數，不用管最後的返回參數。

其基本語法格式為：方法名（臨時變數 => 條件表達式）。其中，括弧中的式子稱為Lambda表達式，會在後文介紹。

(二) Any()方法

判斷是否包含任何元素、是否存在元素滿足指定的條件。

（1）首先是判斷源數據是否包含任何元素。

• Line 15~29：嘗試將source轉換為集合（介面）類型，若轉換成功，即序列可以作為ICllection<>的實例，則通過返回Count屬性，判斷其是否包含任何的元素。

• Line 20~35：嘗試將source轉換為IListProvider（介面）類型，若轉換成功，則調用GetCount()方法，預設傳入true，進行判斷；而否則嘗試轉換為集合類型。

• Line 37~42：提取source的迭代器對象，判斷其是否存在下一個元素，如果枚舉數已成功地推進到下一個元素，返回true；如果枚舉數傳遞到集合的末尾，返回false。

對於IListProvider，其內部包含了三個方法：轉換為數組、轉換為泛型集合、GetCount()方法。

其中，前兩個方法的實現均是將元素放入到新的數據結構中，最後返回。內部的欄位_source[]指的是源數據及，_predicate()方法指的是傳入的條件表達式；LargeArrayBuilder可以近似看作StringBuilder。

對於GetCount()方法，其原理也是通過遍歷源數據集，在滿足相應條件的情況下記錄元素個數。

（2）判斷源數據是否包含任意一個符合條件的元素

通過遍歷的方式逐一檢查，存在一個滿足條件就返回true，一個都不滿足就返回false；

(三) 基本計算--Count()、Max()、Min()、Sum()方法

（1）Count()方法

其包含兩個重載形式：一個是純計數，另一個是帶條件計數（記錄滿足條件的元素個數）。

可以發現，其原理和Any()方法中的GetCount()方法基本類似。

（2）Max()、Min()、Sum()方法

這三種方法，前兩種每種包含21個重載函數，Sum()方法包含19個重載函數，因為需要針對不同的數據類型。但最大不同依舊在於是否帶有條件。

其實現原理基本類似，且沒有什麼新的東西，所以在此不做過多論述。

(四) Where的實現

Where子句用在查詢表達式中，用於指定將在查詢表達式中返回數據源中的哪些元素。它將一個布爾條件應用於每個源元素（由範圍變數引用），並返回滿足指定條件的元素。一個查詢表達式可以包含多個Where子句，一個子句可以包含多個條件表達式。簡而言之，Where起到一個篩選器的作用，篩選出符合條件的元素。

並且可以發現，篩選出的元素預設情況下共同構成一個可枚舉的集合。

Where方法的過濾功能主要通過迭代器實現，其源代碼包含7個迭代器。按照功能劃分如下：

（1）索引參與過濾操作運算的迭代器WhereIterator，容器（可迭代對象）包含Enmuerable，List和Array。

（2）索引不參與過濾運算

　　1. Enmuerable：WhereEnumerableIterator和WhereSelectEnumerableIterator

　　2. List：WhereListIterator和WhereSelectListIterator

　　3. Array：WhereArrayIterator和WhereSelectArrayIterator

其中Enmuerable迭代器，List迭代器和Array迭代器在實現上相差不大，都是通過設計模式中的迭代器模式實現具體的功能。區別是Enmuerable迭代器，List迭代器都是調用容器自身的迭代器實現逐個元素的比較和過濾，而Array迭代器是通過數組索引操作實現元素比較和過濾。

除了WhereIterator，其餘六個迭代器均派生自迭代器類Iterator

[# 有關Iterator的源碼]

• Line 12：在構造函數內獲取當前線程的Id。

• Line 21：Current屬性包含一個get訪問器（只讀），返回當前對象。

•  Line 26：該類繼承了介面IEnumerable，所以必須實現GetEnumerator()方法。如果當前迭代器的線程Id和當前線程的Id不同，則克隆一個新的迭代器返回，否則返回當前迭代器。

• Line 29：該類繼承了介面IDisposable，所以必須實現Dispose()方法。必要情況下釋放對象。

• Line 36~40：因為需要進行篩選（迭代器遍歷）工作，所以需要定義迭代器，並將其初始狀態設置為1，返回當前迭代器。

• Line 44：該方法MoveNext()來自於所繼承的介面IEnumerator，其根據不同的容器，有不同的實現（就像剛纔提到的List和Array的迭代方式），所以定義為抽象方法。

• Line 47~50：虛方法Select()，預設返回WhereEnumerableIterator迭代器。

• Line 53~56：虛方法Where()，預設返回WhereSelectEnumerableIterator迭代器。

這兩個迭代器均不參與過濾運算，兩個虛方法主要用於具體容器的復用或重寫。如果調用Where的迭代器，屬於剛纔提到的不參與過濾運算的六個迭代器對象，則會覆蓋父類中的某些方法；如果是其它迭代器，例如Distinct迭代器，則會調用父類的Where和Select方法。

Where擴展方法（一）

• Line 12~19：檢查數據源和過濾器是否為空。

• Line 20：嘗試將source轉換為迭代器對象，會產生兩種情況：

（1）如果是Where相關的迭代器，如調用形式為XX.Where().Where()。此處iterator.Where(predicate)的Iterator是Where相關的迭代器對象(WhereListIterator、WhereArrayIterator)，此時調用的Where方法是派生類WhereXXXIterator重寫後的Where方法，返回的是WhereXXXIterator對象，XXX表示List或Array或Enumerable。

（2）如果是其他迭代器，如調用形式為XX.Distinct().Where()，此處iterator.Where(predicate)的Iterator是Distinct的迭代器對象，此時調用的Where方法是父類Iterator種的Where方法，返回的是預設的WhereEnumerableIterator對象。

• Line 25~33：嘗試將source轉換為數組類型。若轉換成功且長度不為0，則返回WhereArrayIterator實例。

• Line 34~41：嘗試將source轉換為List類型。若轉換成功且長度不為0，則返回WhereListIterator實例。

• 若兩種類型均無法轉換，則返回預設實例WhereEnumerableIterator。

Where擴展方法（二）

該方法為帶索引參數的擴展方法，其沒有對線程對資源的占用情況進行檢查，而是直接調用了WhereIterator方法

WhereIterator方法中維護了一個計數器，每迴圈一次，計數器加1，計數器中如果出現整型數字溢出情況，則拋出異常。yield return將結果以值的形式返回給枚舉器對象，可一次返回一個元素；yield break將控制權無條件地交給迭代器的調用方，該調用方為枚舉器對象的IEnumerator.MoveNext方法（或其對應的泛型System.Collections.Generic.IEnumerable<T>）或Dispose方法。

[# 有關迭代器WhereEnumerableIterator的源碼]

其包含三個欄位：源數據、過濾器、迭代器對象。

GetCount()方法在上文提到過，用於計算源數據集中，符合條件的元素個數，預設傳入true。

包含兩個類型轉換方法，分別轉換為數組類型和泛型集合類型。轉換原理均是通過建立相應對象，並寫入數據完成。

一個構造方法，初始化源數據集和過濾器對象。

繼承的類與介面。

由於其繼承了許多介面和類，所以此處重寫了介面中的方法，包括創建並返回新的（克隆）迭代器對象、釋放對象、向後移動到下一個元素。

• Line 85：變數 _state 位於類Enumerable中的Iterator類型中，初始值為1，用於表示當前狀態，指示出下一步應當怎麼做。

重寫了IEnumerable<TSource>介面中的Select()和Where()方法，用於當調用Where的迭代器不屬於六大類型時，調用上一級的方法。

【Select()方法和Where()方法原理類似，在此不作敘述】

（五）排序

將了這麼多題外話，終於拉回了主題。Linq中也有用於排序的方法，包括OrderBy、OrderByDescending、ThenBy、ThenByDescending，在一個語句中，以OrderBy型開頭，之後的只能用ThenBy型，但ThenBy型可多次使用。一般地，O/T型共同存在的排序多用於多關鍵字排序。

基礎語法如下：

[# 有關OrderBy的源碼]

OrderBy()方法有兩個重載方法，均返回一個OrderedEnumerable類型的對象。

其內置的排序方法，位於類EnumerableSorter<TElement, TKey>中，分別為PartialQuickSort()和QuickSort()。

在排序前，

（1）   對於QuickSort()方法

其重寫了父類EnumerableSorter<TElement>中的同名抽象方法，並調用類ArraySortHelper<T>中的IntrospectiveSort()方法，這與前一篇文章中提到的數組排序方法Array.Sort()，方法一致。

（2）   對於PartialQuickSort()方法

該方法直接定義在類EnumerableSorter<TElement, TKey>中，針對源數據集的某一部分進行排序。

• Line 3：map為待排序數組；letf與right為邊界指針（此處的指針有別於C/C++中的指針，此處僅代表一個標記）；minIdx與maxIdx為排序區域。

• Line 12~19：當left小於length（未越界）時，CompareKeys()方法用於返回兩元素的大小關係：相等返回0，左大右小返回1，反之返回-1。

從左往右，找到第一個大於等於中間位置的元素。

其方法內部的四個紫色欄位均在類EnumerableSorter中

【註：下方有關五個參數的解釋為推斷得出】

_keySelector表示委托方法Func()，過濾器；_compare表示比較器對象；_descending表示是否降序；_next下一個迭代排序器對象；_keys表示經過濾器篩選出的待排序數據集；

• Line 20~23：從右往左，找到第一個小於等於中間位置的元素。

• Line 24~37：如果left與right沒有彼此越過對方，則交換位置，並開始下一次查找。

此時，內層迴圈結束，完成了以中間位置元素為基準值的排序，保證基準值左側小、右側大。

• Line 38~45：若此時兩指針並未在需求的排序區域內，則相對應方向移動。

• Line 46~61：當內層迴圈結束時兩指針的大小關係為num = num2 + 1，所以Line 46在判斷被兩指針分割的兩部分，哪一部分更短，優選處理短的一部分。

整個排序過程以遞歸的方式進行，類似於快速排序。

【註：以下內容屬於推斷得出】

數據集在調用OrderBy()等一類排序方法後，會先將源數據轉換為泛型Buffer類型

之後，再調用類OrderedEnumerable中的SortedMap()方法

在調用真正開始排序前，首先調用ComputeMap()方法，根據過濾器，篩選出要排序的元素，並保存在_keys中。再根據不同的參數，調用不同的方法進行排序。

以上為OrderBy一類排序方法的“前搖”和過程，其餘的OrderByDescenidng()、ThenBy()、ThenByDescending()方法與OrderBy()類似。

流程圖如下：

小結二

綜合來看，就對於OrderBy一類排序演算法本身，其時間複雜度和Array中的Sort()方法相差不大，但實際運行效果卻要比Array.Sort()方法慢。原因應該在於其需要頻繁創建EnumerableSorter對象、將數據類型轉換為Buffer再轉換為數組、排序後從IOrderByEnumerable類型轉換為源數據類型，這些過程大大延長了總時間，尤其是在數據量較大的時候，所需時間將會產生較大差異。

三．有關Lambda表達式

Lambda表達式用來創建匿名函數，常用於委托、回調，且可以訪問到外部變數。使用Lambda運算符“=>”，從其主體中分離 lambda 參數列表，可採用以下任意一種形式：

一般地，輸入的參數不需要顯示指定類型。但當編譯器無法判斷其類型時，可顯示指明各個參數的類型：

(一) 有關匿名

（1）匿名類型

該類型可用來將一組只讀屬性封裝到單個對象中，而無需顯式定義一個類型。類型由編譯器在編譯階段生成，並且不能在源代碼級使用。可結合使用new運算符和對象初始值設定項創建匿名類型。

其中，這裡的var被定義為匿名類型（AnonymousType），v被定義為類型 `a 。

在反編譯程式中，查詢到20中相關的方法

根據IL DASM工具可以發現，其包含的主要信息：類<>f__AnonymousType0`2<’<參數para>j__TPar’,’<Message>j__TPar’>；私有隻讀欄位<Amount>i__Field和<Message>i__Field；三個非靜態重寫方法Equals()、GetHashCode()、ToString()。

以此為例，在源碼中找到相關信息，其位於程式集PresentationFramwork.dll中

• Line 8：內部密封類，類名為<>f__AnonymousType0；泛型類型為<ControlsUsedInApp>j__TPar。

• Line 12~17：定義參數變數的屬性—get（只讀）。

• Line 21~25：構造函數，將傳入的參數賦值給類的內部變數。

• Line 29~33：Equals()方法，嘗試將傳入的Object類型對象轉換為與被比較對象相同的匿名類型，並按照預設比較其和基本原則，按順序逐一比較內部參數。

• Line 37~40：返回當前對象的哈希代碼。哈希碼為每個變數/對象的唯一標識符，用於在一定情況下相互區別。

• Line 44~53：將匿名類型的整個部分轉化為字元串的形式（大括弧居然也算！？）。

（2）匿名方法

委托是用於引用與其具有相同標簽的方法。即，可以使用委托對象調用可由委托引用的方法。匿名方法提供了一種傳遞代碼塊作為委托參數的技術，其沒有名稱只有方法體；沒有返回值類型，類型根據具體方法中的return語句推斷。如，Func()方法、Action()方法、Predicate()方法。

所以在OrderBy一類排序中，其內部需要傳入一個匿名方法，以賦值給Func()方法，故使用Lambda表達式。

(二) Lambda 表達式的自然類型

Lambda表達式本身沒有類型，因為CLS（通用類型系統）沒有“Lambda 表達式”這一固有概念。不過，有時以非正式的方式談論 Lambda 表達式的“類型”會很方便。該非正式“類型”是指委托類型或 Lambda 表達式所轉換到的Expression類型。

從C# 10開始，Lambda表達式可能具有自然類型。編譯器不會強製為 Lambda 表達式聲明委托類型（如Func<>或Action<>），而是根據 Lambda 表達式推斷委托類型。

也就是說，一開始的Lambda表達式只能賦值給委托類型。而在此之後，Lambda表達式可以根據具體的情況，賦值給具體的類型。

【註：更多Lambda表達式內容請參閱Lambda 表達式 - C# 引用 | Microsoft Docs】

[# 有關泛型的協變與逆變]

據官方解釋，協變指能夠使用比原始指定的派生類型的派生程度更大（更具體的）的類型；逆變指能夠使用比原始指定的派生類型的派生程度更小（不太具體的）的類型。

在談論協變與逆變之前先來看一下泛型集合中的對象轉換。

此處有三個類。其中Student與Worker派生自Person，那麼可以將Person稱為Student和Worker的上層數據類型；Student和Worker稱為Person的下層類型。

可以發現，雖然Person時Student和Worker的父類，但List<Person>不是List<Student>和List<Worker>的父類，所以後兩行的賦值會報錯。

在C# 4之前，類似於上述的賦值操作是不被允許的。因為假設其能夠賦值，即List<Person> p = new List<Student>();成立，那麼雖然p的類型為List<Person>但其實例對象使List<Student>，在調用方法時，調用的也就是Student的方法。如果現在實現這個語句：p.Add(new Person());其實質上是用Student中的Add方法，而Student又是Person的子類，Person無法安全（直接）轉換為Studnt對象，所以這樣的集合定義沒有意義，因此不被允許。

從C# 4開始，類似的操作，在泛型委托、泛型介面中，允許發生。但上述操作依舊是無法實現的，因為其違反類型類型轉換的基本流程。

定義一個無參泛型委托。

• 協變：

我們嘗試在上層類型中存放下層類型。不出意外，依舊報錯。根據剛纔的分析，要想解決這個錯誤，需要解決兩個問題：

（1）   在調用p()方法時，實際上調用的是s()方法，所以需要s執行的結果能轉換為p執行後所返回的類型。即，s能夠轉換為p類型。

（2）   解除編譯器的檢查限制，在此處允許將Work<Student>類型的對象賦值給Work<Person>類型的變數。

對於（1）已經滿足，由隱式轉換直接完成；而條件（2）就需要在委托中加上out關鍵字。

• 逆變

嘗試在上層類型中存放下層類型。解決這個錯誤，也需要解決兩個問題：

（1）在調用s()方法時，實際上調用的是p()方法，即，p能夠轉換為s類型。

（2）解除編譯器的檢查限制，在此處允許將Work<Person>類型的對象賦值給Work<Student>類型的變數。

對於（1）因為Student為Person的子類，所以二者存在聯繫，通過強制類型轉換可以實現；而條件（2）需要在委托中加上in關鍵字。

【註：如果沒有子父類的關係，加上in/out關鍵字，也無法實現】

簡而言之：協變可以在上層數據類型中存放下層對象；逆變可以在下層的數據類型中存放上層對象（這裡的上層與下層是相對而言），這兩個過程本質上是參數的類型轉換。

據微軟官方的說法，協變於逆變只發生在數組、委托、泛型參數之上，對於類的上下轉型而言不算做協變於逆變。

TRANSLATE with