Алгоритъмът за сортиране в кофата на място ли е?

2024 Автор: Lynn Donovan | [email protected]. Последно модифициран: 2023-12-15 23:43

Не, не е в- място сортиране алгоритъм . Цялата идея е този вход сортове себе си, докато са преместени в кофи . В най-лошия от добрите случаи (последователни стойности, но без повторение) необходимото допълнително пространство е толкова голямо, колкото оригиналния масив.

По този начин кои алгоритми за сортиране са налице?

Като друг пример, много алгоритми за сортиране пренареждат масивите в сортиран ред на място, включително: сортиране на мехурчета , сортиране с гребен, сортиране по избор, сортиране с вмъкване , Heapsort и Shell сортиране. Тези алгоритми изискват само няколко указателя, така че тяхната пространствена сложност е O(log n). Quicksort работи на място с данните, които трябва да бъдат сортирани.

Впоследствие въпросът е как работи алгоритъмът за сортиране в кофа? Сортиране в кофа , или bin сортиране , е алгоритъм за сортиране че върши работа чрез разпределяне на елементите на масив в брой кофи . Всеки кофа е тогава сортирани индивидуално, или с помощта на различен алгоритъм за сортиране , или чрез рекурсивно прилагане на алгоритъм за сортиране на кофата . Настройте масив от първоначално празни " кофи ".

Съответно, как прилагате алгоритъм за сортиране в кофа?

1. Да предположим, че входният масив е: Създайте масив с размер 10.
2. Вмъкнете елементи в кофите от масива. Елементите се вмъкват според обхвата на кофата.
3. Елементите на всяка кофа се сортират с помощта на някой от стабилните алгоритми за сортиране.
4. Елементите от всяка кофа се събират.

Къде се използва сортиране в кофа?

Сортиране в кофа е основно полезно, когато входът е равномерно разпределен в диапазон. Например, разгледайте следния проблем. Вид голям набор от числа с плаваща запетая, които са в диапазон от 0,0 до 1,0 и са равномерно разпределени в диапазона.