Кратко съдържание



страница56/73
Дата21.07.2018
Размер8.57 Mb.
1   ...   52   53   54   55   56   57   58   59   ...   73

Сортиране на масиви


За да сортираме елементите на даден масив в .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.

}

1   ...   52   53   54   55   56   57   58   59   ...   73


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница