代码

#include <iostream>
#include <vector>

void countingSort(unsigned* a, int n, int byteIndex) {
    std::vector<unsigned> output(n);  // Output array
    std::vector<int> count(256, 0);   // Count array (for byte values 0-255)

    // Counting frequency of each byte
    for (int i = 0; i < n; ++i) {
        int byte = (a[i] >> (byteIndex * 8)) & 0xFF; // Extract the byte we are sorting on
        count[byte]++;
    }

    // Calculate the prefix sum for the count array
    for (int i = 1; i < 256; ++i) {
        count[i] += count[i - 1];
    }

    // Build the output array using the count array
    for (int i = n - 1; i >= 0; --i) {
        int byte = (a[i] >> (byteIndex * 8)) & 0xFF;
        output[count[byte] - 1] = a[i];
        count[byte]--;
    }

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

void radixSort(unsigned* a, int n) {
    // Perform Counting Sort for each byte (from LSB to MSB)
    for (int byteIndex = 0; byteIndex < 4; ++byteIndex) {
        countingSort(a, n, byteIndex);
    }
}

void sort(unsigned* a, int n) {
    radixSort(a, n);
}

评测结果