algorithm
Radix sorteren
Zoeken…
Radix Sorteer basisinformatie
Radix Sort is een algoritme gebaseerd op ondergrensvergelijking. Het is een niet-vergelijkend algoritme voor het sorteren van gehele getallen dat gegevens sorteert met geheeltallige sleutels door sleutels te groeperen op afzonderlijke cijfers die een significante positie en waarde delen. Radix-sortering is een lineair tijdsorteeralgoritme dat in O (n + k) -tijd sorteert wanneer elementen zich in het bereik van 1 tot k bevinden. Het idee van Radix Sort is om cijfer voor cijfer te sorteren, beginnend van het minst significante cijfer tot het meest significante cijfer. Radix sorteert gebruik sorteer sorteren als een subroutine om te sorteren. Radix-sortering is generalisatie van bucket-sortering.
Pseudo-code voor bucket-sortering:
- Maak een array van [0..n-1] elementen.
- Oproepemmer Sorteer herhaaldelijk op ten minste tot het meest significante cijfer van elk element als sleutel.
- Retourneer de gesorteerde array.
Voorbeeld van Radix-sortering:
Extra ruimte: O(n)
Tijd Complexiteit: O(n)