0908学习 agile Posted on Sep 8 2023 面试 unity基础 ##虚方法调用 --- - 现在面向对象的封装、继承、多态中的`多态`实现主要就是靠`虚方法` - 一个类型可能会有子类，子类可能会重写类型的方法从而达到不同的行为(多态)，而这些`重写的方法`都在`虚方法表`里，`调用`的话就需要`查表`。 - 编译器在编译的时候为每一个含有`虚函数的类`分配一个`虚函数表`，生成对象的时候为`每一个对象`分配一个`虚表指针`，指向本类的`虚函数表`。在程序`运行`期间，当用`派生类的对象`给`基类`引用`赋值`时，就会用`派生类的虚表指针`覆盖`基类的虚表指针`，因此在用`基类指针`调用该方法的时候总能正确的`指向派生类所重写的方法` - `基类`构造函数的执行要`早`于`子类`构造函数 - `基类`构造函数中对于`虚方法`的`调用`，实际调用的是`子类中重写的虚方法` - `隐藏数据成员`：在派生类中声名名称和类型相同的成员，`不需要new关键字` - `隐藏函数成员`：在派生类中声名新的带有相同函数签名的成员（函数名和函数参数相同即可，对返回值类型无要求），在`声名前面加上new关键字` - `sealed`应用于方法后，`不影响当前类的继承关`系。它能够防止当前这个已经重写的方法被其子类去重写替换，也就是说`sealed必须是与override搭配使用`，对应虚方法或抽象方法。 ```C# class A { public virtual void Fun1() { Debug.Log("A:Fun1"); } public void Fun2() { Debug.Log("A:Fun2"); } public virtual void Fun3() { Debug.Log("A:Fun3"); } } class B : A { public sealed override void Fun1() { Debug.Log("B:Fun1"); } public new void Fun2() { Debug.Log("B:Fun2"); } public override void Fun3() { Debug.Log("B:Fun3"); } } class C : B { public new virtual void Fun3() { Debug.Log("C:Fun3"); } } class D : C { public override void Fun3() { Debug.Log("D:Fun3"); } } A a = new B(); //B:Fun1 a.Fun1(); //A:Fun2 a.Fun2(); // B:Fun3 a.Fun3(); a = new C(); // B:Fun1 a.Fun1(); // A:Fun2 a.Fun2(); //B:Fun3 a.Fun3(); B b = new C(); //B:Fun1 b.Fun1(); //B:Fun2 b.Fun2(); //B:Fun3 b.Fun3(); A ad = new D(); //B:Fun3 ad.Fun3(); var cd = (C)ad; //D:Fun3 cd.Fun3(); ``` --- ###子类与父类虚方法的调用规则 --- - 当调用一个对象的函数时，系统会直接去检查这个对象声明的类，看所调用的函数是否为虚函数； - 如果不是虚函数，那么它就直接执行该函数。如果是虚函数，首先到派生类中查找是否有覆盖，如果有就使用派生类的。 - 如果派生类中有这个方法，但`override`替换成`new`,那么继承链也是段的。 --- ## [](#hash算法与hash函数)Hash 算法与 Hash 函数 --- - `Hash算法`是一种数字摘要算法，它能将`不定长度`的二进制数据集给映射到一个`较短`的二进制长度数据集。常见的 MD5 算法就是一种Hash算法，通过 MD5 算法可对任何数据生成数字摘要。而`实现`了 Hash 算法的函数我们叫它`Hash函数`。Hash 函数有以下几点特征。 - `相同的数据`进行Hash运算，得到的结果一定相同。 - `不同的数据`进行Hash运算，其结果也可能会相同。 - Hash 运算是`不可逆`的，不能由key获取`原始的数据`。 --- #### [](#常见的hash算法)常见的 Hash 算法 --- - `直接寻址法`：取`keyword`或`keyword 的某个线性函数值为散列地址`。即 `H(key)=key` 或 `H(key) = a•key + b`，当中 `a` 和 `b` 为常数（这样的散列函数叫做自身函数） - `平方取中法`：取`keyword`平方后的`中间几位`作为散列地址。 - `折叠法`：将`keyword`切割成`位数同样`的`几部分`，最后`一部分位数能够不同`，然后取这几部分的`叠加和`（去除进位）作为散列地址。 - `随机数法`：选择一随机函数，取`keyword`的`随机值`作为散列地址，通常使用于`keyword长度不同`的场合。 - `除留余数法`：取`keyword`被某个不大于散列表表长`m`的数`p`除后所得的余数为散列地址。即 `H(key) = key MOD p, p<=m`。不仅能够对`keyword` 直接取模，也可在折叠、平方取中等运算之后取模。对`p` 的选择非常重要，一般取`素数或 m`，若`p` 选的不好，`容易产生碰撞` --- #### [](#hash桶算法)Hash 桶算法 --- `Hash桶算法`主要是用来`归类Hash值`的，一般用来`配合其他算法`计算最终 Hash，而`不是单独`用的，不然 Hash 碰撞会非常频繁。（其实就是除留余数法的最简化版。） --- ### [](#hash碰撞)Hash 碰撞 --- 上面的 Hash 函数特征介绍中有一条：`不同的数据进行Hash运算，其结果也可能会相同。`。这就是 Hash 碰撞，即`不同的数据经过Hash函数处理后得到了相同的输出`。这并不是我们所期望看到的，所以为了解决 Hash 碰撞，又产生了很多解决 Hash 碰撞的方法。 --- #### [](#常见解决hash碰撞的方法)常见解决 Hash 碰撞的方法 - `拉链法`：这种方法的思路是将产生冲突的元素建立一个`单链表`，并将`头指针地址`存储至`Hash 表`对应`桶`的位置。这样定位到`Hash表桶`的位置后可通过`遍历单链表`的形式来查找元素。其实这种方法还是有瑕疵的，例如`如果字典内所有键都在一个桶的链表里，那么查找起来时间复杂度还是 O(n)`。在 Java 的 HashMap(对位 C# 的字典) 中，当`单链表的长度大于 8` 时，会把它变成`红黑树`，优化增删改查效率。`但是在.Net Framework 8里面暂时还没有哦`。 - `再Hash法`：顾名思义就是将`key`使用其它的 Hash 函数再次 Hash，直到找到不冲突的位置为止。 - `开放定址法` - `公共溢出分区法` --- ##List --- - List使用数组形式作为底层数据结构，`好处`是使用索引方式提`取元素很快`，但在`扩容`的时候就会很糟糕，每次new数组都会造成内存垃圾，这给垃圾回收GC带来了很多负担 - 每次容量不够的时候，整个数组的容量都会扩充一倍，`_defaultCapacity`是容量的默认值为4。因此整个扩充的路线为4，8，16，32，64，128，256，512，1024…依次类推。。。 ```C# int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2; ``` - 性能的角度来说，在使用集合类型时指定初始容量,在2的次方中找一个合适的就可以了。 - 对List调用foreach的时候，会执行List的 GetEnumerator方法得到新的迭代器。然后会`进行版本号对比`，一旦在遍历过程中对List做了`增删操作`，版本号就会变化，从而与迭代器的版本号不一致，我们也就会看到`报错异常`。所以不能在遍历过程中对 List 进行增删操作。会这样设计是有原因的，因为一旦允许在遍历过程中进行增删操作，遍历就不再是遍历了，要么会重复，要么会缺漏，再严重点就直接空指针了 ```C# public struct Enumerator : IEnumerator<T>, System.Collections.IEnumerator { internal Enumerator(List<T> list) { _list = list; _index = 0; _version = list._version; _current = default; } public bool MoveNext() { List<T> localList = _list; if (_version == localList._version && ((uint)_index < (uint)localList._size)) { _current = localList._items[_index]; _index++; return true; } return MoveNextRare(); } private bool MoveNextRare() { if (_version != _list._version) { ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); } _index = _list._size + 1; _current = default; return false; } ... } ``` --- ##Dictionary 实现 --- ### 1. Entry 结构体[](#1-entry结构体) --- - `Entry`是Dictionary种存放数据的最小单位，调用`Add(Key,Value)`方法添加的元素都会被封装在这样的一个结构体中 --- ```C# private struct Entry { public int hashCode; // 除符号位以外的31位hashCode值, 如果该Entry没有被使用，那么为-1 public int next; // 下一个元素的下标索引，如果没有下一个就为-1 public TKey key; // 存放元素的键 public TValue value; // 存放元素的值 } ``` --- ###其它关键私有变量[#](#2-其它关键私有变量) --- ```C# private int[] buckets; // Hash桶 private Entry[] entries; // Entry数组，存放元素 private int count; // 当前entries的index位置 private int version; // 当前版本，防止迭代过程中集合被更改 private int freeList; // 被删除Entry在entries中的下标index，这个位置是空闲的 private int freeCount; // 有多少个被删除的Entry，有多少个空闲的位置 private IEqualityComparer<TKey> comparer; // 比较器 private KeyCollection keys; // 存放Key的集合 private ValueCollection values; // 存放Value的集合 ``` --- ###增加元素 --- - 当`Hash`桶内发生碰撞时，会变成`单链表`。当 `entries`数组满的时候，字典会进行扩容，也就是数组拷贝，最好`提前`设定好字典容量，避免频繁的字典扩容。`Hash碰撞次数(100)到达一个阈值，也会触发扩容操作` --- ```C# private void Insert(TKey key, TValue value, bool add){ if( key == null ) { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); } if (buckets == null) Initialize(0); // 通过key获取hashCode int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; // 计算出目标bucket下标 int targetBucket = hashCode % buckets.Length; // 碰撞次数 int collisionCount = 0; for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) { if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) { // 如果是增加操作，遍历到了相同的元素，那么抛出异常 if (add) { ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate); } // 如果不是增加操作，那可能是索引赋值操作 dictionary["foo"] = "foo" // 那么赋值后版本++，退出 entries[i].value = value; version++; return; } // 每遍历一个元素，都是一次碰撞 collisionCount++; } int index; // 如果有被删除的元素，那么将元素放到被删除元素的空闲位置 if (freeCount > 0) { //在移除的时候被赋值 index = freeList; freeList = entries[index].next; freeCount--; } else { // 如果当前entries已满，那么触发扩容 if (count == entries.Length) { Resize(); targetBucket = hashCode % buckets.Length; } index = count; count++; } // 给entry赋值 //拉链法，桶里装的是最新的index entries[index].hashCode = hashCode; entries[index].next = buckets[targetBucket]; entries[index].key = key; entries[index].value = value; buckets[targetBucket] = index; // 版本号++ version++; // 如果碰撞次数大于设置的最大碰撞次数，那么触发Hash碰撞扩容 if(collisionCount > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(comparer)) { comparer = (IEqualityComparer<TKey>) HashHelpers.GetRandomizedEqualityComparer(comparer); Resize(entries.Length, true); } } ``` --- - 因为`count`是通过自增的方式来指向`entries[]`下一个空闲的`entry`，如果有元素被删除了，那么在`count`之前的位置就会出现一个空闲的`entry`；如果不处理，会有很多空间被浪费 - **Remove**操作会记录`freeList、freeCount`，就是为了将删除的空间利用起来。实际上**Add**操作会优先使用`freeList`的空闲`entry`位置 --- ###删除操作 --- - 删除也是需要找到元素的位置，然后再进行删除的操作。 --- ```C# public bool Remove(TKey key) { if(key == null) { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); } if (buckets != null) { // 1. 通过key获取hashCode int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; // 2. 取余获取bucket位置 int bucket = hashCode % buckets.Length; // last用于确定是否当前bucket的单链表中最后一个元素 int last = -1; // 3. 遍历bucket对应的单链表 for (int i = buckets[bucket]; i >= 0; last = i, i = entries[i].next) { if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) { // 4. 找到元素后，如果last< 0，代表当前是bucket中最后一个元素，那么直接让bucket内下标赋值为 entries[i].next即可 if (last < 0) { buckets[bucket] = entries[i].next; } else { // 4.1 last不小于0，代表当前元素处于bucket单链表中间位置，需要将该元素的头结点和尾节点相连起来,防止链表中断 entries[last].next = entries[i].next; } // 5. 将Entry结构体内数据初始化 entries[i].hashCode = -1; // 5.1 建立freeList单链表 entries[i].next = freeList; entries[i].key = default(TKey); entries[i].value = default(TValue); // *6. 关键的代码，freeList等于当前的entry位置，下一次Add元素会优先Add到该位置 freeList = i; freeCount++; // 7. 版本号+1 version++; return true; } } } return false; } ``` --- ###查找 --- - 假设我们现在执行这样一条语句`dictionary.GetValueOrDefault("a")`，会执行以下步骤.: - 获取key的hashCode，计算出所在的桶位置。我们之前提到，"a" 的`hashCode=6`，所以最后计算出来`targetBucket=2` - 通过`buckets[2]=1`找到`entries[1]`,比较key的值是否相等，相等就返回`entryIndex`，不想等就继续`entries[next]`查找，直到找到key相等元素或者`next==-1`的时候。这里我们找到了`key=="a"`的元素，返回`entryIndex=0` - 如果`entryIndex>=0`那么返回对应的`entries[entryIndex]`元素，否则返回`default(TValue)`。这里我们直接返回`entries[0].value` --- ```C# // 寻找Entry元素的位置 private int FindEntry(TKey key) { if( key == null) { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); } if (buckets != null) { int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; // 获取HashCode，忽略符号位 // int i = buckets[hashCode % buckets.Length] 找到对应桶，然后获取entry在entries中位置 // i >= 0; i = entries[i].next 遍历单链表 for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) { // 找到就返回了 if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i; } } return -1; } ... internal TValue GetValueOrDefault(TKey key) { int i = FindEntry(key); // 大于等于0代表找到了元素位置，直接返回value // 否则返回该类型的默认值 if (i >= 0) { return entries[i].value; } return default(TValue); } ``` --- ###Resize操作(扩容) --- ####扩容操作的触发条件 - 数组已经满了，没有办法继续存放新的元素 - Dictionary中发生的碰撞次数太多，会严重影响性能，也会触发扩容操作(碰撞次数阈值为100) --- ####扩容操作如何进行 - 申请两倍于现在大小的buckets、entries - 将现有的元素拷贝到新的entries - 如果是Hash碰撞扩容，使用新HashCode函数重新计算Hash值 - 对entries每个元素`bucket = newEntries[i].hashCode % newSize`确定新buckets位置 - 重建hash链，`newEntries[i].next=buckets[bucket]; buckets[bucket]=i; ` --- - HashMap如果碰撞的次数太多了，那么会将`单链表`转换为`红黑树`提升查找性能。目前.Net Framwork中还没有这样的优化，.Net Core中已经有了类似的优化 - 每次扩容操作都需要遍历所有元素，会影响性能。所以创建Dictionary实例时`最好设置一个预估的初始大小`。 --- ```C# private void Resize(int newSize, bool forceNewHashCodes) { Contract.Assert(newSize >= entries.Length); // 1. 申请新的Buckets和entries int[] newBuckets = new int[newSize]; for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1; Entry[] newEntries = new Entry[newSize]; // 2. 将entries内元素拷贝到新的entries总 Array.Copy(entries, 0, newEntries, 0, count); // 3. 如果是Hash碰撞扩容，使用新HashCode函数重新计算Hash值 if(forceNewHashCodes) { for (int i = 0; i < count; i++) { if(newEntries[i].hashCode != -1) { newEntries[i].hashCode = (comparer.GetHashCode(newEntries[i].key) & 0x7FFFFFFF); } } } // 4. 确定新的bucket位置 // 5. 重建Hahs单链表 for (int i = 0; i < count; i++) { if (newEntries[i].hashCode >= 0) { int bucket = newEntries[i].hashCode % newSize; newEntries[i].next = newBuckets[bucket]; newBuckets[bucket] = i; } } buckets = newBuckets; entries = newEntries; } ``` --- ###Collection 版本控制 - `version`这个变量，在每一次新增、修改和删除操作时，都会使`version++`； - 通过`foreach`遍历该实例，在`foreach`代码块中使用`dic.Remove(kv.Key)`删除元素,就会抛出了`System.InvalidOperationException:"Collection was modified..."`这样的异常，原因就是版本号不一致，就会抛出异常 --- ##HashSet --- - HashSet是一个无序的能够保持唯一性的集合。我们可以将HashSet看作是简化的`Dictionary<TKey,TValue>`，只不过`Dictionary<TKey,TValue>`存储的键值对对象，而HashSet存储的是普通对象。其内部实现也和`Dictionary<TKey,TValue>`基本一致，用到了`Hash桶`和`单链表`。区别是存储的`Entry`没有`key` --- ##SortedDictionary --- - `SortedDictionary<TKey,TValue>`和`Dictionary<TKey,TValue>`类似。`SortedDictionary`是有序的，`Dictionary`是无序的。`SortedDictionary`使用一种平衡搜索二叉树——`红黑树`(内部存储用的是`TreeSet`继承自`SortedSet`，实现为`红黑树`)，作为存储结构。 --- ##SortedSet - SortedSet支持元素按顺序排列，内部实现也是红黑树 --- ###红黑树和AVL树的比较 - AVL树比红黑树更为平衡，其`搜索效率`也好于红黑树 - 红黑树在最坏的情况下搜索时间复杂度为2logn，大于AVL树的logn - AVL树是严格平衡，红黑树只能达到“黑平衡”，即从任意节点出发到叶子节点经过的黑节点数量相同，但经过的红色节点数量不确定，最差的情况下，经过的红色节点和黑色节点一样多 - 红黑树`增删节点`的性能优于AVL树 - 往红黑树`增加节点或删除节点`引起红黑树不平衡,只需要`最多三次旋转`就能解决。相同条件下，AVL树的旋转次数要多于红黑树 --- ##SortedList - SortedList内部是使用数组实现的，添加和删除元素的时间复杂度是`O(n)`，查找元素的时间复杂度是`O(logn)` --- ###SortedList和SortedDictionary比较 --- - SortedList和SortedDictionary同时`支持快速查询和排序` - SortedList优势在于使用的`内存`比SortedDictionary`少` - SortedDictionary对未排序的数据执行`更快的插入和删除`操作：它的时间复杂度为`O(logn)`，而 SortedList为`O(n)` - SortedList适用于既需要快速查找又需要顺序排列但是添加和删除`元素较少`的场景 --- ##Stack --- - 栈内部实现还是数组，所以Push的时候时间复杂度可能为O(n)，因为可能会发生扩容行为，Pop的话就是 O(1)。 --- ```C# private T[] _array; private int _size; private int _version; private const int _defaultCapacity = 4; static T[] _emptyArray = new T[0]; ``` --- #### [](#增加元素-5)增加元素 --- ```C# public void Push(T item) { if (_size == _array.Length) { T[] newArray = new T[(_array.Length == 0) ? _defaultCapacity : 2 * _array.Length]; Array.Copy(_array, 0, newArray, 0, _size); _array = newArray; } _array[_size++] = item; _version++; } ``` --- ### [](#删除元素-5)删除元素 --- ```C# public T Pop() { if (_size == 0) { } _version++; T item = _array[--_size]; _array[_size] = default(T); return item; } ``` --- ### [](#查找元素-5)查找元素 --- - 注意同样不能遍历的时候对栈进行增删操作。 先来看他的迭代器构造函数 ``` internal Enumerator(Stack<T> stack) { _stack = stack; _version = _stack._version; _index = -2; currentElement = default(T); } ``` --- - 注意到那个index设置为了`-2`，这里是有特殊含义的，如果index为`-2`，代表这个迭代器是新生的，或者说是被重置的，迭代开始。如果为`-1`，说明迭代器已经由于某种原因被终止了，迭代结束。 --- ```C# public bool MoveNext() { bool retval; if (_version != _stack._version) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); if (_index == -2) { _index = _stack._size - 1; retval = (_index >= 0); if (retval) currentElement = _stack._array[_index]; return retval; } if (_index == -1) { return false; } retval = (--_index >= 0); if (retval) currentElement = _stack._array[_index]; else currentElement = default(T); return retval; } ``` --- ##Queue --- - 队列内部实现使用了`环形队列算法`，相对于传统的顺序队列，它具有更强的空间可复用性以及安全性。它的入队时间复杂度为`O(n)`，出队时间复杂度为`O(1)`。 --- ###相关字段 --- ```C# private T[] _array; private int _head; private int _tail; private int _size; private int _version; private const int _MinimumGrow = 4; private const int _ShrinkThreshold = 32; private const int _GrowFactor = 200; private const int _DefaultCapacity = 4; static T[] _emptyArray = new T[0]; ``` --- ### [](#增加元素-6)增加元素 --- ```C# public void Enqueue(T item) { //需要进行扩容操作 if (_size == _array.Length) { int newcapacity = (int) ((long) _array.Length * (long) _GrowFactor / 100); if (newcapacity < _array.Length + _MinimumGrow) { newcapacity = _array.Length + _MinimumGrow; } SetCapacity(newcapacity); } _array[_tail] = item; //确保_tail一直指向队尾，这里如果直接自增1，因为逻辑上的闭环，可能就会回到前面的位置。 _tail = (_tail + 1) % _array.Length; _size++; _version++; } ``` --- - `_head`一直确保指向队首。 --- ```C# private void SetCapacity(int capacity) { T[] newarray = new T[capacity]; if (_size > 0) { //如果队首的值小于队尾的值，直接复制即可 if (_head < _tail) { Array.Copy(_array, _head, newarray, 0, _size); } else//如果队首的值大于等于队尾的值（这种情况将在先添加后移除再添加的条件下出现） { //先把从队首指向的数组索引一直到数组最后一位范围内的值复制给新数组（从新数组的0索引开始） Array.Copy(_array, _head, newarray, 0, _array.Length - _head); //再从数组第一位一直到队尾指向的数组索引范围内的值复制给新数组（从新数组的_array.Length - _head值索引开始） //这样才能确保数据顺序正确且完整 Array.Copy(_array, 0, newarray, _array.Length - _head, _tail); } } _array = newarray; _head = 0; _tail = (_size == capacity) ? 0 : _size; _version++; } ``` ---  环形队列队尾的值小于队首的值情形 --- ### [](#删除元素-6)删除元素 --- ``` public T Dequeue() { if (_size == 0) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyQueue); T removed = _array[_head]; _array[_head] = default(T); //同样的，保证_head一直指向队首 _head = (_head + 1) % _array.Length; _size--; _version++; return removed; } ``` --- ### [](#查找元素-6)查找元素 --- - 队列的查找部分和栈的设计一样，但是具体的数值意义是相反的，如果index为`-1`，代表这个迭代器是新生的，或者说是被重置的，迭代开始。如果为`-2`，说明迭代器已经由于某种原因被终止了，迭代结束。 --- ```C# public bool MoveNext() { if (_version != _q._version) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); if (_index == -2) return false; _index++; if (_index == _q._size) { _index = -2; _currentElement = default(T); return false; } _currentElement = _q.GetElement(_index); return true; } ``` --- ###Hashtable - 因为Hashtable的Key和Value都是object类型，所以在使用值类型的时候，必然会出现装箱和拆箱的操作，因此性能肯定是不如Dictionary --- ### `List<>.Sort()`排序的底层实现原理 - 底层实现原理就是快速排序 + 堆排序 - 内省排序：从快速排序开始，当递归深度超过一定深度（深度为排序元素数量的对数值）后转为堆排序 --- ```C# // 1，看到我们调用的Sort方法 public void Sort(IComparer<T> comparer) { Sort(0, Count, comparer); } // 2，进入Sort(), 这里只关注倒数第二行，调用了Array.Sort() public void Sort(int index, int count, IComparer<T> comparer) { if (index < 0) { ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); } if (count < 0) { ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); } if (_size - index < count) { ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen); } Array.Sort(_items, index, count, comparer); _version++; } // 3, 这里只关注最后一行，调用了ArraySortHelper<T>.Default.Sort() public static void Sort<T>(T[] array, int index, int length, IComparer<T> comparer) { if (array == null) { throw new ArgumentNullException("array"); } if (index < 0 || length < 0) { throw new ArgumentOutOfRangeException((length < 0) ? "length" : "index", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); } if (array.Length - index < length) { throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); } if (length > 1 && ((comparer != null && comparer != Comparer<T>.Default) || !TrySZSort(array, null, index, index + length - 1))) { ArraySortHelper<T>.Default.Sort(array, index, length, comparer); } } // 4, 这一段，根据版本使用不同的排序 public void Sort(T[] keys, int index, int length, IComparer<T> comparer) { try { if (comparer == null) { comparer = Comparer<T>.Default; } // 如果.net版本是4.5 则执行IntrospectiveSort if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5) { IntrospectiveSort(keys, index, length, comparer); } // 否则都执行深度限制快速排序， 深度限制是32 else { DepthLimitedQuickSort(keys, index, length + index - 1, comparer, 32); } } catch (IndexOutOfRangeException) { IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer); } catch (Exception innerException) { throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), innerException); } } // 5，IntrospectiveSort 使用内省排序 ， 不在本篇文章介绍中 internal static void IntrospectiveSort(T[] keys, int left, int length, IComparer<T> comparer) { if (length >= 2) { IntroSort(keys, left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length), comparer); } } // 6，DepthLimitedQuickSort 重点！！！！！ // 深度限制 32 也就是说快排的轮次最大进行32轮， 32轮能排2^32个数 // 以下快排用的双边循环法 不清楚的可以参考我的博文 排序算法--快速排序的两种遍历方法(C#) internal static void DepthLimitedQuickSort(T[] keys, int left, int right, IComparer<T> comparer, int depthLimit) { while (depthLimit != 0) { // 确定起始点，中点，终点 int num = left; int num2 = right; int num3 = num + (num2 - num >> 1); // 将三个位置的顺序确定 SwapIfGreater(keys, comparer, num, num3); SwapIfGreater(keys, comparer, num, num2); SwapIfGreater(keys, comparer, num3, num2); T val = keys[num3]; //找基准位置 while (true) { // 找到左边需要换位置的索引 if (comparer.Compare(keys[num], val) < 0) { num++; continue; } // 找到右边需要换位置的索引 while (comparer.Compare(val, keys[num2]) < 0) { num2--; } // 如果超了 break if (num > num2) { break; } // 否则交换 if (num < num2) { T val2 = keys[num]; keys[num] = keys[num2]; keys[num2] = val2; } // 两边都往中间缩一个 num++; num2--; // 判断是否超了 if (num > num2) { break; } } depthLimit--; if (num2 - left <= right - num) { if (left < num2) { // 排左边 DepthLimitedQuickSort(keys, left, num2, comparer, depthLimit); } left = num; } else { if (num < right) { // 排右边 DepthLimitedQuickSort(keys, num, right, comparer, depthLimit); } right = num2; } if (left >= right) { return; } } // hello ，这里抓到一枚堆排同志 Heapsort(keys, left, right, comparer); } // 7， 接下来是堆排 private static void Heapsort(T[] keys, int lo, int hi, IComparer<T> comparer) { int num = hi - lo + 1; // 构建堆 for (int num2 = num / 2; num2 >= 1; num2--) { DownHeap(keys, num2, num, lo, comparer); } // 交换堆顶与末尾元素，并重新构建堆 for (int num3 = num; num3 > 1; num3--) { Swap(keys, lo, lo + num3 - 1); DownHeap(keys, 1, num3 - 1, lo, comparer); } } // 8，堆下沉 private static void DownHeap(T[] keys, int i, int n, int lo, IComparer<T> comparer) { T val = keys[lo + i - 1]; while (i <= n / 2) { int num = 2 * i; if (num < n && comparer.Compare(keys[lo + num - 1], keys[lo + num]) < 0) { num++; } if (comparer.Compare(val, keys[lo + num - 1]) >= 0) { break; } keys[lo + i - 1] = keys[lo + num - 1]; i = num; } keys[lo + i - 1] = val; } ``` --- 0911学习 0901学习