代码

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

// Helper function to perform counting sort based on a specific bit
void countingSort(unsigned *a, int n, int exp) {
    std::vector<unsigned> output(n);  // Output array
    int count[256] = {0};  // Counting array for 256 values (byte range)

    // Counting occurrences of digits (based on exp)
    for (int i = 0; i < n; i++) {
        count[(a[i] >> exp) & 0xFF]++;
    }

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

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

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

// Main Radix Sort function
void sort(unsigned *a, int n) {
    // Perform radix sort for each byte (32-bit unsigned int has 4 bytes)
    for (int exp = 0; exp < 32; exp += 8) {
        countingSort(a, n, exp);
    }
}

评测结果