代码

#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);
    }
}

int main() {
    int n = 100000; // Example size for testing
    unsigned *a = new unsigned[n];
    
    // Fill the array with random numbers for testing
    for (int i = 0; i < n; i++) {
        a[i] = rand();
    }

    // Sort the array
    sort(a, n);

    // Output the sorted array (for testing purposes)
    for (int i = 0; i < 10; i++) {
        std::cout << a[i] << " ";
    }
    std::cout << std::endl;

    delete[] a;
    return 0;
}

评测结果