代码

#include <cstdint>
#include <cstring>
#include <algorithm>

void countingSort(unsigned *input, unsigned *output, int n, int bytePos) {
    unsigned count[256] = {0};
    // Count frequency of each byte value
    for (int i = 0; i < n; i++) {
        unsigned char byte = (input[i] >> (bytePos * 8)) & 0xFF;
        count[byte]++;
    }
    // Compute cumulative sum
    for (int i = 1; i < 256; i++) {
        count[i] += count[i - 1];
    }
    // Place elements into output array in sorted order
    for (int i = n - 1; i >= 0; i--) {
        unsigned char byte = (input[i] >> (bytePos * 8)) & 0xFF;
        output[count[byte] - 1] = input[i];
        count[byte]--;
    }
}

void radixSort(unsigned *a, unsigned *aux, int n) {
    for (int k = 0; k < 4; k++) {
        countingSort(a, aux, n, k);
        std::swap(a, aux);
    }
    // After 4 passes, the sorted array is in aux, so copy it back to a
    std::memcpy(a, aux, n * sizeof(unsigned));
}

void sort(unsigned *a, int n) {
    if (n <= 1) return;
    unsigned *aux = new unsigned[n];
    radixSort(a, aux, n);
    delete[] aux;
}

评测结果