代码

#include <iostream>
#include <vector>
#include <algorithm>

void countingSortByByte(unsigned *a, int n, int shift) {
    const int range = 256;  // 0-255 for a byte
    std::vector<int> count(range, 0);
    std::vector<unsigned> output(n);

    // Count occurrences of each byte
    for (int i = 0; i < n; i++) {
        int byteValue = (a[i] >> shift) & 0xFF;  // Extract the byte value
        count[byteValue]++;
    }

    // Compute cumulative count
    for (int i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }

    // Build output array
    for (int i = n - 1; i >= 0; i--) {
        int byteValue = (a[i] >> shift) & 0xFF;
        output[count[byteValue] - 1] = a[i];
        count[byteValue]--;
    }

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

void sort(unsigned *a, int n) {
    // Perform radix sort on 4 bytes (32 bits)
    for (int shift = 0; shift < 32; shift += 8) {
        countingSortByByte(a, n, shift);
    }
}

评测结果