Введение в сортировку в C #
Сортировка в c # - это процесс упорядочения содержимого коллекции в определенном порядке. Коллекция может быть массивом, списком или любой другой группой данных. Коллекция может содержать элементы как простых типов, так и сложных типов. Простой тип может быть набором целых чисел, строк, чисел с плавающей запятой и т. Д. Сложный тип может быть набором объектов пользовательских типов, таких как Employee, Student и т. Д. Сложные типы более чем часто являются вложенными, что означает объекты могут иметь несколько атрибутов.
Примеры
- Простой тип
- Целочисленная коллекция - (1, 2, 3, 4, 5)
- Коллекция струн - («Марк», «Джейми», «Анна»)
- Комплексный тип
- ((Имя: «Марка», Код сотрудника: «123», Офис: «Лондон»),
(Имя: «Джейн», идентификационный номер сотрудника: «456», офис: «Нью-Йорк»),
(Имя: «Энни», идентификационный номер сотрудника: «789», офис: «Сидней»))
- ((Имя: «Марка», Код сотрудника: «123», Офис: «Лондон»),
C # предоставляет встроенные методы для сортировки коллекций. Будь то метод Array, List или любой универсальный набор, метод C # Sort () может отсортировать его на основе предоставленного Comparer. Внутренне реализация .Net использует алгоритм Quicksort для сортировки коллекций в C #. Об этом мы поговорим в следующих разделах статьи.
Как сортировка выполняется в C #?
Как указывалось ранее, .Net Framework использует подход Quicksort для сортировки элементов в коллекции C #. Итак, что такое быстрая сортировка?
Быстрая сортировка следует стратегии разделяй и властвуй. Это означает, что алгоритм сортировки выбирает элемент сводки и делит массив на основе элемента сводки. Элементы, меньшие, чем стержень, размещены перед ним. Элементы больше, чем шарнир, размещаются после него. Это гарантирует, что элемент сводки будет отсортирован. Кроме того, массив делится на два - элементы меньше, чем шарнир и элементы больше, чем шарнир. Далее алгоритм следует одинаковому подходу для обоих массивов.
Иллюстрацию этого можно увидеть ниже.
Несортированный массив - 18, 5, 16, 23, 50, 32
Шаг 1 (Pivot = 32) - 18, 5, 16, 23, 32, 50
Шаг 2а
Несортированный массив - 18, 5, 16, 23
Pivot = 23
Частично отсортированный массив - 18, 5, 16, 23
Шаг 2б
Несортированный массив - 50
Пивот = 50
Частично отсортированный массив - 50
Шаг 3а
Несортированный массив - 18, 5, 16
Pivot = 16
Частично отсортированный массив - 5, 16, 18
Сортированный массив - 5, 16, 18, 23, 32, 50
Таким образом, Quicksort имеет два ключевых процесса - выбор оси и разбиение массива. Реализации алгоритма зависят от выбора оси. Это может быть либо первый элемент, либо последний, либо любой случайный элемент, либо медиана массива. После того, как разделение выполнено, а ось помещена в правильное положение, алгоритм рекурсивно вызывается для секционированных массивов, пока не будет отсортирован каждый элемент.
Когда сортировка выполняется в C #, возникает концепция стабильной и нестабильной быстрой сортировки. В стабильной быстрой сортировке, если два элемента равны, их порядок относительно исходного массива сохраняется. Иначе, это в нестабильной быстрой сортировке. Реализация C # использует нестабильную быструю сортировку.
Типы сортировки в C #
В этом разделе статьи мы сосредоточимся в основном на двух типах коллекций в C # - массивах и списках. Мы глубоко погрузимся в то, как C # сортирует массивы и списки. Следующий раздел попытается объяснить это на нескольких примерах.
1. Сортировка массива в C #
Давайте рассмотрим различные способы сортировки массива в C #.
а. Использование Default Comparer
Это метод Sort () по умолчанию. Если метод Comparer явно не передается в метод, C # использует порядок возрастания для упорядочивания элементов.
Код:
using System;
public class Program
(
public static void Main()
(
String() strArray = ("I", "Am", "Learning", "Array", "Sorting", "In", "C#");
int() intArray = (23, 76, 12, 43, 90, 30);
Array.Sort(strArray);
Array.Sort(intArray);
Console.WriteLine("Sorted String Array:\n");
DisplayArray(strArray);
Console.WriteLine("\n\n\nSorted Integer Array:\n");
DisplayArray(intArray);
)
static void DisplayArray(string() arr)
(
foreach (string a in arr)
(
Console.Write(a + "\t");
)
)
static void DisplayArray(int() arr)
(
foreach (int a in arr)
(
Console.Write(a + "\t");
)
)
)
Выход:
б. Использование Custom Comparer
Мы также можем предоставить наш собственный метод Comparer для метода Sort (). Это будет указывать компилятору C # использовать собственный компаратор вместо стандартного.
Чтобы создать собственный компаратор, нам нужно реализовать метод Compare () из интерфейса IComparer. Приведенный ниже код демонстрирует, как создать компаратор, который бы сортировал элементы в порядке убывания.
Мы создали класс, унаследовали его от интерфейса IComparer, реализовали метод Compare () и переопределили его для сравнения элементов в порядке убывания.
Код:
using System;
public class DescendingComparer : System.Collections.IComparer
(
public int Compare(Object a, Object b)
(
return (new System.Collections.CaseInsensitiveComparer()).Compare(b, a);
)
)
public class Program
(
public static void Main()
(
String() strArray = ("I", "Am", "Learning", "Array", "Sorting", "In", "C#");
int() intArray = (23, 76, 12, 43, 90, 30);
Array.Sort(strArray, new DescendingComparer());
Array.Sort(intArray, new DescendingComparer());
Console.WriteLine("Sorted String Array in Descending Order:\n");
DisplayArray(strArray);
Console.WriteLine("\n\n\nSorted Integer Array in Desc Order:\n");
DisplayArray(intArray);
)
static void DisplayArray(string() arr)
(
foreach (string a in arr)
(
Console.Write(a + "\t");
)
)
static void DisplayArray(int() arr)
(
foreach (int a in arr)
(
Console.Write(a + "\t");
)
)
)
Выход:
с. Использование пар ключ-значение
C # также предоставляет способ сортировки одного массива, используя значения ключей из другого массива. В приведенном ниже примере есть пары ключ-значение имен и фамилий людей. Мы бы отсортировали их по имени и фамилии, используя метод Sort ().
Код:
using System;
public class Program
(
public static void Main()
(
String() firstNames = ("Tom", "Jack", "Anna", "Veronica", "Jessica", "Mike");
String() lastNames = ("Phelps", "Anderson", "Spectre", "Clarke", "Williams", "Fonseca");
Array.Sort(firstNames, lastNames);
Console.WriteLine("Sorted by First Names:\n");
DisplayArray(firstNames, lastNames);
Array.Sort(lastNames, firstNames);
Console.WriteLine("\n\nSorted by Last Names:\n");
DisplayArray(firstNames, lastNames);
)
static void DisplayArray(string() arr1, string() arr2)
(
for (int i = 0; i < arr1.Length; i++)
(
Console.WriteLine(arr1(i) + " " + arr2(i));
)
)
)
Выход:
2. Сортировка списка в C #
Давайте рассмотрим различные способы сортировки списка в C #.
Примечание. Для использования списков в C #, включая библиотеку System.Collections.Generic.а. Использование Default Comparer
Это метод sort () по умолчанию. если в метод явно не передается компаратор, c # использует восходящий порядок для размещения элементов.
Код:
public class Program
using System.Collections.Generic;
(
public static void Main()
(
String() strArray = ("I", "Am", "Learning", "Array", "Sorting", "In", "C#");
List strList = new List(strArray);
int() intArray = (23, 76, 12, 43, 90, 30);
List intList = new List(intArray);
strList.Sort();
intList.Sort();
Console.WriteLine("Sorted String List:\n");
DisplayList(strList);
Console.WriteLine("\n\n\nSorted Integer List:\n");
DisplayList(intList);
)
static void DisplayList(List myList)
(
foreach (string a in myList)
(
Console.Write(a + "\t");
)
)
static void DisplayList(List myList)
(
foreach (int a in myList)
(
Console.Write(a + "\t");
)
)
)
Выход:
б. Использование Custom Comparer
Мы также можем предоставить наш собственный компаратор для метода sort (). Это будет указывать компилятору c # использовать собственный компаратор вместо стандартного.
Чтобы создать собственный компаратор, нам нужно реализовать метод Compare () из интерфейса IComparer. Приведенный ниже код демонстрирует, как создать компаратор, который бы сортировал элементы в порядке убывания.
Мы создали класс, унаследовали его от интерфейса IComparer, реализовали метод Compare () и переопределили его для сравнения элементов в порядке убывания.
Код:
using System;
using System.Collections.Generic;
public class LengthComparer : IComparer
(
public int Compare(string a, string b)
(
return (a.Length.CompareTo(b.Length));
)
)
public class DigitSumComparer : IComparer
(
public int Compare(int a, int b)
(
int sum_a = 0;
int sum_b = 0;
while (a > 0)
(
sum_a += (a % 10);
a /= 10;
)
while (b > 0)
(
sum_b += (b % 10);
b /= 10;
)
return (sum_a.CompareTo(sum_b));
)
)
public class Program
(
public static void Main()
(
LengthComparer lc = new LengthComparer();
DigitSumComparer dsc = new DigitSumComparer();
String() strArray = ("I", "Am", "Learning", "Array", "Sorting", "In", "C#");
List strList = new List(strArray);
int() intArray = (23, 76, 12, 43, 90, 30);
List intList = new List(intArray);
strList.Sort(lc);
intList.Sort(dsc);
Console.WriteLine("Sorted String List by Length:\n");
DisplayList(strList);
Console.WriteLine("\n\n\nSorted Integer List by Sum of Digits:\n");
DisplayList(intList);
)
static void DisplayList(List myList)
(
foreach (string a in myList)
(
Console.Write(a + "\t");
)
)
static void DisplayList(List myList)
(
foreach (int a in myList)
(
Console.Write(a + "\t");
)
)
)
Выход:
Сортировка сложных типов списков
Сложные типы списков являются пользовательскими списками. Чтобы быть более точным, это списки объектов пользовательских классов. Будучи определяемыми пользователем, объекты представляют собой смесь различных примитивных типов. Сложно сортировать сложный тип списка. Компилятор C # ожидает, что каждый сложный класс наследуется от интерфейса IComparable и определяет метод CompareTo (). Этот метод содержит инструкции о том, как сравнивать элементы списка для сортировки.
В приведенном ниже примере мы определяем пользовательский класс Employees и сортируем объекты Employee по их идентификаторам.
Пример № 1
Код:
using System;
using System.Collections.Generic;
public class Employee : IComparable
(
public int id (get;set;)
public string name(get;set;)
public double salary(get;set;)
public int CompareTo(Employee e)
(
return this.id.CompareTo(e.id);
)
)
public class Program
(
public static void Main()
(
List emps = new List();
emps.Add(new Employee()
(id = 123, name = "Tom Phelps", salary = 20000.00));
emps.Add(new Employee()
(id = 897, name = "Jack Anderson", salary = 40050.50));
emps.Add(new Employee()
(id = 342, name = "Anna Spectre", salary = 31030.89));
emps.Add(new Employee()
(id = 219, name = "Veronica Clarke", salary = 66333.66));
emps.Add(new Employee()
(id = 642, name = "Jessica Williams", salary = 50505.05));
emps.Add(new Employee()
(id = 923, name = "Mike Fonseca", salary = 76543.21));
Console.WriteLine("Original Employee List:\n");
DisplayList(emps);
emps.Sort();
Console.WriteLine("\n\nSorted Employee List by IDs:\n");
DisplayList(emps);
)
static void DisplayList(List emp)
(
foreach (Employee e in emp)
(
Console.WriteLine("Id: " + e.id + ", Name: " + e.name + ", Salary: " + e.salary);
)
)
)
Выход:
Теперь возникает очевидный вопрос: а что если мы хотим отсортировать объекты класса Employee на основе какого-либо другого свойства? Это возможно. Нам нужно реализовать интерфейс IComparer. Давайте посмотрим на пример ниже, чтобы понять.
Пример № 2
Код:
using System;
using System.Collections.Generic;
public class Employee
(
public int id (get;set;)
public string name(get;set;)
public double salary(get;set;)
)
public class SortByName : IComparer
(
public int Compare(Employee e1, Employee e2)
(
return e1.name.CompareTo(e2.name);
)
)
public class SortBySalary : IComparer
(
public int Compare(Employee e1, Employee e2)
(
return e1.salary.CompareTo(e2.salary);
)
)
public class Program
(
public static void Main()
(
SortByName sbn = new SortByName();
SortBySalary sbs = new SortBySalary();
List emps = new List();
emps.Add(new Employee()
(id = 123, name = "Tom Phelps", salary = 20000.00));
emps.Add(new Employee()
(id = 897, name = "Jack Anderson", salary = 40050.50));
emps.Add(new Employee()
(id = 342, name = "Anna Spectre", salary = 31030.89));
emps.Add(new Employee()
(id = 219, name = "Veronica Clarke", salary = 66333.66));
emps.Add(new Employee()
(id = 642, name = "Jessica Williams", salary = 50505.05));
emps.Add(new Employee()
(id = 923, name = "Mike Fonseca", salary = 76543.21));
emps.Sort(sbn);
Console.WriteLine("Sorted Employee List by Names:\n");
DisplayList(emps);
emps.Sort(sbs);
Console.WriteLine("\n\nSorted Employee List by Salaries:\n");
DisplayList(emps);
)
static void DisplayList(List emp)
(
foreach (Employee e in emp)
(
Console.WriteLine("Id: " + e.id + ", Name: " + e.name + ", Salary: " + e.salary);
)
)
)
Выход:
Вывод
Итак, эта статья подробно рассказала о том, как сортировать коллекции в C #. Мы сосредоточились главным образом на массивах и списках, поскольку эти два также охватывают все примитивные типы. После того, как концепция сортировки в C # очень хорошо понятна, становится легко реализовать сортировку в других коллекциях, таких как перечисления, словари и т. Д. После завершения этой статьи рекомендуется изучить документацию MSDN для получения дополнительных реализаций сортировки в C #.
Рекомендуемые статьи
Это руководство по сортировке в C #. Здесь мы обсудим производительность сортировки, типы сортировки, такие как массив и список, а также примеры и реализацию кода. Вы также можете посмотреть следующие статьи, чтобы узнать больше -
- Объекты в C #
- Модификаторы доступа в C #
- Пузырьковая сортировка на Java
- Указатели в C #
- Сортировка в Python
- String Array в JavaScript
- Сравнимый пример в Java | Интерфейс коллекции на Java
- Массив строк в C с функциями
- Различные примеры коллекций в C #