代码

#include <algorithm> // For std::swap

void sort(unsigned *a, int n) {
    const int num_shifts = 4;
    const int bucket_count = 256;

    unsigned *temp = new unsigned[n];
    unsigned *input = a;
    unsigned *output = temp;

    for (int shift = 0; shift < num_shifts; ++shift) {
        size_t count[bucket_count] = {0};

        // Count the occurrences of each digit
        for (int i = 0; i < n; ++i) {
            unsigned digit = (input[i] >> (shift * 8)) & 0xFF;
            ++count[digit];
        }

        // Calculate prefix sums to determine positions
        size_t prefix[bucket_count] = {0};
        for (int i = 1; i < bucket_count; ++i) {
            prefix[i] = prefix[i - 1] + count[i - 1];
        }

        // Distribute elements into the output array
        for (int i = 0; i < n; ++i) {
            unsigned digit = (input[i] >> (shift * 8)) & 0xFF;
            output[prefix[digit]++] = input[i];
        }

        // Swap input and output for the next pass
        std::swap(input, output);
    }

    delete[] temp;
}

评测结果