В методе List <T>.Sort () сравнивается ли элемент с самим собой?

Question

Если я передам пользовательский IComparer экземпляру метода List Sort (), будет ли метод Compare (x, y) сравнения когда-либо вызываться с тем же элементом?

т. Возможно ли назвать Compare(x,x).

Редактировать: Больше интересует случай, когда элементы списка различны.

Answer 1

Я написал тестовую программу, чтобы попробовать ее.Похоже, что на самом деле делает Compare () одним и тем же элементом к себе (по крайней мере, Compare () вызывается для одного и того же элемента дважды).В этой программе метод Compare () вызывается с аргументами (2, 2).

using System;
using System.Collections.Generic;

static class Program
{
    class MyComparer : Comparer<int>
    {
        public override int Compare(int x, int y)
        {
            Console.WriteLine("Compare(" + x + ", " + y + ")");
            if (x < y) return -1;
            if (x > y) return 1;
            return 0;
        }
    }

    static void Main()
    {
        MyComparer comparer = new MyComparer();
        List<int> list = new List<int> { 1, 2, 3 };
        list.Sort(comparer);
        return;

    }
}

И вывод:

Compare(1, 2)
Compare(1, 3)
Compare(2, 3)
Compare(1, 2)
Compare(2, 2)
Compare(2, 3)
Compare(2, 2)

Answer 2

Из документов :

Этот метод использует Array.Sort, который использует алгоритм быстрой сортировки.

Быстрая сортировка никогда не будетсравните элемент с самим собой. Некоторые реализации QuickSort сравнивают элементы с самим собой.Это также может произойти, если этот элемент встречается в вашем Списке более одного раза.

В любом случае, для того чтобы ваша функция сравнения была правильной, хорошо функционирующей функцией сравнения, вам необходимо обработать случай, когда элементы являютсяпо сравнению с самим собой.

Answer 3

Хотя это не строго гарантировано, я уверен, что метод Sort в List никогда не вызовет ваш метод сравнения для сравнения объекта с самим собой, если только этот объект не появится в списке несколько раз.Я основываю этот вывод на том факте, что List.Sort реализован с использованием алгоритма QuickSort (согласно MSDN), который никогда не сравнивает , как правило, не предполагает сравнения одного и того же элемента с самим собой (ини один из других задокументированных алгоритмов сортировки, о которых я могу думать).(Правка. Похоже, что реализация Microsoft сравнивает этот элемент с самим собой. См. Принятый ответ выше.)

Однако, хорошая практика кодирования будет диктовать, что ваша реализация IComparer должна быть способна обрабатывать передачу одного и того же объекта в обоихпараметры, так как в противном случае ваша реализация не полностью выполняет контракт, определенный IComparer.Вероятно, это будет работать для вашего сценария, но вы будете полагаться на детали реализации метода sort (которые могут измениться в будущем), и вы не сможете использовать реализацию IComparer в других сценариях, где такого нетгарантией (или, что еще хуже, вы или кто-то еще пользуетесь ею и, возможно, создаете труднодоступную ошибку).

Answer 4

Другой ответ, основанный на XML-части ECMA-335 , спецификации BCL (Base Class Library).Хотя это и не гарантировано связано с тем, что делают реальные реализации, это настолько авторитетно, насколько это возможно.И в спецификации ничего не сказано, кроме:

В худшем случае это операция O (n ^ 2), где n - количество элементов для сортировки.В среднем это O (n log n).

Хотя это наводит на мысль о быстрой сортировке, это абсолютно не гарантия.Кроме того, спецификация не требует реализации в терминах Array.Sort.

. Нижняя строка: что касается спецификации, то реализации вполне могут сравнивать элементы с самим собой.