Въведение в сортирането в C #
Сортирането в c # е процесът на подреждане на съдържанието на колекция в определен ред. Колекцията може да бъде масив, списък или друга група данни. Колекцията може да съдържа елементи от прости типове, както и сложни типове. Един прост тип може да бъде съвкупност от цели числа, низове, числа с плаваща запетая и т.н. Сложен тип може да бъде колекция от обекти от дефинирани от потребителя типове като Служител, Студент и др. Сложните типове са повече от често вложени, което означава обектите могат да имат множество атрибути.
Примери
- Прост тип
- Цялостна колекция - (1, 2, 3, 4, 5)
- Колекция от струни - (“Марк”, “Джейми”, “Анна”)
- Комплекс тип
- ((Име: „Марк“, идентификационен номер на служителя: „123“, офис: „Лондон“),
(Име: „Jane“, идентификационен номер на служителя: „456“, офис: „NY“),
(Име: „Ани“, идентификационен номер на служителя: „789“, офис: „Сидни“))
- ((Име: „Марк“, идентификационен номер на служителя: „123“, офис: „Лондон“),
C # е предоставил вградени методи за сортиране на колекции. Дали това е масив, списък или която и да е обща колекция, методът C # Sort () може да я сортира въз основа на предоставения сравнител. Вътре, .Net реализацията използва алгоритъма Quicksort за сортиране на колекции в C #. Ще обсъдим повече за това в следващи раздели на статията.
Как се извършва сортирането в C #?
Както беше посочено по-рано, .Net рамката използва подхода Quicksort, за да сортира елементите в колекция C #. И така, какво е quicksort?
Quicksort следва стратегия за разделяне и завладяване. Това означава, че алгоритъмът за сортиране избира въртящ се елемент и разделя масива въз основа на въртящия се елемент. Елементите, по-малки от въртенето, се поставят пред него. Елементите, по-големи от въртенето, се поставят след него. Това гарантира, че шарнирният елемент е сортиран. Също така масивът е разделен на два елемента, по-малки от въртене и елементи, по-големи от въртенето. На следващо място, алгоритъмът следва същия подход и за двата масива.
Илюстрация на това може да видите по-долу.
Несортиран масив - 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
Стъпка 2b
Несортиран масив - 50
Pivot = 50
Частично сортиран масив - 50
Стъпка 3а
Несортиран масив - 18, 5, 16
Пивот = 16
Частично сортиран масив - 5, 16, 18
Сортиран масив - 5, 16, 18, 23, 32, 50
По този начин Quicksort има два ключови процеса - избор на въртене и дял на масива. Реализациите на алгоритъма зависят от избора на въртенето. Тя може да бъде или първият елемент, или последният, или произволен произволен елемент, или средната на масива. След като дялът е направен и въртенето е поставено в правилната позиция, алгоритъмът се извиква рекурсивно за разделените масиви, докато всеки елемент не бъде сортиран.
Когато сортирането се извършва в C #, идва концепцията за стабилен и нестабилен Quicksort. В стабилен Quicksort, ако два елемента са равни, редът им от първоначалния масив се запазва. В противен случай той е в нестабилен бърз корт. C # реализацията използва нестабилен Quicksort.
Видове сортиране в C #
В този раздел на статията ще се съсредоточим главно върху два вида колекции в C # - масиви и списъци. Ние бихме се потопили дълбоко в това как C # сортира масивите и списъците. Следващият раздел ще се опита да го обясни с някои примери.
1. Сортиране на масив в C #
Нека разгледаме различните начини, по които можем да сортираме масив в C #.
а. Използване на Default сравнение
Това е методът по подразбиране Sort (). Ако нито един сравнител не е изрично предаден към метода, 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");
)
)
)
изход:
б. Използване на персонализиран сравнител
Можем да предоставим и наш собствен потребителски сравнение за метода Sort (). Това ще инструктира C # компилатора да използва персонализирания сравнител вместо стандартния.
За да създадем персонализиран сравнител, трябва да приложим метода за сравнение () от интерфейса на IComparer. Кодът по-долу показва как да се създаде сравнение, което да сортира елементите в низходящ ред.
Създадохме клас, наследихме го от интерфейса на IComparer, внедрихме метода Сравнение () и го заменихме, за да сравним елементите в низходящ ред.
Код:
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 сравнение
Това е методът по подразбиране 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");
)
)
)
изход:
б. Използване на персонализиран сравнител
Можем също така да предоставим собствен персонализиран сравнение с метода sort (). Това ще инструктира компилатора c # да използва персонализирания сравнител вместо стандартния.
За да създадем персонализиран сравнител, трябва да приложим метода за сравнение () от интерфейса на IComparer. Кодът по-долу показва как да се създаде сравнение, което да сортира елементите в низходящ ред.
Създадохме клас, наследихме го от интерфейса на IComparer, внедрихме метода Сравнение () и го заменихме, за да сравним елементите в низходящ ред.
Код:
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 (). Този метод съдържа инструкциите за сравняване на елементите от списъка за сортиране.
В примера по-долу ние дефинираме потребителски клас служители и сортираме обектите на служителя въз основа на техните идентификационни номера.
Пример №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);
)
)
)
изход:
Сега очевидният въпрос, който ни идва на ум, е, че ако искаме да сортираме обектите от класа Служители въз основа на някаква друга собственост? Това е възможно. Ще трябва да внедрим интерфейса на 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 #