Radix sort is a non-comparison integer sorting aglorithm that sorts numbers by distributing them into buckets based on their digits. The alogrithm processes the numbers from the least siginficant digit to the most significant digit.

Radix sort can be implemented using two primary approaches:

• This group of sorting algorithms differs primarily in how they handle buckets:
• Radix sort: Sorts based on the digits of the key;
• Counting sort: Each bucket contains a single key value;
• Bucket sort: Buckets store a range of values;

JavaScript

 1 function radixSort(arr, maxDigit) {
 2     var modulo = 10;
 3     var divisor = 1;
 4     for (var i = 0; i < maxDigit; i++) {
 5         divisor *= 10;
 6         modulo *= 10;
 7         var bucket = [];
 8         for (var j = 0; j < arr.length; j++) {
 9             var key = parseInt((arr[j] % modulo) / divisor);
10             if (bucket[key] == null) {
11                 bucket[key] = [];
12             }
13             bucket[key].push(arr[j]);
14         }
15         var position = 0;
16         for (var j = 0; j < bucket.length; j++) {
17             var value = null;
18             if (bucket[j] != null) {
19                 while ((value = bucket[j].shift()) != null) {
20                     arr[position++] = value;
21                 }
22             }
23         }
24     }
25     return arr;
26 }

C语言

 1 #include<stdio.h>
 2 #define MAX 20
 3 #define BASE 10
 4 
 5 void print(int *a, int n) {
 6     int i;
 7     for (i = 0; i < n; i++) {
 8         printf("%d\t", a[i]);
 9     }
10 }
11 
12 void radixsort(int *a, int n) {
13     int i, b[MAX], m = a[0], exp = 1;
14 
15     for (i = 1; i < n; i++) {
16         if (a[i] > m) {
17             m = a[i];
18         }
19     }
20 
21     while (m / exp > 0) {
22         int bucket[BASE] = {0};
23 
24         for (i = 0; i < n; i++) {
25             bucket[(a[i] / exp) % BASE]++;
26         }
27 
28         for (i = 1; i < BASE; i++) {
29             bucket[i] += bucket[i - 1];
30         }
31 
32         for (i = n - 1; i >= 0; i--) {
33             b[--bucket[(a[i] / exp) % BASE]] = a[i];
34         }
35 
36         for (i = 0; i < n; i++) {
37             a[i] = b[i];
38         }
39 
40         exp *= BASE;
41     }
42 }
43 
44 int main() {
45     int arr[MAX];
46     int i, n;
47 
48     printf("Enter total elements (n <= %d) : ", MAX);
49     scanf("%d", &n);
50     n = n < MAX ? n : MAX;
51 
52     printf("Enter %d Elements : ", n);
53     for (i = 0; i < n; i++) {
54         scanf("%d", &arr[i]);
55     }
56 
57     printf("\nARRAY  : ");
58     print(&arr[0], n);
59 
60     radixsort(&arr[0], n);
61 
62     printf("\nSORTED : ");
63     print(&arr[0], n);
64     printf("\n");
65 
66     return 0;
67 }

C++

 1 int maxdigit(int data[], int n) // Função para determinar o número de dígitos
 2 {
 3     int maxData = data[0];
 4     int d = 1;
 5     int p = 10;
 6     for (int i = 1; i < n; i++) {
 7         if (data[i] > maxData) {
 8             maxData = data[i];
 9         }
10     }
11     while (maxData > 0) {
12         maxData /= p;
13         d++;
14     }
15     return d;
16 }
17 
18 void radixsort(int data[], int n) // Algoritmo de Radix Sort
19 {
20     int d = maxdigit(data, n);
21     int *tmp = new int[n];
22     int *count = new int[10]; // Contador
23     int i, j, k;
24     int radix = 1;
25 
26     for (i = 1; i <= d; i++) {
27         for (j = 0; j < 10; j++) {
28             count[j] = 0;
29         }
30 
31         for (j = 0; j < n; j++) {
32             k = (data[j] / radix) % 10;
33             count[k]++;
34         }
35 
36         for (j = 1; j < 10; j++) {
37             count[j] += count[j - 1];
38         }
39 
40         for (j = n - 1; j >= 0; j--) {
41             k = (data[j] / radix) % 10;
42             tmp[count[k] - 1] = data[j];
43             count[k]--;
44         }
45 
46         for (j = 0; j < n; j++) {
47             data[j] = tmp[j];
48         }
49 
50         radix *= 10;
51     }
52 
53     delete[] tmp;
54     delete[] count;
55 }