代码

#include <bits/stdc++.h>

// Function to get the digit at the dth position
unsigned getDigit(unsigned number, int d, int radix) {
    return (number / static_cast<unsigned>(pow(radix, d))) % radix;
}

// Counting sort for a specific digit
void countingSortByDigit(unsigned* a, int n, int digit, int radix) {
    std::vector<int> count(radix, 0);
    std::vector<unsigned> output(n);

    // Count occurrences of each digit
    for (int i = 0; i < n; i++) {
        count[getDigit(a[i], digit, radix)]++;
    }

    // Cumulative count
    for (int i = 1; i < radix; i++) {
        count[i] += count[i - 1];
    }

    // Build the output array
    for (int i = n - 1; i >= 0; i--) {
        output[count[getDigit(a[i], digit, radix)] - 1] = a[i];
        count[getDigit(a[i], digit, radix)]--;
    }

    // Copy the output array to the original array
    for (int i = 0; i < n; i++) {
        a[i] = output[i];
    }
}

// Radix sort function
void sort(unsigned* a, int n) {
    const int radix = 256; // Using 8 bits per digit
    const int numDigits = 4; // 32 bits / 8 bits per digit

    // Sort for each digit
    for (int digit = 0; digit < numDigits; digit++) {
        countingSortByDigit(a, n, digit, radix);
    }
}

评测结果