C# list sort底层原理

标签：HERE   tar   partition   other   ros   which   插入排序算法   lex   使用   

如果提供比较，则使用委托表示的方法对列表中的元素进行排序。如果comparison为null，则抛出ArgumentNullException。

此方法使用数组.排序，其应用自省排序，如下所示：

如果分区大小小于或等于16个元素，则使用插入排序算法

如果分区数超过2logn，其中n是输入数组的范围，则使用Heapsort算法。

否则，它将使用快速排序算法。

这个实现执行不稳定的排序；也就是说，如果两个元素相等，它们的顺序可能不会被保留。相反，稳定排序保留相等元素的顺序。

此方法是一个O（n logn）操作，其中n是Count。

官网文档：

https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1.sort?redirectedfrom=MSDN&view=net-5.0#System_Collections_Generic_List_1_Sort_System_Comparison__0__

Remarks

If comparison is provided, the elements of the List are sorted using the method represented by the delegate.

If comparison is null, an ArgumentNullException is thrown.

This method uses Array.Sort, which applies the introspective sort as follows:

• If the partition size is less than or equal to 16 elements, it uses an insertion sort algorithm

• If the number of partitions exceeds 2 log n, where n is the range of the input array, it uses a Heapsort algorithm.

• Otherwise, it uses a Quicksort algorithm.

This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.

This method is an O(n log n) operation, where n is Count.

C# list sort底层原理

标签：HERE   tar   partition   other   ros   which   插入排序算法   lex   使用   

原文地址：https://www.cnblogs.com/workharder/p/14384077.html