Часто приходится создавать списки List со ссылочными типами данных, такими как классы или массивы. Другая же необходимая задача — это сортировка списков. В языке C# у List есть метод, позволяющий сортировать список. Когда список состоит из примитивных типов данных — методом Sort пользоваться легко, но если данные представляют собой какую-либо структуру или класс, то всё не так очевидно. Рассмотрим в данной статье сортировку List в C#.
Создание списка List для сортировки
Допустим нам необходимо хранить данные пользователей: их имя и год рождения. Для этого создадим в языке программирования C# список List, элементами которого, является строковый массив. Имя переменной: people.
|
1 |
List<string[]> people = new List<string[]>(); |
Добавим в него четыре элемента с информацией о пользователях:
|
1 2 3 4 |
people.Add(new string[] { "Иван", "1980" }); people.Add(new string[] { "Яна", "1987" }); people.Add(new string[] { "Михаил", "1979" }); people.Add(new string[] { "Анна", "1992" }); |
Соответственно каждый элемент списка List содержит одномерный строковый массив из двух элементов с именем и годом рождения человека.
Вспомогательный метод для вывода списка в консоль
Напишем также метод OutputList, который выводит все элементы коллекции на экран в консоль.
|
1 2 3 4 5 6 7 8 9 10 |
static void OutputList(List<string[]> list, string label) { Console.WriteLine(label); Console.WriteLine(); foreach (string[] item in list) Console.WriteLine(item[0] + ", дата рождения: " + item[1]); Console.WriteLine(); } |
Аргументы метода: list — сам список, который нужно вывести в консоль и label — строка с информацией (она будет выведена перед списком).
Выведем на экран текущее содержимое списка people (запустим программу комбинацией клавиш Ctrl + F5):
|
1 |
OutputList(people, "Список до сортировки"); |
Сортировка List в языке C#
Для того, чтобы произвести сортировку списка List, элементами которого являются ссылочные типы данных, сначала необходимо написать метод, описывающий сравнение двух таких «сложных» элементов списка.
Данный метод называется Compare и он должен находиться в отдельно созданном классе, реализующем интерфейс IComparer<>.
Первый пример сортировки списка
Сначала выполним сортировку по такому принципу: отсортируем список people по возрастанию длин имён людей.
Для этого создадим класс с именем NameComparer (имя может быть любым допустимым), который реализует интерфейс IComparer<string[]>. Тип string[] мы указываем, поскольку элемент списка в нашем случаем — это строковый массив.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class NameComparer : IComparer<string[]> { public int Compare(string[] o1, string[] o2) { if (o1[0].Length > o2[0].Length) { return 1; } else if (o1[0].Length < o2[0].Length) { return -1; } return 0; } } |
В классе обязательно должен содержаться метод Compare, в котором описано как сравнивать два объекта (два элемента списка). В нашем случае эти объекты имеют имена o1 и o2.
Сортировка по возрастанию
Если первый объект по нужному признаку больше второго объекта, то следует возвратить единицу. Если меньше, то минус единицу.
Если объекты равны, то возвращаем ноль.
Для сортировки по убыванию поменяйте местами 1 и -1.
В данном примере мы сравниваем длину строк первых (нулевых) элементов двух массивов, поскольку в первом элементе хранится имя пользователя.
Отсортируем список people. Для этого создадим экземпляр класса NameComparer и вызовем у списка метод Sort, передав в него в качестве аргумента экземпляр созданного класса. После выведем список в консоль.
|
1 2 3 4 5 |
NameComparer nc = new NameComparer(); people.Sort(nc); OutputList(people, "Список после сортировки по длине имён"); |
Второй пример сортировки списка
Рассмотрим еще один пример сортировки. На этот раз отсортируем список people по году рождения людей (от старших к младшим). Для этого создадим класс YearComparer.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class YearComparer : IComparer<string[]> { public int Compare(string[] o1, string[] o2) { int a = Convert.ToInt32(o1[1]); int b = Convert.ToInt32(o2[1]); if (a > b) { return 1; } else if (a < b) { return -1; } return 0; } } |
Поскольку у нас год хранится в виде строки, сначала её необходимо конвертировать в число. Делается это с помощью метода Convert.ToInt32() [строки 5 и 6].
Отсортируем List по годам рождения пользователей и выведем его на экран.
|
1 2 3 4 5 |
YearComparer yc = new YearComparer(); people.Sort(yc); OutputList(people, "Список после сортировки по году рождения"); |
Скачать исходник программы из данного урока:
Скачать исходник Репозиторий проекта на GitHub
Принцип работы метода Sort в списках List
Следует отдельно сказать о том, какие алгоритмы сортировки применяются в методе Sort().
- Если в списке менее 16 элементов, то сортировка будет производиться методом вставок.
- Если количество элементов в списке (обозначим буквой N) превышает число 2 * Log(N), то используется алгоритм пирамидальной сортировки.
- Во всех остальных случаях используется алгоритм быстрой сортировки.
Сложность выполнения метода в среднем равна O(N * Log(N)). В худшем случае сортировка займёт O(N ^ 2) операций.
Также отметим, что метод Sort реализует так называемую нестрогую сортировку, то есть возможны случаи, когда порядок одинаковых элементов будет меняться.
Материалы по теме:
Поделиться в соц. сетях: