FCL源碼中數組類型的學習及排序函數Sort函數的分析

Array 是所有數組的基類
ArrayList 解決了所有Array 類的缺點    能動態擴容, 但是類型不安全的，而是會有裝箱與拆箱的性能開銷
List<T> 則是解決了ArrayList 類的裝箱，拆箱問題, 能夠動態擴容，但是所有的順序結構數據結構的缺點就是數據空間的開闢開銷
這三個類都是基於數組實現的, 並沒有用到鏈表的實現.
具體的源碼可以通過.NET Reflector 來看。對於內置函數Sort 我一直比較好奇，分析著它的實現應該是快排實現的，分析了下List<T> 的Sort 函數，先看看源碼:

代碼

 1 private static void IntroSort(T[] keys, int lo, int hi, int depthLimit, IComparer<T> comparer)
 2 {
 3     while (hi > lo)
 4     {
 5         int num = (hi - lo) + 1;
 6         if (num <= 0x10)
 7         {
 8             switch (num)
 9             {
10                 case 1:
11                     return;
12 
13                 case 2:
14                     ArraySortHelper<T>.SwapIfGreater(keys, comparer, lo, hi);
15                     return;
16 
17                 case 3:
18                     ArraySortHelper<T>.SwapIfGreater(keys, comparer, lo, hi - 1);
19                     ArraySortHelper<T>.SwapIfGreater(keys, comparer, lo, hi);
20                     ArraySortHelper<T>.SwapIfGreater(keys, comparer, hi - 1, hi);
21                     return;
22             }
23             ArraySortHelper<T>.InsertionSort(keys, lo, hi, comparer);
24             return;
25         }
26         if (depthLimit == 0)
27         {
28             ArraySortHelper<T>.Heapsort(keys, lo, hi, comparer);
29             return;
30         }
31         depthLimit--;
32         int num2 = ArraySortHelper<T>.PickPivotAndPartition(keys, lo, hi, comparer);
33         ArraySortHelper<T>.IntroSort(keys, num2 + 1, hi, depthLimit, comparer);
34         hi = num2 - 1;
35     }
36 }

FCL的數組類中 內置了專門用來處理排序的一個類 ArraySortHelper<T>。
數組類型的數據結構(不管是List, ArrayList, Array)其Sort 排序函數都是基於ArraySortHelper<T> Sort 函數來排序的。
該函數主要涉及到三種排序演算法: 快排, 插入排序, 堆排序, 內省排序
排序數字小於16個，直接使用插入排序
遞歸深度在32次之內(數字小於4GB)採用快排
大於4GB，則堆排序

看了下源碼，不得不佩服那些大神寫的框架源碼，那些最基本的數據結構和演算法在底層的應用這麼廣，起了這麼大的作用，是我們平常使用的函數的基礎。