C# List＜＞.Sort， 排序的底层实现原理_少侠Smile丶-程序员秘密

首先，C# List<>.Sort() 排序的底层实现原理就是快速排序 + 堆排序（.net 4.5用的内省排序）。

大佬可以 return了。

接下来，让我们一一还原案发现场。

源码干货预警，头大！！！！！

// 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