algorithm
Sortowanie Radix
Szukaj…
Radix Sort Podstawowe informacje
Radix Sort jest dolnym algorytmem opartym na porównaniu. Jest to nieporównawczy algorytm sortowania liczb całkowitych, który sortuje dane za pomocą kluczy całkowitych poprzez grupowanie kluczy według pojedynczych cyfr, które mają pewną znaczącą pozycję i wartość. Sortowanie Radix jest algorytmem liniowego sortowania w czasie, który sortuje w czasie O (n + k), gdy elementy są w zakresie od 1 do k. Ideą Radix Sort jest sortowanie cyfra po cyfrze, zaczynając od najmniej znaczącej cyfry do najbardziej znaczącej cyfry. Sortowanie Radix wykorzystuje sortowanie zliczające jako podprogram do sortowania. Sortowanie Radix to uogólnienie sortowania kubełkowego.
Pseudo kod dla sortowania kubełkowego:
- Utwórz tablicę elementów [0..n-1].
- Call Bucket Sortuj kilkakrotnie według najbardziej znaczącej cyfry każdego elementu jako klucza.
- Zwraca posortowaną tablicę.
Przykład sortowania Radix:
Space Auxiliary: O(n)
Złożoność czasu: O(n)