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:

  1. Utwórz tablicę elementów [0..n-1].
  2. Call Bucket Sortuj kilkakrotnie według najbardziej znaczącej cyfry każdego elementu jako klucza.
  3. Zwraca posortowaną tablicę.

Przykład sortowania Radix:

Przykład sortowania Radix

Space Auxiliary: O(n)
Złożoność czasu: O(n)



Modified text is an extract of the original Stack Overflow Documentation
Licencjonowany na podstawie CC BY-SA 3.0
Nie związany z Stack Overflow