сортиране алгоритъм - алгоритъм за поръчване на елементи в списъка. Ако член на списък има множество области, поле, обслужващи критерия за ред, наречен ключ вид. На практика, като ключов често служи редица и съхранява всички данни, които не се отразява на работата на алгоритъма в останалите полета.
Изявление на проблема
,
Предполагаме, че всеки елемент (в допълнение на другата информация, не се отразява на вида) се свързва ключ. На снимачната площадка на ключовете, дадени с цел връзка -linear един (или перфектен) поръчка. за които са изпълнени следните условия:
право на делене. за всяко или или или;
преходност. за всички, ако и след това.
сортиране на обект е от не-намаляваща намиране пермутация елементи с индекси, в който ключовете са подредени в низходящ ред:
В резултат на получения алгоритъм и прилагане пермутации сортирани масив:
По същия начин, можем да определим сортирането от липсата на увеличение.
Оценка на сортиране алгоритъм
Алгоритми за сортиране се оценяват скорост на изпълнение и ефективност на паметта:
Време - основният параметър, който характеризира изпълнението на алгоритъма. Нарича се също и сложността на изчисленията. За да се рационализира важно най-лошото. средно и по-добро поведение на алгоритъма по отношение на множество входяща мощност А. Ако алгоритъм се прилага на входа на набор A. означават N = | А |. За типичен добро поведение на алгоритъма - е O (п влезте н) и лошо поведение - е O (N 2). Идеален поведение за поръчване - O (N). Сортиране алгоритми, които използват само абстрактна ключ операция сравнение винаги трябва най-малко Ω (п влезте н) сравнения. Въпреки това, има алгоритъм за сортиране Хан (Yijie Хан) с изчислителната сложност O (п влезете дневника н влезете влезете влезте н), като се използва фактът, че ключовият пространството е ограничено (това е изключително трудно, а за O -oboznacheniem много висока покривност фактор което прави невъзможно да се използват в ежедневната практика). Налице е също така концепцията за сортиране мрежи. Ако приемем, че е възможно едновременно (например, в паралелна изчисляване) да извършва няколко сравнения може да се справи числа п О (влизане 2 N) операции. Броят п трябва да се знае предварително;
Памет - серия от алгоритми изисква отпускането на допълнителна памет за временно съхраняване на данни. Обикновено тези алгоритми изискват О (лог п) памет. При оценката не се счита за място, което е на оригиналния масив и независим от входната последователност на разходите, например, за съхранение на програмен код (от всичко това potreblyaetO (1)). алгоритми за сортиране, без да консумира допълнителна памет, вижте сайта на сортиране.
Имоти и класификация
Стабилност (Engl стабилност.) - устойчиви сортиране не се променя взаимното положение на елементите с един и същ ключ [3].
Природен поведение - ефективността на метода за обработка на вече подредени или частично подредени данни. Алгоритъмът се държи естествено, ако тази функция дава възможност за въвеждане на последователност и работи по-добре.
Използване на операцията за сравнение. Алгоритмите, използвани за сортиране на елементите на сравнение между наречен на базата на сравнения. Минималната-лошия сложността на случая за тези алгоритми е O (п влезте н), но те се различават по-голяма гъвкавост на приложение. За специални случаи (типове данни), има по-ефективни алгоритми.
Друга важна характеристика на алгоритъма е неговия обхват. Има два основни вида поръчка:
Вътрешен сортиране работи масиви действително могат да се поберат в RAM случаен достъп до всяко място. Те обикновено са подредени в едно и също място, без допълнителни разходи.
Модерната архитектура на персонални компютри са широко използвани за виртуална памет памет и кеширане. сортиране алгоритъм трябва да върви добре с приложимите алгоритми за кеширане и виртуална памет.
Външни спомени за сортиране работи с голям обем от устройства, но не и с произволен достъп и последователното (организиране на файлове), т. Е. В момента се "вижда" само един от елементите, и пренавиване на разходите в сравнение с памет ненужно голям. Това налага някои допълнителни ограничения по отношение на алгоритъма и води до специална поръчка методи обикновено използват повече дисково пространство. В допълнение, достъпът до данните в външна памет е много по-бавно, отколкото работата с RAM.
Достъп до медиите се извършва по последователен начин: по всяко време могат да се четат или пишат само елемент следваща текущата.
Обемът на данни не им позволява да останат в RAM.
алгоритми също са класифицирани като:
на необходимостта от допълнителна памет или нейно отсъствие
необходимостта от познаване на структурата на данните, след операцията за сравнение, или липсата на такава
Списък на алгоритми за сортиране
В тази таблица, п - е броя на записите, които трябва да се изгладят, и K - броя на уникалните ключове.
Алгоритми за сортиране стабилен
Сортиране за това (Избор на вид) - сложност алгоритъм: O (N 2); намерят най-малката или големият елемент и да го поставите в началото или в края на един подреден списък
мехурче сортиране (angl.Bubblesort) - сложност на алгоритми: O (n2); за всяка двойка индекси се разменят, ако елементите, които не са в ред.
Сортиране разбъркване (Shaker, Коктейл вид, двупосочен метод на мехурчето) - алгоритъм сложност: О (N2)
Gnome нещо - има нещо общо с балон сортиране и сортиране чрез вмъкване. Сложността на алгоритъма - О (N2).
Сортиране вложки (сортиране чрез вмъкване) - сложност на алгоритми: O (N2); определи къде текущия елемент трябва да бъде в списъка поръча и да го поставите там
слеят сортиране (Обединяване на сортиране) - сложност на алгоритми: O (п влезте н); изисква О (п) на допълнителна памет; Ние изграждаме първата и втората половина на списъка поотделно, а след това - слеят подредени списъци
Tree вид (angl.Treesort) - сложност на алгоритми: O (п влезте н); изисква О (п) допълнителна памет
Алгоритъмът за сортиране Timsort (angl.Timsort) - сложност на алгоритми: O (п влезте н); изисква О (п) на допълнителна памет; Комбинирана алгоритъм (използва вмъкване на сортиране и сортиране чрез сливане. Проектиран за използване в Python език [
Сортиране броене (броене вид) - сложност алгоритъм: О (п + к); изисква О (п + к) допълнителна памет (разгледано 3 изпълнение)
Модулна сортиране (сортиране количка, Bucket вид) - сложност на алгоритми: O (N); изисква O (к) допълнителна памет и знание за естеството на данните, които ще бъдат сортирани, излиза извън рамките на функциите "пренареждане" и "Сравни".
Нестабилни алгоритми за сортиране
Сортиране за това (Избор на вид) - сложност алгоритъм: O (N 2); намерят най-малката или големият елемент и да го поставите в началото или в края на един подреден списък
Shell вид (Shell вид) - алгоритъм сложност: О (п влизане 2 н); се опита да подобри вмъкване на сортиране
Гребен вид (Гребен вид) - сложност на алгоритми: O (п влезете п)
Пирамидално сортиране (купчина сортиране, пирамидално сортиране) - сложност на алгоритми: O (п влезте н); конвертирате списък в купчина. Ние приемаме най-голям елемент и го добавете към края на списъка
Smoothsort (Smoothsort) - сложност на алгоритми: O (п влезете п)
Quicksort (Quicksort), в примерното изпълнение, с минимални разходи на памет - сложността на алгоритъм: О (п влизане п) - средно време, О (N2) - най-лошия случай; Той е считан за най-бързият известен с организирането на големи списъци със случайни; с дяла на оригиналния набор от данни на две половини, така че всеки елемент от първата половина е разпоредена по отношение на който и да е елемент от втората половина; След това алгоритъмът се прилага рекурсивно за всяка половина. При използване на O (N) допълнителната памет, е възможно да се направи стабилен вид.
Introsort - сложност на алгоритми: O (п влезте н), комбинация от бърз и пирамидално сортиране. Пирамидално сортиране важи и ако рекурсия дълбочина по-голяма от дневник (н).
Търпението сортиране - сложност на алгоритми: O (п влезете п) - най-лошия случай се нуждае от допълнително O (N) съхранение, също така намира най-дългата увеличаване подпоследователност
, Техен вид - сортиране рекурсивни алгоритми с сложност време.
Radix сортиране - алгоритъм сложност: О (п · к); изисква О (к) допълнителна памет.
Digital сортиране - същото като вид на корен.
Непрактично алгоритми за сортиране
Bogosort - O (N · п!) Като цяло. Случайно разбърквате масива, проверка на поръчката.
Сортиране пермутация - O (N · п!) - най-лошия възможен момент. За всяка двойка се проверява правилния ред се генерират и всички възможни пермутации на оригиналния масив.
Глупаво сортиране (Тъп вид) - О (п 3); рекурсивен версия допълнително изисква О (N2) памет
Борт Сортирайте - O (N) или O (√n), изисква специализиран хардуер
Палачинка сортиране (палачинка сортиране) - O (N), изисква специализиран хардуер
Алгоритми, които не се основават на сравнения
Модулна сортиране (сортиране количка, Bucket вид)
Лексикографски или корен сортиране (Radix вид)
Сортиране броене (броене вид)
Други алгоритми за сортиране
Свързани статии