За да сортираме елементите на даден масив в .NET Framework използваме статичния метод Sort(…) на типа System.Array. Алгоритъмът, чрез който се извършва сортирането, е бързото сортиране на Хоор (QuickSort), който има сложност Θ( n log(n) ) в средния случай.
Забележка: QuickSort не е "устойчив" алгоритъм за сортиране, т.е. ако два елемента са равни, не е сигурно дали тяхната подредба ще се запази. Методът Sort(…) има няколко предефиниции. Ще разгледаме по-важните от тях:
-
Sort(Array) – сортира елементите на зададения едномерен масив, като очаква те да имплементират интерфейса IComparable. Той е имплементиран от много стандартни типове – Int32, Float, Double, Decimal, String, DateTime и др. Ако сме си дефинирали наш тип (клас) и искаме да сортираме масив от такива елементи, трябва имплементираме IComparable и по-точно неговия виртуален метод CompareTo(…).
-
Sort(Array, IComparer) – сортира елементите на дадения едномерен масив по зададена схема за сравнение (имплементирана в интерфейса IComparer).
-
Sort(Array, index, length) – сортира част от елементите на масива – в интервала [index, index + length).
-
Sort(Array, Array) – сортира елементите на двата масива като използва елементите на първия масив като ключове, по които да сортира масивите.
Сортиране на масиви – пример
Със следващия пример ще покажем колко е лесно сортирането на даден масив в .NET Framework:
static void Main()
{
String[] beers = {"Загорка", "Ариана", "Шуменско", "Астика",
"Каменица", "Болярка", "Амстел"};
Console.WriteLine("Unsorted: {0}",
String.Join(", ", beers));
// Result: Unsorted: Загорка, Ариана, Шуменско,
// Астика, Каменица, Болярка, Амстел
// Elements of the array beers are of type String,
// so they implement IComparable
Array.Sort(beers);
Console.WriteLine("Sorted: {0}",
String.Join(", ", beers));
// Result: Sorted: Амстел, Ариана, Астика,
// Болярка, Загорка, Каменица, Шуменско
}
| Сортиране с IComparer – пример
В следващия пример ще покажем как можем да сортираме масиви като подаваме на метода Array.Sort(…) като параметър тип, който имплементира интерфейса IComparer. За целта сме дефинирали клас Student и клас StudentAgeComparer, който имплементира IComparer и в метода си Compare(…) сравнява студентите по техните години. Забележете, че ако някой от двата обекта, които се подават като параметри на Compare(…), не е Student, подаваме ArgumentException, защото няма как да ги сравним.
using System;
using System.Collections;
class Student
{
internal string mName;
internal int mAge;
public Student(string aName, int aAge)
{
mName = aName;
mAge = aAge;
}
public override string ToString()
{
return String.Format("({0} : {1})", mName, mAge);
}
}
class StudentAgeComparer : IComparer
{
public int Compare(object aEl1, object aEl2)
{
Student student1 = aEl1 as Student;
if (student1 == null)
{
throw new ArgumentException(
"Argument 1 is not Student or is null");
}
Student student2 = aEl2 as Student;
if (student2 == null)
{
throw new ArgumentException(
"Argument 2 is not Student or is null");
}
return student1.mAge.CompareTo(student2.mAge);
}
}
class CompareStudentsDemo
{
static void Main()
{
Student[] students =
{
new Student("Бай Иван", 73),
new Student("Дядо Мраз", 644),
new Student("Баба Яга", 412),
new Student("Кака Мара", 27),
new Student("Кольо Пияндето", 32)
};
Array.Sort(students, new StudentAgeComparer());
Console.WriteLine("Students sorted by age:");
foreach (Student student in students)
{
Console.WriteLine(student);
}
}
}
|
Ето и изходът от примера:
Двоично търсене
Когато искаме многократно да търсим различни елементи в даден масив, е по-добре първо да го сортираме и после да използваме метода на двоичното търсене. Това е бърз метод за претърсване на вече сортиран масив. Сложността, с която претърсва масив от n елемента, е Θ( log(n) ).
В .NET Framework двоичното търсене е реализирано в статичния метод Array.BinarySearch(Array, object). Ако елементът бъде намерен, методът връща неговия индекс, а в противен случай връща отрицателно число, което е побитово отрицание на индекса на първия елемент, който е по-голям от търсения или побитово отрицание на индекса на последния елемент + 1, ако търсената стойност е по-голяма от всички елементи в масива. Методът Array.BinarySearch(…) има същите изисквания като Array.Sort(…) – или елементите на масива трябва да имплементират IComparable или трябва да се подаде инстанция на IComparer.
Двоично търсене – пример
Със следващия пример ще покажем използването на статичния метод Array.BinarySearch(…) за да претърсим масива за дадени елементи. Ще използваме и оператора за побитово отрицание ~ за да видим на коя позиция е следващия по-големина елемент, ако елементът, който търсим не бъде намерен в масива.
static void Main()
{
String[] beers = {"Загорка", "Ариана", "Шуменско", "Астика",
"Каменица", "Болярка", "Амстел"};
Array.Sort(beers);
string target = "Астика";
int index = Array.BinarySearch(beers, target);
Console.WriteLine("{0} is found at index {1}.",
target, index);
// Result: Астика is found at index 2.
target = "Мастика";
index = Array.BinarySearch(beers, target);
Console.WriteLine("{0} is not found. The next larger element is at index {1}.", target, ~index);
// Result: Мастика is not found. The next larger element is
at index 6.
}
|
Сподели с приятели: |
