Pseudokod

Lekcja 4 z 9 w kursie Sortowanie radixowe — seria DSA w Coddy.

countingSortByDigit(array, exp):
   n = length(array)
   output = array of size n
   count = array of 10 zeros
   for each x in array:                 # tally each digit
      count[(x / exp) % 10] += 1
   for d from 1 to 9:                   # running totals -> positions
      count[d] += count[d - 1]
   for k from n-1 down to 0:            # place from the back (stable)
      d = (array[k] / exp) % 10
      count[d] -= 1
      output[count[d]] = array[k]
   return output

radixSort(array):
   max = largest value in array
   exp = 1
   while max / exp > 0:
      array = countingSortByDigit(array, exp)
      exp = exp * 10

exp to wartość pozycyjna: 1 dla jedności, 10 dla dziesiątek, 100 dla setek. (x / exp) % 10 wyodrębnia tę cyfrę.
countingSortByDigit to stabilne sortowanie według jednej cyfry: zlicza wystąpienia każdej cyfry, zamienia te liczby na pozycje, a następnie umieszcza elementy od końca, aby zachować kolejność.
radixSort po prostu wykonuje takie przejście dla każdej cyfry i kończy, gdy exp przekroczy największą liczbę.

Spróbuj swoich sił

Ta lekcja nie zawiera wyzwania z kodem.