Стабилна (стабилна) за сортиране - сортиране, което не се променя относителната реда на сортират елементи, които имат едни и същи клавиши.
Устойчивото развитие е много важна характеристика на един алгоритъм за сортиране, но, въпреки това, тя почти винаги може да се постигне чрез удължаване на оригиналните ключове дължи повече информация за първоначалната им цел. Въпреки очевидната необходимост, подсказва името, не се изисква стабилността за точността на сортиране и често не се наблюдава, тъй като тя е почти винаги е необходимо да се осигури допълнителна памет и време.
При сортиране на записите на формата [фамилно име, собствено име] на ключовите стойности за имената на Сергей Иванов и Иван Иванов ще бъде същото, така че стабилни сортиране непрекъснато Сергей и Иван места (Python 3. сортиране timsort [1]):
В резултат на това записите се сортират само с фамилното име, като се запазват първоначалния ред сред записи със същите имена:
Сортиране, който е основният елемент на скъпи дупки курсове - Wheeler. Тя трябва да бъде стабилна.
Алгоритми за сортиране стабилен
Сортиране слее с допълнителна памет
С този алгоритъм, сортирането се извършва първо рекурсивен разделяне на части на оригиналния масив, доколкото всяка от масива не би един или нулеви елементи (за всяка стъпка рекурсия разделянето се провежда в половината). След това част от двойките "сливане". Общият сложността на алгоритъма - О (п влизане п), където алгоритъм се вода (н) повече масиви с памет за съхраняване на синтез.
Сортиране използване стабилен участък
Този алгоритъм е подобен на бърз алгоритъм вид. Точно както един бърз алгоритъм за сортиране алгоритъм източник масив е разделен на две части - едната в всички елементи е по-малка или равна на някои държави подкрепа, а другият - по-голям или равен. След рекурсивно разделени части масив се сортира по същия начин. Разликата между този алгоритъм и бърз алгоритъм за сортиране, който се използва тук, вместо стабилна разделение нестабилна. По-долу показва изпълнението на алгоритъма в Псевдокод:
За стабилна разделение масив изисква O (п влезте н) елементарни операции. Тъй като "дълбочина", осъществяван от рекурсивно спускане среден случай е O (влезте н) общото сложността на алгоритъма е O (п log² н). В този алгоритъм, необходима за изпълнение на рекурсивни O (влезте н) стека, а в най-лошия случай, общата сложност е O (N ² влезте н) и изисква O (N) памет.
Обединяване на сортиране алгоритми без допълнителна памет
Всички от следните алгоритми се основават на сливането вече се сортира масиви, без използването на допълнителна памет извън О (log² п) стек (което - .. Така нареченото състояние на минимална памет [2]) и се различават само в алгоритъма за сливане. Следното е псевдо-код алгоритми (сливане алгоритми - процедура Обединяване - са показани отделно за всеки метод):
Прат алгоритъм
Алгоритъмът Pratt сортирани масиви са два елемента, а и р. които са медианите на масива, състояща се от елементите на двата масива. След това, за цялата решетка може да бъде представен като aαbxβy. След това, циклични елементи изместване, при което се получават следната последователност: axβαby. Освен алгоритъм слят рекурсивно повтаря за брадва и масиви.
циклична смяна елемент изисква О (п) на елементарните операции и O (1) допълнителна памет, и търсенето на две медиани вече сортирани масиви - О (log² п) на елементарните операции и O (1) допълнителна памет. Тъй като извършва O (влезте н) на рекурсия стъпки, сложността на такъв алгоритъм сливане на е O (п влезте н), както и цялостната сложност на алгоритъм за сортиране - O (п log² н). В този алгоритъм изисква О (log² п) стек.
Алгоритъм без Търсене Media
Търсене по медиите може да се отърве от предходната алгоритъм, както следва. Най-голямата от двете елемент масиви средата изберете α (поддържащ елемент). Освен това, по-малък набор намери първата поява на позицията на елемент по-голяма от или равна α. Ние наричаме това бета. След това, елементите на циклични смени само като в алгоритъма Pratt (aαbxβy → axβαby) и се извършва рекурсивно сливане получените части. В псевдо-код сливане алгоритъм е показано по-долу.
FindFirstPosition процедури и FindLastPosition практически идентични с процедурата на двоично търсене:
За разлика от Pratt алгоритъм, дял алгоритъм може да бъде по същество неравномерно. Но дори и в най-лошия случай, алгоритъмът ще разбие цялата гама от [а. Y] в съотношение 3: 1 (ако всички елементи на втората лента ще бъдат по-големи или по-малки от референтните и по този начин двете групи имат същия брой елементи). Това гарантира, логаритмична брой на рекурсия стъпки, когато сливането някакви масиви. По този начин ние виждаме, че по същия начин, както при алгоритъм Прат, сложността на сливането на алгоритъма е O (п влезте н), сложността на алгоритъм за сортиране - O (п log² н), както и необходимата памет - O (log² н).
Стабилен сортиране без допълнителна памет за време O (п влезете п)
Начини за подобряване на алгоритмите
- Във всички по-горе алгоритми в разделението на оригиналния масив в частта от рекурсивни разделяне може да бъде спряно, ако сумата на счупване на масива е достатъчно малък. След това можете да се прилага просто алгоритми за сортиране (например, поставяне на сортиране), която се знае, че работи по-бързо от сложно, ако размерът на входния масив е малък. В действителност тази техника е не само приложим за алгоритмите, представени тук, но всеки друг алгоритъм, при което се използва рекурсивен разлагане на източник на масива (например, конвенционален летливи Quicksort). Конкретният брой входни елементи, които е необходимо да се премине прост алгоритъм за сортиране, зависи от компютъра.
- алгоритъм Прат алгоритъм, без да търсите и медианите алгоритъм, използващ стабилна разделение, вместо всеки път, когато се обадите рекурсивно сливането, е възможно да се разпределят динамично множество временни променливи. След това можете да продължите да варира дял само толкова дълго, колкото броя на елементите в по-голям диапазон е по-малка или равна на капацитета на временен масив. В действителност, на определен етап на рекурсия, без да търсят медианите Прат алгоритъм, и алгоритъмът се превръщат в един прост алгоритъм за сливането. По този начин. ако достатъчно динамична системна памет, асимптотичната време може да се намали до О (п влизане п) вместо О (п log² п).
Свързани статии