FCL源码中数组类型的学习及排序函数Sort函数的分析_.NET_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > .NET > FCL源码中数组类型的学习及排序函数Sort函数的分析

FCL源码中数组类型的学习及排序函数Sort函数的分析

 2017/10/16 15:25:54  又见阿郎  程序员俱乐部  我要评论(0)
  • 摘要:Array是所有数组的基类ArrayList解决了所有Array类的缺点能动态扩容,但是类型不安全的,而是会有装箱与拆箱的性能开销List<T>则是解决了ArrayList类的装箱,拆箱问题,能够动态扩容,但是所有的顺序结构数据结构的缺点就是数据空间的开辟开销这三个类都是基于数组实现的,并没有用到链表的实现.具体的源码可以通过.NETReflector来看。对于内置函数Sort我一直比较好奇,分析着它的实现应该是快排实现的,分析了下List<T>的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,则堆排序

看了下源码,不得不佩服那些大神写的框架源码,那些最基本的数据结构和算法在底层的应用这么广,起了这么大的作用,是我们平常使用的函数的基础。

发表评论
用户名: 匿名