На практика често се използва усъвършенствани техники за сортиране, както преки методи имат относително ниска скорост.
Въпреки това, с малка дължина на масива и / или специални елементи към първоначалното си място, директни методи също дават добри резултати.
Помислете за принципите на основните (преки) методи за сортиране.
Размяна Sort (метод на "балон")
Последователно сравняване съседни двойки елементи х [к] и Х [к 1] (к = 1,2. N -1) и, ако тяхната относителна позиция не отговаря на предварително определено състояние, те са пренаредени (разменят).
Търсени максимум (минимум) елемент и се прехвърля в края на масива. След това този метод се прилага за всички елементи, с изключение на последния (тя вече е в сила), и т.н.
Друго изпълнение на метода - елемент за пренос на открита в началото на масива и последващото прилагане на метода за всички елементи, с изключение на първия, и т.н.
Масивът е разделен на две части: сортирани и сортиран. Елементи на несортиран част алтернативно избрани и поставени в сортирани част, така че да не нарушава подреждането на елементите. В началото като отхвърли част само те приемат един първи елемент.
Според броя на сравненията, всички методи са с квадратно зависимост от дължината на масива
Според броя на задачи:
· Методи обмен и вложки имат квадратно зависимост от дължината на масива
· Метод за избор има редица задачи поръчва п * LN (п)
Експерти предполагат, като се използва методът на избор за сортиране на сложни структури от данни, където се извършва сравнение на голям брой задачи.
Като цяло, методите за поставяне и подбор са приблизително еквивалентни и няколко пъти (в зависимост от дължината на масива) е по-добре от споделяне метод.
За подобрени методи за сортиране включват, например, следните алгоритми:
ü сортиране чрез включвания с намаляване разстояния;
ü Сортиране използването на дървен материал;
ü Сортиране чрез разделяне (Hoare Quicksort)
рекурсивни алгоритми
Има случаи, когато задачата се разделя на подзадачи, които от своя страна имат същата структура като основна задача.
В такива случаи се използва механизъм, наречен рекурсия.
Метод подпрограма разговор, в който подпрограмата нарича себе си, се нарича рекурсия.
Практики прилагат рекурсия, наречена рекурсивни подпрограми.
Нека обясним механизма на рекурсивни подпрограми, използвайки класически пример за използването на рекурсия.
Изчисляване на факториален.
Обосновка на избора на метода.
Трябва да отбележим, че за изчисляване на факториела на число N може да бъде, както следва:
Ние сме за прилагане на алгоритъм, с помощта на механизъм рекурсия.
Тъй като рутинна ще изготви изчисляване на стойността, а след това ние осъзнаваме, че ще бъде под формата на функция.
Факт функция (п: байт). цяло число;
ако п = 0, тогава Факт: = 1
друго Факт: = N * Факт (п-1);
Механизмът е описано по-горе често се нарича директен рекурсия.
Има и друг рекурсивни механизъм - непряка рекурсия.
Механизмът се използва за изпълнение на следната ситуация.
Първият подпрограмата е втората, все още не е описано.
Ние показваме ситуацията с пример.
процедура А (VAR х: реален);
Свързани статии