Radix sort (sắp xếp cơ số)

1def radix_sort(a):2    # Sort by each decimal digit, least significant first3    max_value = max(a)4    exp = 15    while max_value // exp > 0:6        a = sort_by_digit(a, exp)7        exp *= 108    return a9
10
11def sort_by_digit(a, exp):12    buckets = [[] for _ in range(10)]13    for value in a:14        digit = (value // exp) % 1015        buckets[digit].append(value)16    # Concatenating buckets 0..9 keeps the sort stable17    return [value for bucket in buckets for value in bucket]18
19
20nums = [170, 45, 75, 90, 802, 24, 2, 66]21print("Before:", nums)22print("After: ", radix_sort(nums))

1function radixSort(arr) {2    let a = [...arr];3    const max = Math.max(...a);4    // One counting pass per digit, least significant first5    for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {6        const buckets = Array.from({ length: 10 }, () => []);7        for (const x of a) {8            buckets[Math.floor(x / exp) % 10].push(x);9        }10        a = buckets.flat();11    }12    return a;13}14
15const data = [170, 45, 75, 90, 802, 24, 2, 66];16console.log("Before:", data);17console.log("Sorted:", radixSort(data));

1import java.util.Arrays;2
3public class Main {4    static void radixSort(int[] arr) {5        int max = 0;6        for (int v : arr) max = Math.max(max, v);7        // One stable counting pass per decimal digit8        for (int exp = 1; max / exp > 0; exp *= 10) countingPass(arr, exp);9    }10
11    static void countingPass(int[] arr, int exp) {12        int n = arr.length;13        int[] out = new int[n];14        int[] count = new int[10];15        for (int v : arr) count[(v / exp) % 10]++;16        for (int i = 1; i < 10; i++) count[i] += count[i - 1];17        // Walk backwards to keep the pass stable18        for (int i = n - 1; i >= 0; i--) {19            int digit = (arr[i] / exp) % 10;20            out[--count[digit]] = arr[i];21        }22        System.arraycopy(out, 0, arr, 0, n);23    }24
25    public static void main(String[] args) {26        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};27        System.out.println("Before: " + Arrays.toString(arr));28        radixSort(arr);29        System.out.println("After:  " + Arrays.toString(arr));30    }31}

1#include <algorithm>2#include <iostream>3#include <vector>4
5void printVec(const std::vector<int>& a) {6    for (int x : a) std::cout << x << " ";7    std::cout << "\n";8}9
10// Stable counting sort on one decimal digit (exp = 1, 10, 100, ...)11void countingPass(std::vector<int>& a, int exp) {12    std::vector<int> output(a.size());13    std::vector<int> count(10, 0);14    for (int x : a) ++count[(x / exp) % 10];15    for (int d = 1; d < 10; ++d) count[d] += count[d - 1];16    for (int i = static_cast<int>(a.size()) - 1; i >= 0; --i) {17        int digit = (a[i] / exp) % 10;18        output[--count[digit]] = a[i];19    }20    a = output;21}22
23void radixSort(std::vector<int>& a) {24    int maxVal = *std::max_element(a.begin(), a.end());25    for (int exp = 1; maxVal / exp > 0; exp *= 10) {26        countingPass(a, exp);27    }28}29
30int main() {31    std::vector<int> data = {170, 45, 75, 90, 802, 24, 2, 66};32    std::cout << "Before: ";33    printVec(data);34    radixSort(data);35    std::cout << "After:  ";36    printVec(data);37    return 0;38}

1#include <stdio.h>2#include <stdlib.h>3
4void printArr(const int a[], int n) {5    for (int i = 0; i < n; i++) printf("%d ", a[i]);6    printf("\n");7}8
9// Stable counting sort on one decimal digit (exp = 1, 10, 100, ...)10void countingPass(int a[], int n, int exp) {11    int* output = malloc(n * sizeof(int));12    int count[10] = {0};13    for (int i = 0; i < n; i++) count[(a[i] / exp) % 10]++;14    for (int d = 1; d < 10; d++) count[d] += count[d - 1];15    for (int i = n - 1; i >= 0; i--) {16        int digit = (a[i] / exp) % 10;17        output[--count[digit]] = a[i];18    }19    for (int i = 0; i < n; i++) a[i] = output[i];20    free(output);21}22
23void radixSort(int a[], int n) {24    int maxVal = a[0];25    for (int i = 1; i < n; i++) {26        if (a[i] > maxVal) maxVal = a[i];27    }28    for (int exp = 1; maxVal / exp > 0; exp *= 10) {29        countingPass(a, n, exp);30    }31}32
33int main(void) {34    int data[] = {170, 45, 75, 90, 802, 24, 2, 66};35    int n = sizeof(data) / sizeof(data[0]);36    printf("Before: ");37    printArr(data, n);38    radixSort(data, n);39    printf("After:  ");40    printArr(data, n);41    return 0;42}