Как List.Sort () использует предоставленный экземпляр Comparer?

Question

В следующем коде, что произойдет в методе Sort Method Of Main, есть ли в нем цикл?

Я обнаружил, что он использует QuickSort Algorithm, но как он сортируется по функции сравнения?

class Products
    {
        public string Name { get; private set; }
        public decimal Price { get; private set; }
        public Products(string name,decimal price)
        {
            Name = name;
            Price = price;
        }
        public Products()
        {

        }
        public static List<Products> GetSampleProducts()
        {
            return new List<Products>()
            {
                new Products{Name = "Company",Price=1800},
                new Products{Name = "Assassins",Price=2800},
                new Products{Name = "Zrogs",Price=1300},
                new Products{Name = "Swenney Todd",Price=1300}
            };
        }
        public override string ToString()
        {
            return string.Format("{0} price is {1}", Name, Price);
        }
    }
    class ProductComparer : IComparer<Products>
    {
        public int Compare(Products x, Products y)
        {
            return x.Name.CompareTo(y.Name);
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Products products = new Products();
            List<Products> lst_products = Products.GetSampleProducts();
            lst_products.Sort (new ProductComparer());
            foreach (Products p in lst_products)
            {
                Console.WriteLine(p);
            }
            Console.ReadKey();
        }
    }

Спасибо ...

Answer 1

Обычно используется метод Array.Sort () и компаратор, предоставленные вами для сравнения следующих двух элементов при сортировке с использованием алгоритма QuickSort .

Забавный анимированный QuickSort:

Визуализация алгоритма быстрой сортировки. Горизонтальные линии представляют собой опорные значения:

EDIT:

Ниже приведены методы, которые фактически выполняют быструю сортировку с использованием предоставленного компаратора (QuickSort, SwapIfGreaterWithItems)

// internal class ArraySortHelper<T> : IArraySortHelper<T>
internal static void QuickSort(
                         T[] keys, 
                         int left, 
                         int right, 
                         IComparer<T> comparer)
{
    do
    {
        int a = left;
        int b = right;
        int num3 = a + ((b - a) >> 1);
        ArraySortHelper<T>.SwapIfGreaterWithItems(keys, comparer, a, num3);
        ArraySortHelper<T>.SwapIfGreaterWithItems(keys, comparer, a, b);
        ArraySortHelper<T>.SwapIfGreaterWithItems(keys, comparer, num3, b);
        T y = keys[num3];
        do
        {
            while (comparer.Compare(keys[a], y) < 0)
            {
                a++;
            }
            while (comparer.Compare(y, keys[b]) < 0)
            {
                b--;
            }
            if (a > b)
            {
                break;
            }
            if (a < b)
            {
                T local2 = keys[a];
                keys[a] = keys[b];
                keys[b] = local2;
            }
            a++;
            b--;
        }
        while (a <= b);
        if ((b - left) <= (right - a))
        {
            if (left < b)
            {
                ArraySortHelper<T>.QuickSort(keys, left, b, comparer);
            }
            left = a;
        }
        else
        {
            if (a < right)
            {
                ArraySortHelper<T>.QuickSort(keys, a, right, comparer);
            }
            right = b;
        }
    }
    while (left < right);
}


private static void SwapIfGreaterWithItems(
                                T[] keys, 
                                IComparer<T> comparer, 
                                int a, 
                                int b)
{
    if ((a != b) && (comparer.Compare(keys[a], keys[b]) > 0))
    {
        T local = keys[a];
        keys[a] = keys[b];
        keys[b] = local;
    }
}